7,129
个编辑
更改
→属性
二分图可以用以下几种不同的方式来描述其特征：
二分图可以用以下几种不同的方式来描述其特征：
* A graph is bipartite [[if and only if]] it does not contain an [[Cycle (graph theory)|odd cycle]]. Theorem 2.1.3, p. 8. Asratian et al. attribute this characterization to a 1916 paper by [[Dénes Kőnig]]. For infinite graphs, this result requires the [[axiom of choice]].
* 当且仅当它不包含奇数环的时候，该图为二分图。
* 当且仅当图是2色系图2-colorable（即，其色数小于或等于2，详见“图着色”）时，该图为二分图。<ref name="adh98-7"/>
* 当且仅当图是2色系图2-colorable（即，其色数小于或等于2，详见“图着色”）时，该图为二分图。<ref name="adh98-7"/>
* 当且仅当它是二分图时，图的频谱是对称的。<ref>{{citation | last = Biggs | first = Norman | edition = 2nd | isbn = 9780521458979 | page = 53
* 当且仅当它是二分图时，图的频谱是对称的。<ref>{{citation | last = Biggs | first = Norman | edition = 2nd | isbn = 9780521458979 | page = 53
| pages = 51–73 | title = Bigraphs versus digraphs via matrices | volume = 4 | year = 1980}}. Brualdi et al. credit the idea for this equivalence to {{citation | doi = 10.4153/CJM-1958-052-0 | last1 = Dulmage | first1 = A. L. | last2 = Mendelsohn | first2 = N. S. | author2-link = Nathan Mendelsohn | mr = 0097069 | journal = Canadian Journal of Mathematics | pages = 517–534 | title = Coverings of bipartite graphs | volume = 10
| pages = 51–73 | title = Bigraphs versus digraphs via matrices | volume = 4 | year = 1980}}. Brualdi et al. credit the idea for this equivalence to {{citation | doi = 10.4153/CJM-1958-052-0 | last1 = Dulmage | first1 = A. L. | last2 = Mendelsohn | first2 = N. S. | author2-link = Nathan Mendelsohn | mr = 0097069 | journal = Canadian Journal of Mathematics | pages = 517–534 | title = Coverings of bipartite graphs | volume = 10
| year = 1958}}.</ref>通过这种构建方式，二分图可以被解释为是一个[[有向图]]的''' 二分双重覆盖 Bipartite double cover'''。
| year = 1958}}.</ref>通过这种构建方式，二分图可以被解释为是一个[[有向图]]的''' 二分双重覆盖 Bipartite double cover'''。
== 算法 ==
== 算法 ==