7,129
个编辑
更改
跳到导航
跳到搜索
第40行：
第40行： − + + + +
→特征表述
* 当且仅当它不包含奇数环的时候，该图为二分图。
* 当且仅当它不包含奇数环的时候，该图为二分图。
* 当且仅当图是2色系图2-colorable（即，其色数小于或等于2，详见“图着色”）时，该图为二分图。<ref name="adh98-7"/>
* 当且仅当图是它是2-可着色的（即其色数小于或等于2）时，该图为二分图。<ref name="adh98-7"/>
* 一个图是二部图当且仅当它的顶点集 <math>V</math>可分为2个集合 <math>A</math>和<math>B</math>，以至于<math>\sum_{v \in A} \deg(v) = \sum_{v \in B} \deg(v)</math>, <math> \forall v \in A \deg(v) \leq |B| </math> 和<math> \forall v \in B \deg(v) \leq |A| </math>
* 任何由以下组成的二部图 <math>n</math> 顶点最多可以有 <math>n^2 / 4</math>边缘。
* 当且仅当它是二分图时，图的频谱是对称的。<ref>{{citation | last = Biggs | first = Norman | edition = 2nd | isbn = 9780521458979 | page = 53
* 当且仅当它是二分图时，图的频谱是对称的。<ref>{{citation | last = Biggs | first = Norman | edition = 2nd | isbn = 9780521458979 | page = 53
| publisher = Cambridge University Press | series = Cambridge Mathematical Library | title = Algebraic Graph Theory | url = https://books.google.com/books?id=6TasRmIFOxQC&pg=PA53 | year = 1994}}.</ref>
| publisher = Cambridge University Press | series = Cambridge Mathematical Library | title = Algebraic Graph Theory | url = https://books.google.com/books?id=6TasRmIFOxQC&pg=PA53 | year = 1994}}.</ref>
<br>
===柯尼希定理和完美图 Kőnig's theorem and perfect graphs ===
===柯尼希定理和完美图 Kőnig's theorem and perfect graphs ===