7,129
个编辑
更改
跳到导航
跳到搜索
第40行：
第40行： − +
→特征表述
* 当且仅当它不包含奇数环的时候，该图为二分图。
* 当且仅当它不包含奇数环的时候，该图为二分图。
* 当且仅当图是它是2-可着色的（即其色数小于或等于2）时，该图为二分图。<ref name="adh98-7"/>
* 当且仅当图是它是2-可着色的（即其色数小于或等于2）时，该图为二分图。<ref name="adh98-7">Asratian, Armen S.; Denley, Tristan M. J.; Häggkvist, Roland (1998), Bipartite Graphs and their Applications, Cambridge Tracts in Mathematics, 131, Cambridge University Press, ISBN 9780521593458</ref>
* 一个图是二部图当且仅当它的顶点集 <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>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>边缘。
* 任何由以下组成的二部图 <math>n</math> 顶点最多可以有 <math>n^2 / 4</math>边缘。