1,592
个编辑
更改
Moved page from wikipedia:en:Bipartite graph (history)
此词条暂由彩云小译翻译，未经人工整理和审校，带来阅读不便，请见谅。
[[Image:Simple-bipartite-graph.svg|thumb|Example of a bipartite graph without cycles]]
Example of a bipartite graph without cycles
没有圈的二部图的例子
[[File:Biclique K 3 5.svg|thumbnail|A [[complete bipartite graph]] with m = 5 and n = 3]]
A [[complete bipartite graph with m = 5 and n = 3]]
A [[ m = 5和 n = 3的完全二分图]
In the [[mathematics|mathematical]] field of [[graph theory]], a '''bipartite graph''' (or '''bigraph''') is a [[Graph (discrete mathematics)|graph]] whose [[vertex (graph theory)|vertices]] can be divided into two [[disjoint sets|disjoint]] and [[Independent set (graph theory)|independent sets]] <math>U</math> and <math>V</math> such that every [[edge (graph theory)|edge]] connects a vertex in <math>U</math> to one in <math>V</math>. Vertex sets <math>U</math> and <math>V</math> are usually called the ''parts'' of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length [[cycle (graph theory)|cycles]].<ref name=diestel2005graph>{{cite book|last=Diestel|first=Reinard|title=Graph Theory, Grad. Texts in Math|year=2005|publisher=Springer|isbn=978-3-642-14278-9|url=http://diestel-graph-theory.com/}}</ref><ref>{{citation
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets <math>U</math> and <math>V</math> such that every edge connects a vertex in <math>U</math> to one in <math>V</math>. Vertex sets <math>U</math> and <math>V</math> are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.<ref>{{citation
在图论的数学领域中，二部图(或称二部图)是一种图，它的顶点可以分为两个不相交的独立集合。顶点集 < math > u </math > 和 < math > v </math > 通常被称为图的部分。等价地，二部图是一个不包含任何奇数长度圈的图
| last1 = Asratian
| last1 = Asratian
1 = Asratian
| first1 = Armen S.
| first1 = Armen S.
1 = Armen s.
| last2 = Denley
| last2 = Denley
2 = Denley
| first2 = Tristan M. J.
| first2 = Tristan M. J.
2 = Tristan m. j.
| last3 = Häggkvist
| last3 = Häggkvist
| last3 = Häggkvist
| first3 = Roland
| first3 = Roland
3 = Roland
| isbn = 9780521593458
| isbn = 9780521593458
9780521593458
| publisher = Cambridge University Press
| publisher = Cambridge University Press
剑桥大学出版社
| series = Cambridge Tracts in Mathematics
| series = Cambridge Tracts in Mathematics
| 系列 = 剑桥数学丛书
| title = Bipartite Graphs and their Applications
| title = Bipartite Graphs and their Applications
| title = 二部图及其应用
| volume = 131
| volume = 131
131
| year = 1998
| year = 1998
1998年
| url-access = registration
| url-access = registration
| url-access = registration
| url = https://archive.org/details/bipartitegraphst0000asra
| url = https://archive.org/details/bipartitegraphst0000asra
Https://archive.org/details/bipartitegraphst0000asra
}}.</ref>
}}.</ref>
} . </ref >
The two sets <math>U</math> and <math>V</math> may be thought of as a [[graph coloring|coloring]] of the graph with two colors: if one colors all nodes in <math>U</math> blue, and all nodes in <math>V</math> green, each edge has endpoints of differing colors, as is required in the graph coloring problem.<ref name="adh98-7"/><ref name="s12">{{citation
The two sets <math>U</math> and <math>V</math> may be thought of as a coloring of the graph with two colors: if one colors all nodes in <math>U</math> blue, and all nodes in <math>V</math> green, each edge has endpoints of differing colors, as is required in the graph coloring problem.<ref name="s12">{{citation
这两个集合 < math > u </math > 和 < math > v </math > 可以被看作是两种颜色的图的着色: 如果 < math > u </math > 蓝色中的所有节点都有一种颜色，而 < math > v </math > 绿色中的所有节点都有一种颜色，那么每个边的端点都有不同颜色的端点，就像图着色问题中所要求的那样。12"> { citation
| last = Scheinerman | first = Edward R. | authorlink = Ed Scheinerman
| last = Scheinerman | first = Edward R. | authorlink = Ed Scheinerman
作者: Ed Scheinerman | last = Scheinerman | first = Edward r | authorlink = Ed Scheinerman
| edition = 3rd
| edition = 3rd
3 rd
| isbn = 9780840049421
| isbn = 9780840049421
9780840049421
| page = 363
| page = 363
363
| publisher = Cengage Learning
| publisher = Cengage Learning
2012年3月24日 | publisher = 圣智学习出版公司
| title = Mathematics: A Discrete Introduction
| title = Mathematics: A Discrete Introduction
| title = 数学: 离散介绍
| url = https://books.google.com/books?id=DZBHGD2sEYwC&pg=PA363
| url = https://books.google.com/books?id=DZBHGD2sEYwC&pg=PA363
Https://books.google.com/books?id=dzbhgd2seywc&pg=pa363
| year = 2012}}.</ref> In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a [[Gallery of named graphs|triangle]]: after one node is colored blue and another green, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color.
| year = 2012}}.</ref> In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a triangle: after one node is colored blue and another green, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color.
2012}}.相比之下，对于非二部图，如三角形，这样的着色是不可能的: 在一个节点被着成蓝色和另一个绿色之后，三角形的第三个顶点连接到两种颜色的顶点上，这样就不能给它分配任何一种颜色。
One often writes <math>G=(U,V,E)</math> to denote a bipartite graph whose partition has the parts <math>U</math> and <math>V</math>, with <math>E</math> denoting the edges of the graph. If a bipartite graph is not [[connected graph|connected]], it may have more than one bipartition;<ref>{{citation
One often writes <math>G=(U,V,E)</math> to denote a bipartite graph whose partition has the parts <math>U</math> and <math>V</math>, with <math>E</math> denoting the edges of the graph. If a bipartite graph is not connected, it may have more than one bipartition;<ref>{{citation
人们经常用 < math > g = (u，v，e) </math > 来表示一个二部图，其分区由 < math > u </math > 和 < math > v </math > 组成，用 < math > e </math > 表示图的边。如果一个二部图是不连通的，它可能有一个以上的二部图
| last1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand
| last1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand
1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand
| last2 = Zhang | first2 = Ping | author2-link = Ping Zhang (graph theorist)
| last2 = Zhang | first2 = Ping | author2-link = Ping Zhang (graph theorist)
| last2 = Zhang | first2 = Ping | author2-link = Ping Zhang (图论学家)
| isbn = 9781584888000
| isbn = 9781584888000
9781584888000
| page = 223
| page = 223
223
| publisher = CRC Press
| publisher = CRC Press
| publisher = CRC Press
| series = Discrete Mathematics And Its Applications
| series = Discrete Mathematics And Its Applications
系列 = 离散数学及其应用
| title = Chromatic Graph Theory
| title = Chromatic Graph Theory
彩色图论
| url = https://books.google.com/books?id=_l4CJq46MXwC&pg=PA223
| url = https://books.google.com/books?id=_l4CJq46MXwC&pg=PA223
Https://books.google.com/books?id=_l4cjq46mxwc&pg=pa223
| volume = 53
| volume = 53
53
| year = 2008}}.</ref> in this case, the <math>(U,V,E)</math> notation is helpful in specifying one particular bipartition that may be of importance in an application. If <math>|U|=|V|</math>, that is, if the two subsets have equal [[cardinality]], then <math>G</math> is called a ''balanced'' bipartite graph.<ref name="adh98-7">{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 7.</ref> If all vertices on the same side of the bipartition have the same [[Degree (graph theory)|degree]], then <math>G</math> is called [[biregular graph|biregular]].
| year = 2008}}.</ref> in this case, the <math>(U,V,E)</math> notation is helpful in specifying one particular bipartition that may be of importance in an application. If <math>|U|=|V|</math>, that is, if the two subsets have equal cardinality, then <math>G</math> is called a balanced bipartite graph. If all vertices on the same side of the bipartition have the same degree, then <math>G</math> is called biregular.
2008}}.在这种情况下，< math > (u，v，e) </math > 符号有助于指定一个特定的双分区，这个双分区在应用程序中可能非常重要。如果 < math > | u | = | v | </math > ，也就是说，如果两个子集具有相等的基数，那么 < math > g </math > 被称为平衡二部图。如果二分区同一侧的所有顶点都具有相同的度数，那么 < math > g </math > 称为二正则。
==Examples==
When modelling [[heterogeneous relation|relations]] between two different classes of objects, bipartite graphs very often arise naturally. For instance, a graph of football players and clubs, with an edge between a player and a club if the player has played for that club, is a natural example of an ''affiliation network'', a type of bipartite graph used in [[social network analysis]].<ref>{{citation
When modelling relations between two different classes of objects, bipartite graphs very often arise naturally. For instance, a graph of football players and clubs, with an edge between a player and a club if the player has played for that club, is a natural example of an affiliation network, a type of bipartite graph used in social network analysis.<ref>{{citation
当建立两类不同对象之间的模型关系时，二部图往往自然而然地出现。例如，一个足球运动员和俱乐部的图，如果一个运动员为一个俱乐部效力，那么该运动员和俱乐部之间就有一条边，这是一个隶属关系网络的自然例子，这是一种用于社会网络分析的二部图。< ref > { citation
| last1 = Wasserman | first1 = Stanley
| last1 = Wasserman | first1 = Stanley
1 = Wasserman | first1 = Stanley
| author-link1= Stanley Wasserman
| author-link1= Stanley Wasserman
1 = Stanley Wasserman
| last2 = Faust | first2 = Katherine
| last2 = Faust | first2 = Katherine
| last2 = Faust | first2 = Katherine
| isbn = 9780521387071
| isbn = 9780521387071
9780521387071
| pages = 299–302
| pages = 299–302
| 页数 = 299-302
| publisher = Cambridge University Press
| publisher = Cambridge University Press
剑桥大学出版社
| series = Structural Analysis in the Social Sciences
| series = Structural Analysis in the Social Sciences
系列 = 社会科学中的结构分析
| title = Social Network Analysis: Methods and Applications
| title = Social Network Analysis: Methods and Applications
社会网络分析: 方法和应用
| url = https://books.google.com/books?id=CAm2DpIqRUIC&pg=PA299
| url = https://books.google.com/books?id=CAm2DpIqRUIC&pg=PA299
Https://books.google.com/books?id=cam2dpiqruic&pg=pa299
| volume = 8
| volume = 8
8
| year = 1994}}.</ref>
| year = 1994}}.</ref>
| year = 1994} . </ref >
Another example where bipartite graphs appear naturally is in the ([[NP-complete]]) railway optimization problem, in which the input is a schedule of trains and their stops, and the goal is to find a set of train stations as small as possible such that every train visits at least one of the chosen stations. This problem can be modeled as a [[dominating set]] problem in a bipartite graph that has a vertex for each train and each station and an edge for
Another example where bipartite graphs appear naturally is in the (NP-complete) railway optimization problem, in which the input is a schedule of trains and their stops, and the goal is to find a set of train stations as small as possible such that every train visits at least one of the chosen stations. This problem can be modeled as a dominating set problem in a bipartite graph that has a vertex for each train and each station and an edge for
二部图自然出现的另一个例子是在(np 完全)铁路最佳化问题，其中输入的是列车及其停靠时刻表，目标是找到一组尽可能小的火车站，使每列火车至少到达一个选定的车站。这个问题可以被建模为一个二部图中的支配集问题，这个二部图中每列车和每个车站都有一个顶点，每个车站都有一条边
each pair of a station and a train that stops at that station.<ref name=niedermeier2006invitiation>{{cite book|last=Niedermeier|first=Rolf|title=Invitation to Fixed Parameter Algorithms (Oxford Lecture Series in Mathematics and Its Applications)|year=2006|publisher=Oxford|isbn=978-0-19-856607-6|pages=20–21}}</ref>
each pair of a station and a train that stops at that station.
每一对车站和停在那个车站的火车。
A third example is in the academic field of numismatics. Ancient coins are made using two positive impressions of the design (the obverse and reverse). The charts numismatists produce to represent the production of coins are bipartite graphs.<ref name=bracey2012>{{cite article|last=Bracey|first=Robert|title=On the Graphical Interpreation of Herod's Coinage in Judaea and Rome in Coins|year=2012|url=https://www.academia.edu/2078897|pages=65–84}}</ref>
A third example is in the academic field of numismatics. Ancient coins are made using two positive impressions of the design (the obverse and reverse). The charts numismatists produce to represent the production of coins are bipartite graphs.
第三个例子是钱币学领域。古代硬币的制作是基于对设计的正面印象(正面与背面)。钱币收藏家制作的表示硬币产量的图表是二部图。
More abstract examples include the following:
More abstract examples include the following:
更抽象的例子包括:
* Every [[tree (graph theory)|tree]] is bipartite.<ref name="s12"/>
* [[Cycle graph]]s with an even number of vertices are bipartite.<ref name="s12"/>
* Every [[planar graph]] whose [[Glossary of graph theory#Genus|faces]] all have even length is bipartite.<ref>{{citation|first=Alexander|last=Soifer|authorlink=Alexander Soifer|year=2008|title=The Mathematical Coloring Book|title-link= The Mathematical Coloring Book |publisher=Springer-Verlag|isbn=978-0-387-74640-1|pages=136–137}}. This result has sometimes been called the "two color theorem"; Soifer credits it to a famous 1879 paper of [[Alfred Kempe]] containing a false proof of the [[four color theorem]].</ref> Special cases of this are [[grid graph]]s and [[squaregraph]]s, in which every inner face consists of 4 edges and every inner vertex has four or more neighbors.<ref>{{citation|title=Combinatorics and geometry of finite and infinite squaregraphs|first1=H.-J.|last1=Bandelt|first2=V.|last2=Chepoi|first3=D.|last3=Eppstein|author3-link=David Eppstein|arxiv=0905.4537|journal=[[SIAM Journal on Discrete Mathematics]]|volume=24|issue=4|pages=1399–1440|year=2010|doi=10.1137/090760301}}.</ref>
* The [[complete bipartite graph]] on ''m'' and ''n'' vertices, denoted by ''K<sub>n,m</sub>'' is the bipartite graph <math>G = (U, V, E)</math>, where ''U'' and ''V'' are disjoint sets of size ''m'' and ''n'', respectively, and ''E'' connects every vertex in ''U'' with all vertices in ''V''. It follows that ''K<sub>m,n</sub>'' has ''mn'' edges.<ref>{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 11.</ref> Closely related to the complete bipartite graphs are the [[crown graph]]s, formed from complete bipartite graphs by removing the edges of a [[perfect matching]].<ref>{{citation
| last1 = Archdeacon | first1 = D. | author1-link = Dan Archdeacon
| last1 = Archdeacon | first1 = D. | author1-link = Dan Archdeacon
1 = Archdeacon | first1 = d | author1-link = Dan Archdeacon
| last2 = Debowsky | first2 = M.
| last2 = Debowsky | first2 = M.
2 = Debowsky | first2 = m.
| last3 = Dinitz | first3 = J. | author3-link = Jeff Dinitz
| last3 = Dinitz | first3 = J. | author3-link = Jeff Dinitz
3 = j.| author3-link = Jeff Dinitz
| last4 = Gavlas | first4 = H.
| last4 = Gavlas | first4 = H.
4 = Gavlas | first4 = h.
| doi = 10.1016/j.disc.2003.11.021
| doi = 10.1016/j.disc.2003.11.021
| doi = 10.1016/j.disc. 2003.11.021
| issue = 1–3
| issue = 1–3
第一季，第三集
| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
| journal = Discrete Mathematics
2012年3月24日 | 日志 = 离散数学
| pages = 37–43
| pages = 37–43
| 页数 = 37-43
| title = Cycle systems in the complete bipartite graph minus a one-factor
| title = Cycle systems in the complete bipartite graph minus a one-factor
| title = 完全二分图的循环系统减去一个因子
| volume = 284
| volume = 284
284
| year = 2004| doi-access = free
| year = 2004| doi-access = free
2004 | doi-access = free
}}.</ref>
}}.</ref>
} . </ref >
* [[Hypercube graph]]s, [[partial cube]]s, and [[median graph]]s are bipartite. In these graphs, the vertices may be labeled by [[bitvector]]s, in such a way that two vertices are adjacent if and only if the corresponding bitvectors differ in a single position. A bipartition may be formed by separating the vertices whose bitvectors have an even number of ones from the vertices with an odd number of ones. Trees and squaregraphs form examples of median graphs, and every median graph is a partial cube.<ref>{{citation|first=Sergei|last=Ovchinnikov|title=Graphs and Cubes|series=Universitext|publisher=Springer|year=2011}}. See especially Chapter 5, "Partial Cubes", pp. 127–181.</ref>
==Properties==
===Characterization===
Bipartite graphs may be characterized in several different ways:
Bipartite graphs may be characterized in several different ways:
二部图可以用几种不同的方式来表示:
* A graph is bipartite [[if and only if]] it does not contain an [[Cycle (graph theory)|odd cycle]].<ref>{{harvtxt|Asratian|Denley|Häggkvist|1998}}, 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]].</ref>
* A graph is bipartite if and only if it is 2-colorable, (i.e. its [[chromatic number]] is less than or equal to 2).<ref name="adh98-7"/>
* The [[Spectral graph theory|spectrum]] of a graph is symmetric if and only if it's a bipartite graph.<ref>{{citation
| last = Biggs | first = Norman
| last = Biggs | first = Norman
| last = Biggs | first = Norman
| edition = 2nd
| edition = 2nd
2nd
| isbn = 9780521458979
| isbn = 9780521458979
9780521458979
| page = 53
| page = 53
53
| publisher = Cambridge University Press
| publisher = Cambridge University Press
剑桥大学出版社
| series = Cambridge Mathematical Library
| series = Cambridge Mathematical Library
| series = Cambridge Mathematical Library
| title = Algebraic Graph Theory
| title = Algebraic Graph Theory
| title = 代数图论
| url = https://books.google.com/books?id=6TasRmIFOxQC&pg=PA53
| url = https://books.google.com/books?id=6TasRmIFOxQC&pg=PA53
Https://books.google.com/books?id=6tasrmifoxqc&pg=pa53
| year = 1994}}.</ref>
| year = 1994}}.</ref>
| year = 1994} . </ref >
===Kőnig's theorem and perfect graphs===
In bipartite graphs, the size of [[minimum vertex cover]] is equal to the size of the [[maximum matching]]; this is [[Kőnig's theorem (graph theory)|Kőnig's theorem]].<ref>{{cite journal
In bipartite graphs, the size of minimum vertex cover is equal to the size of the maximum matching; this is Kőnig's theorem.<ref>{{cite journal
在二部图中，最小顶点覆盖的大小等于最大匹配的大小，这就是 k-nig 定理。{ cite journal
| author = Kőnig, Dénes
| author = Kőnig, Dénes
作者: k nig，d é nes
| authorlink = Dénes Kőnig
| authorlink = Dénes Kőnig
| authorlink = d é nes k nig
| title = Gráfok és mátrixok
| title = Gráfok és mátrixok
| title = Gráfok és mátrixok
| journal = Matematikai és Fizikai Lapok
| journal = Matematikai és Fizikai Lapok
| journal = Matematikai és Fizikai Lapok
| volume = 38
| volume = 38
38
| year = 1931
| year = 1931
1931年
| pages = 116–119}}.</ref><ref>{{citation
| pages = 116–119}}.</ref><ref>{{citation
116-119} . </ref > < ref > { citation
| last1 = Gross | first1 = Jonathan L.
| last1 = Gross | first1 = Jonathan L.
1 = Gross | first1 = Jonathan l.
| last2 = Yellen | first2 = Jay
| last2 = Yellen | first2 = Jay
2 = Yellen | first2 = Jay
| edition = 2nd
| edition = 2nd
2nd
| isbn = 9781584885054
| isbn = 9781584885054
9781584885054
| page = 568
| page = 568
568
| publisher = CRC Press
| publisher = CRC Press
| publisher = CRC Press
| series = Discrete Mathematics And Its Applications
| series = Discrete Mathematics And Its Applications
系列 = 离散数学及其应用
| title = Graph Theory and Its Applications
| title = Graph Theory and Its Applications
| title = 图论及其应用
| url = https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA568
| url = https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA568
Https://books.google.com/books?id=-7q_pogh-2cc&pg=pa568
| year = 2005}}.</ref> An alternative and equivalent form of this theorem is that the size of the [[maximum independent set]] plus the size of the maximum matching is equal to the number of vertices.
| year = 2005}}.</ref> An alternative and equivalent form of this theorem is that the size of the maximum independent set plus the size of the maximum matching is equal to the number of vertices.
2005}}.</ref > 这个定理的另一种等价形式是最大独立集的大小加上最大匹配的大小等于顶点的数目。
In any graph without [[isolated vertex|isolated vertices]] the size of the [[minimum edge cover]] plus the size of a maximum matching equals the number of vertices.<ref>{{citation
In any graph without isolated vertices the size of the minimum edge cover plus the size of a maximum matching equals the number of vertices.<ref>{{citation
在任何没有孤立顶点的图中，最小边覆盖的大小加上最大匹配的大小等于顶点的数目。< ref > { citation
| last1 = Chartrand | first1 = Gary
| last1 = Chartrand | first1 = Gary
1 = Chartrand | first1 = Gary
| last2 = Zhang | first2 = Ping
| last2 = Zhang | first2 = Ping
2 = Zhang | first2 = Ping
| isbn = 9780486483689
| isbn = 9780486483689
9780486483689
| pages = 189–190
| pages = 189–190
| 页数 = 189-190
| publisher = Courier Dover Publications
| publisher = Courier Dover Publications
2012年10月21日 | 出版商 = 多佛出版社
| title = A First Course in Graph Theory
| title = A First Course in Graph Theory
图论第一课
| url = https://books.google.com/books?id=ocIr0RHyI8oC&pg=PA189
| url = https://books.google.com/books?id=ocIr0RHyI8oC&pg=PA189
Https://books.google.com/books?id=ocir0rhyi8oc&pg=pa189
| year = 2012}}.</ref> Combining this equality with Kőnig's theorem leads to the facts that, in bipartite graphs, the size of the minimum edge cover is equal to the size of the maximum independent set, and the size of the minimum edge cover plus the size of the minimum vertex cover is equal to the number of vertices.
| year = 2012}}.</ref> Combining this equality with Kőnig's theorem leads to the facts that, in bipartite graphs, the size of the minimum edge cover is equal to the size of the maximum independent set, and the size of the minimum edge cover plus the size of the minimum vertex cover is equal to the number of vertices.
2012}}.</ref > 将这个等式与 k nig 定理结合起来得到这样一个结论: 在二部图中，最小边覆盖的大小等于最大独立集的大小，最小边覆盖的大小加上最小顶点覆盖的大小等于顶点的数目。
Another class of related results concerns [[perfect graph]]s: every bipartite graph, the [[complement (graph theory)|complement]] of every bipartite graph, the [[line graph]] of every bipartite graph, and the complement of the line graph of every bipartite graph, are all perfect. Perfection of bipartite graphs is easy to see (their [[chromatic number]] is two and their [[maximum clique]] size is also two) but perfection of the [[complement (graph theory)|complements]] of bipartite graphs is less trivial, and is another restatement of Kőnig's theorem. This was one of the results that motivated the initial definition of perfect graphs.<ref>{{citation|title=Modern Graph Theory
Another class of related results concerns perfect graphs: every bipartite graph, the complement of every bipartite graph, the line graph of every bipartite graph, and the complement of the line graph of every bipartite graph, are all perfect. Perfection of bipartite graphs is easy to see (their chromatic number is two and their maximum clique size is also two) but perfection of the complements of bipartite graphs is less trivial, and is another restatement of Kőnig's theorem. This was one of the results that motivated the initial definition of perfect graphs.<ref>{{citation|title=Modern Graph Theory
另一类相关结果涉及完美图: 每一个二部图、每一个二部图的补图、每一个二部图的线图以及每一个二部图的线图的补图都是完美的。二部图的完美性是显而易见的(它们的色数是2，它们的最大团大小也是2) ，但二部图的补图的完美性是不那么琐碎的，是对 k nig 定理的另一种重述。这是激发完美图最初定义的结果之一
|volume= 184 |series= Graduate Texts in Mathematics
|volume= 184 |series= Graduate Texts in Mathematics
184 | series = 数学研究生教材
|author=Béla Bollobás|publisher =Springer|year= 1998
|author=Béla Bollobás|publisher =Springer|year= 1998
1998年
|isbn= 9780387984889|url=https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA165|page=165|author-link= Béla Bollobás }}.</ref> Perfection of the complements of line graphs of perfect graphs is yet another restatement of Kőnig's theorem, and perfection of the line graphs themselves is a restatement of an earlier theorem of Kőnig, that every bipartite graph has an [[edge coloring]] using a number of colors equal to its maximum degree.
|isbn= 9780387984889|url=https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA165|page=165|author-link= Béla Bollobás }}.</ref> Perfection of the complements of line graphs of perfect graphs is yet another restatement of Kőnig's theorem, and perfection of the line graphs themselves is a restatement of an earlier theorem of Kőnig, that every bipartite graph has an edge coloring using a number of colors equal to its maximum degree.
9780387984889 | url = https://books.google.com/books?id=sbzksz-1qrwc&pg=pa165|page=165|author-link= · 贝拉 · 博洛巴斯}。完全图的线图的补图的完美性是对 k nig 定理的又一次重申，线图本身的完美性是对 k nig 早期定理的重申，即每个二部图都有一个边着色，其颜色数等于它的最大度。
According to the [[strong perfect graph theorem]], the perfect graphs have a [[forbidden graph characterization]] resembling that of bipartite graphs: a graph is bipartite if and only if it has no odd cycle as a subgraph, and a graph is perfect if and only if it has no odd cycle or its [[complement (graph theory)|complement]] as an [[induced subgraph]]. The bipartite graphs, line graphs of bipartite graphs, and their complements form four out of the five basic classes of perfect graphs used in the proof of the strong perfect graph theorem.<ref>{{citation
According to the strong perfect graph theorem, the perfect graphs have a forbidden graph characterization resembling that of bipartite graphs: a graph is bipartite if and only if it has no odd cycle as a subgraph, and a graph is perfect if and only if it has no odd cycle or its complement as an induced subgraph. The bipartite graphs, line graphs of bipartite graphs, and their complements form four out of the five basic classes of perfect graphs used in the proof of the strong perfect graph theorem.<ref>{{citation
根据完美图问题，完美图有一个类似于二部图的禁止图: 一个图是二部图的当且仅当它作为一个子图没有奇圈，并且一个图是完美的当且仅当它没有奇圈或它作为诱导子图的补图。二部图，二部图的线图，以及它们的补图在完美图问题证明中的5个基本类型的完美图中的4个。< ref > { citation
| last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky
| last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky
1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky
| last2 = Robertson | first2 = Neil | author2-link = Neil Robertson (mathematician)
| last2 = Robertson | first2 = Neil | author2-link = Neil Robertson (mathematician)
| last2 = Robertson | first2 = Neil | author2-link = Neil Robertson (数学家)
| last3 = Seymour | first3 = Paul | author3-link = Paul Seymour (mathematician)
| last3 = Seymour | first3 = Paul | author3-link = Paul Seymour (mathematician)
3 = Seymour | first3 = Paul | author3-link = Paul Seymour (数学家)
| last4 = Thomas | first4 = Robin | author4-link = Robin Thomas (mathematician)
| last4 = Thomas | first4 = Robin | author4-link = Robin Thomas (mathematician)
| last4 = Thomas | first4 = Robin | author4-link = Robin Thomas (数学家)
| doi = 10.4007/annals.2006.164.51
| doi = 10.4007/annals.2006.164.51
2006.164.51
| issue = 1
| issue = 1
1
| journal = [[Annals of Mathematics]]
| journal = Annals of Mathematics
2012年3月24日 | 日志 = 数学纪事
| pages = 51–229
| pages = 51–229
| 页数 = 51-229
| title = The strong perfect graph theorem
| title = The strong perfect graph theorem
纽约完美图问题
| volume = 164
| volume = 164
164
| year = 2006| citeseerx = 10.1.1.111.7265| arxiv = math/0212070}}.</ref>
| year = 2006| citeseerx = 10.1.1.111.7265| arxiv = math/0212070}}.</ref>
2006 | citeseerx = 10.1.1.111.7265 | arxiv = math/0212070}} . </ref >
===Degree===
For a vertex, the number of adjacent vertices is called the [[degree (graph theory)|degree]] of the vertex and is denoted <math>\deg(v)</math>.
For a vertex, the number of adjacent vertices is called the degree of the vertex and is denoted <math>\deg(v)</math>.
对于一个顶点，相邻顶点的数目称为顶点的度数，表示为 < math > deg (v) </math > 。
The ''degree sum formula'' for a bipartite graph states that
The degree sum formula for a bipartite graph states that
二部图的度和公式表明:
:<math>\sum_{v \in V} \deg(v) = \sum_{u \in U} \deg(u) = |E|\, .</math>
<math>\sum_{v \in V} \deg(v) = \sum_{u \in U} \deg(u) = |E|\, .</math>
<math>\sum_{v \in V} \deg(v) = \sum_{u \in U} \deg(u) = |E|\, .</math>
The degree sequence of a bipartite graph is the pair of lists each containing the degrees of the two parts <math>U</math> and <math>V</math>. For example, the complete bipartite graph ''K''<sub>3,5</sub> has degree sequence <math>(5,5,5),(3,3,3,3,3)</math>. Isomorphic bipartite graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a bipartite graph; in some cases, non-isomorphic bipartite graphs may have the same degree sequence.
The degree sequence of a bipartite graph is the pair of lists each containing the degrees of the two parts <math>U</math> and <math>V</math>. For example, the complete bipartite graph K<sub>3,5</sub> has degree sequence <math>(5,5,5),(3,3,3,3,3)</math>. Isomorphic bipartite graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a bipartite graph; in some cases, non-isomorphic bipartite graphs may have the same degree sequence.
二部图的度序列是一对列表，每一个列表包含两部分的度。例如，完全二分图 k < sub > 3,5 </sub > 具有度序列 < math > (5,5,5) ，(3,3,3,3,3,3) </math > 。同构二部图具有相同的度序列。然而，度序列通常不能唯一地识别二部图，在某些情况下，不同构的二部图可能具有相同的度序列。
The [[bipartite realization problem]] is the problem of finding a simple bipartite graph with the degree sequence being two given lists of natural numbers. (Trailing zeros may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the digraph.)
The bipartite realization problem is the problem of finding a simple bipartite graph with the degree sequence being two given lists of natural numbers. (Trailing zeros may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the digraph.)
二部实现问题是寻找度序列为两个给定自然数列表的简单二部图的问题。(尾随零可能被忽略，因为它们通过向有向图添加适当数量的孤立顶点来实现。)
===Relation to hypergraphs and directed graphs===
The [[Adjacency matrix of a bipartite graph|biadjacency matrix]] of a bipartite graph <math>(U,V,E)</math> is a [[(0,1) matrix]] of size <math>|U|\times|V|</math> that has a one for each pair of adjacent vertices and a zero for nonadjacent vertices.<ref>{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 17.</ref> Biadjacency matrices may be used to describe equivalences between bipartite graphs, hypergraphs, and directed graphs.
The biadjacency matrix of a bipartite graph <math>(U,V,E)</math> is a (0,1) matrix of size <math>|U|\times|V|</math> that has a one for each pair of adjacent vertices and a zero for nonadjacent vertices. Biadjacency matrices may be used to describe equivalences between bipartite graphs, hypergraphs, and directed graphs.
二部图的二邻接矩阵 < math > (u，v，e) </math > 是一个大小为 < math > | u | times | v | </math > 的(0,1)矩阵，每对相邻顶点有一个1，对不相邻顶点有一个0。双邻接矩阵可以用来描述二部图、超图和有向图之间的等价关系。
A [[hypergraph]] is a combinatorial structure that, like an undirected graph, has vertices and edges, but in which the edges may be arbitrary sets of vertices rather than having to have exactly two endpoints. A bipartite graph <math>(U,V,E)</math> may be used to model a hypergraph in which {{mvar|U}} is the set of vertices of the hypergraph, {{mvar|V}} is the set of hyperedges, and {{mvar|E}} contains an edge from a hypergraph vertex {{mvar|v}} to a hypergraph edge {{mvar|e}} exactly when {{mvar|v}} is one of the endpoints of {{mvar|e}}. Under this correspondence, the biadjacency matrices of bipartite graphs are exactly the [[incidence matrix|incidence matrices]] of the corresponding hypergraphs. As a special case of this correspondence between bipartite graphs and hypergraphs, any [[multigraph]] (a graph in which there may be two or more edges between the same two vertices) may be interpreted as a hypergraph in which some hyperedges have equal sets of endpoints, and represented by a bipartite graph that does not have multiple adjacencies and in which the vertices on one side of the bipartition all have [[degree (graph theory)|degree]] two.<ref>{{SpringerEOM|title=Hypergraph|author=A. A. Sapozhenko}}</ref>
A hypergraph is a combinatorial structure that, like an undirected graph, has vertices and edges, but in which the edges may be arbitrary sets of vertices rather than having to have exactly two endpoints. A bipartite graph <math>(U,V,E)</math> may be used to model a hypergraph in which is the set of vertices of the hypergraph, is the set of hyperedges, and contains an edge from a hypergraph vertex to a hypergraph edge exactly when is one of the endpoints of . Under this correspondence, the biadjacency matrices of bipartite graphs are exactly the incidence matrices of the corresponding hypergraphs. As a special case of this correspondence between bipartite graphs and hypergraphs, any multigraph (a graph in which there may be two or more edges between the same two vertices) may be interpreted as a hypergraph in which some hyperedges have equal sets of endpoints, and represented by a bipartite graph that does not have multiple adjacencies and in which the vertices on one side of the bipartition all have degree two.
一个超图是一个组合结构，就像一个无向图，有顶点和边，但其中的边可能是任意的顶点集，而不是必须有正好两个端点。二部图 < math > (u，v，e) </math > 可以用来建模一个超图，其中超图的顶点集是超边的集合，它包含一条从超图顶点到超图边的边，而这条边恰好是超图的端点之一。在此对应关系下，二部图的二邻接矩阵正好是对应超图的关联矩阵。作为二部图和超图之间对应关系的一种特殊情形，任何多重图(在同一两个顶点之间可能有两条或更多条边的图)都可以被解释为一个超图，其中一些超边具有相等的端点集，并由一个不具有多重邻接的二部图表示，在这个超图中，二部分一边的顶点都具有二次。
A similar reinterpretation of adjacency matrices may be used to show a one-to-one correspondence between [[directed graph]]s (on a given number of labeled vertices, allowing self-loops) and balanced bipartite graphs, with the same number of vertices on both sides of the bipartition. For, the adjacency matrix of a directed graph with {{mvar|n}} vertices can be any [[(0,1) matrix]] of size <math>n\times n</math>, which can then be reinterpreted as the adjacency matrix of a bipartite graph with {{mvar|n}} vertices on each side of its bipartition.<ref>{{citation
A similar reinterpretation of adjacency matrices may be used to show a one-to-one correspondence between directed graphs (on a given number of labeled vertices, allowing self-loops) and balanced bipartite graphs, with the same number of vertices on both sides of the bipartition. For, the adjacency matrix of a directed graph with vertices can be any (0,1) matrix of size <math>n\times n</math>, which can then be reinterpreted as the adjacency matrix of a bipartite graph with vertices on each side of its bipartition.<ref>{{citation
一个类似的邻接矩阵翻唱可以用来显示有向图(在给定数量的标号顶点上，允许自循环)和平衡二部图之间的双射，二部图的两边顶点数相同。因为，顶点有向图的邻接矩阵可以是任意大小的(0,1)矩阵 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n。< ref > { citation
| last1 = Brualdi | first1 = Richard A.
| last1 = Brualdi | first1 = Richard A.
1 = Brualdi | first1 = Richard a.
| last2 = Harary | first2 = Frank | author2-link = Frank Harary
| last2 = Harary | first2 = Frank | author2-link = Frank Harary
2 = Harary | first2 = Frank | author2-link = Frank Harary
| last3 = Miller | first3 = Zevi
| last3 = Miller | first3 = Zevi
3 = Miller | first3 = Zevi
| doi = 10.1002/jgt.3190040107
| doi = 10.1002/jgt.3190040107
| doi = 10.1002/jgt. 3190040107
| mr = 558453
| mr = 558453
558453先生
| issue = 1
| issue = 1
1
| journal = Journal of Graph Theory
| journal = Journal of Graph Theory
| Journal = Journal of Graph Theory
| pages = 51–73
| pages = 51–73
| 页数 = 51-73
| title = Bigraphs versus digraphs via matrices
| title = Bigraphs versus digraphs via matrices
| title = Bigraphs vs 通过矩阵的有向图
| volume = 4
| volume = 4
4
| year = 1980}}. Brualdi et al. credit the idea for this equivalence to {{citation
| year = 1980}}. Brualdi et al. credit the idea for this equivalence to {{citation
1980}}.布鲁迪等人。把这个等价的概念归功于{ citation
| doi = 10.4153/CJM-1958-052-0
| doi = 10.4153/CJM-1958-052-0
| doi = 10.4153/CJM-1958-052-0
| last1 = Dulmage | first1 = A. L.
| last1 = Dulmage | first1 = A. L.
1 = Dulmage | first1 = A.l.
| last2 = Mendelsohn | first2 = N. S. | author2-link = Nathan Mendelsohn
| last2 = Mendelsohn | first2 = N. S. | author2-link = Nathan Mendelsohn
2 = Mendelsohn | first2 = n. s. | author2-link = Nathan Mendelsohn
| mr = 0097069
| mr = 0097069
0097069先生
| journal = Canadian Journal of Mathematics
| journal = Canadian Journal of Mathematics
加拿大数学杂志
| pages = 517–534
| pages = 517–534
| 页数 = 517-534
| title = Coverings of bipartite graphs
| title = Coverings of bipartite graphs
| title = 二部图的覆盖
| volume = 10
| volume = 10
10
| year = 1958}}.</ref> In this construction, the bipartite graph is the [[bipartite double cover]] of the directed graph.
| year = 1958}}.</ref> In this construction, the bipartite graph is the bipartite double cover of the directed graph.
| year = 1958}。 </ref > 在这个结构中，二部图是有向图的二部双覆盖。
==Algorithms==
===Testing bipartiteness===
It is possible to test whether a graph is bipartite, and to return either a two-coloring (if it is bipartite) or an odd cycle (if it is not) in [[linear time]], using [[depth-first search]]. The main idea is to assign to each vertex the color that differs from the color of its parent in the depth-first search forest, assigning colors in a [[preorder traversal]] of the depth-first-search forest. This will necessarily provide a two-coloring of the [[spanning forest]] consisting of the edges connecting vertices to their parents, but it may not properly color some of the non-forest edges. In a depth-first search forest, one of the two endpoints of every non-forest edge is an ancestor of the other endpoint, and when the depth first search discovers an edge of this type it should check that these two vertices have different colors. If they do not, then the path in the forest from ancestor to descendant, together with the miscolored edge, form an odd cycle, which is returned from the algorithm together with the result that the graph is not bipartite. However, if the algorithm terminates without detecting an odd cycle of this type, then every edge must be properly colored, and the algorithm returns the coloring together with the result that the graph is bipartite.<ref>{{citation
It is possible to test whether a graph is bipartite, and to return either a two-coloring (if it is bipartite) or an odd cycle (if it is not) in linear time, using depth-first search. The main idea is to assign to each vertex the color that differs from the color of its parent in the depth-first search forest, assigning colors in a preorder traversal of the depth-first-search forest. This will necessarily provide a two-coloring of the spanning forest consisting of the edges connecting vertices to their parents, but it may not properly color some of the non-forest edges. In a depth-first search forest, one of the two endpoints of every non-forest edge is an ancestor of the other endpoint, and when the depth first search discovers an edge of this type it should check that these two vertices have different colors. If they do not, then the path in the forest from ancestor to descendant, together with the miscolored edge, form an odd cycle, which is returned from the algorithm together with the result that the graph is not bipartite. However, if the algorithm terminates without detecting an odd cycle of this type, then every edge must be properly colored, and the algorithm returns the coloring together with the result that the graph is bipartite.<ref>{{citation
我们可以用深度优先搜索来检验一个图是否是二部图，并且可以在线性时间内返回一个双染色(如果是二部图)或一个奇循环(如果不是)。其主要思想是在深度优先搜索森林中为每个顶点分配与其父顶点颜色不同的颜色，在深度优先搜索森林的前序遍历中分配颜色。这将必然提供一个双着色的跨森林组成的边连接顶点到他们的父母，但它可能不适当的颜色一些非森林边。在深度优先搜索森林中，每个非森林边缘的两个端点中的一个是另一个端点的祖先，当深度首次搜索发现这种类型的边缘时，应该检查这两个顶点是否有不同的颜色。如果不是这样，那么森林中从祖先到后代的路径与错误着色的边一起形成一个奇循环，这个奇循环由算法返回，并得到图不是二部图的结果。然而，如果算法在没有检测到奇圈的情况下终止，那么每条边都必须正确着色，并且算法返回着色结果和图是二部图的结果。< ref > { citation
| last = Sedgewick | first = Robert | author-link = Robert Sedgewick (computer scientist)
| last = Sedgewick | first = Robert | author-link = Robert Sedgewick (computer scientist)
罗伯特·塞奇威克: 计算机科学家
| edition = 3rd
| edition = 3rd
3 rd
| pages = 109–111
| pages = 109–111
| pages = 109-111
| publisher = Addison Wesley
| publisher = Addison Wesley
艾迪生 · 韦斯利
| title = Algorithms in Java, Part 5: Graph Algorithms
| title = Algorithms in Java, Part 5: Graph Algorithms
Java 中的算法，第五部分: 图算法
| year = 2004}}.</ref>
| year = 2004}}.</ref>
| year = 2004} . </ref >
Alternatively, a similar procedure may be used with [[breadth-first search]] in place of depth-first search. Again, each node is given the opposite color to its parent in the search forest, in breadth-first order. If, when a vertex is colored, there exists an edge connecting it to a previously-colored vertex with the same color, then this edge together with the paths in the breadth-first search forest connecting its two endpoints to their [[lowest common ancestor]] forms an odd cycle. If the algorithm terminates without finding an odd cycle in this way, then it must have found a proper coloring, and can safely conclude that the graph is bipartite.<ref>{{citation
Alternatively, a similar procedure may be used with breadth-first search in place of depth-first search. Again, each node is given the opposite color to its parent in the search forest, in breadth-first order. If, when a vertex is colored, there exists an edge connecting it to a previously-colored vertex with the same color, then this edge together with the paths in the breadth-first search forest connecting its two endpoints to their lowest common ancestor forms an odd cycle. If the algorithm terminates without finding an odd cycle in this way, then it must have found a proper coloring, and can safely conclude that the graph is bipartite.<ref>{{citation
或者，类似的方法也可以用广度优先搜索替代深度优先搜索。同样，在搜索林中，每个节点以与其父节点相反的颜色按广度优先的顺序给出。如果，当一个顶点着色时，存在一条边将其与先前着色的顶点用同样的颜色连接起来，那么这条边与广度优先搜索森林中连接其两个端点与它们的最近公共祖先的路径一起形成一个奇怪的循环。如果算法以这种方式终止而不发现奇循环，那么它一定已经发现了一个适当的着色，并且可以安全地得出图是二部图的结论。< ref > { citation
| last1 = Kleinberg | first1 = Jon | author1-link = Jon Kleinberg
| last1 = Kleinberg | first1 = Jon | author1-link = Jon Kleinberg
1 = Kleinberg | first1 = Jon | author1-link = Jon Kleinberg
| last2 = Tardos | first2 = Éva | author2-link = Éva Tardos
| last2 = Tardos | first2 = Éva | author2-link = Éva Tardos
| last2 = Tardos | first2 = Éva | author2-link = Éva Tardos
| pages = 94–97
| pages = 94–97
94-97
| publisher = Addison Wesley
| publisher = Addison Wesley
艾迪生 · 韦斯利
| title = Algorithm Design
| title = Algorithm Design
算法设计
| year = 2006}}.</ref>
| year = 2006}}.</ref>
| year = 2006} . </ref >
For the [[intersection graph]]s of <math>n</math> [[line segment]]s or other simple shapes in the [[Euclidean plane]], it is possible to test whether the graph is bipartite and return either a two-coloring or an odd cycle in time <math>O(n\log n)</math>, even though the graph itself may have up to <math>O(n^2)</math> edges.<ref>{{citation
For the intersection graphs of <math>n</math> line segments or other simple shapes in the Euclidean plane, it is possible to test whether the graph is bipartite and return either a two-coloring or an odd cycle in time <math>O(n\log n)</math>, even though the graph itself may have up to <math>O(n^2)</math> edges.<ref>{{citation
对于 < math > n </math > 线段的交叉图或欧几里德平面上其他简单形状，即使图本身可能有 < math > o (n ^ 2) </math > 边，也可以检验图是否为二部图，并在时间上返回一个双染色或奇循环。< ref > { citation
| last = Eppstein | first = David | author-link = David Eppstein
| last = Eppstein | first = David | author-link = David Eppstein
最后 = Eppstein | 第一 = David | author-link = David Eppstein
| arxiv = cs.CG/0307023
| arxiv = cs.CG/0307023
| arxiv = cs.CG/0307023
| doi = 10.1145/1497290.1497291
| doi = 10.1145/1497290.1497291
10.1145/1497290.1497291
| issue = 2
| issue = 2
2
| journal = ACM Transactions on Algorithms
| journal = ACM Transactions on Algorithms
关于算法的 ACM 汇刊
| mr = 2561751
| mr = 2561751
2561751先生
| page = Art. 15
| page = Art. 15
| page = Art.15
| title = Testing bipartiteness of geometric intersection graphs
| title = Testing bipartiteness of geometric intersection graphs
| title = 几何交图的测试双分性
| volume = 5
| volume = 5
5
| year = 2009}}.</ref>
| year = 2009}}.</ref>
2009} . </ref >
===Odd cycle transversal===
{{main|Odd cycle transversal}}
[[File:Odd Cycle Transversal of size 2.png|thumb|A graph with an odd cycle transversal of size 2: removing the two blue bottom vertices leaves a bipartite graph.]]
A graph with an odd cycle transversal of size 2: removing the two blue bottom vertices leaves a bipartite graph.
一个具有大小为2的奇圈横截的图: 去掉两个蓝色底顶点后得到一个二部图。
[[Odd cycle transversal]] is an [[NP-complete]] [[algorithm]]ic problem that asks, given a graph ''G'' = (''V'',''E'') and a number ''k'', whether there exists a set of ''k'' vertices whose removal from ''G'' would cause the resulting graph to be bipartite.<ref name=yannakakis1978node>{{citation
Odd cycle transversal is an NP-complete algorithmic problem that asks, given a graph G = (V,E) and a number k, whether there exists a set of k vertices whose removal from G would cause the resulting graph to be bipartite.<ref name=yannakakis1978node>{{citation
奇圈横截是一个 np 完全计算问题，它要求给定一个图 g = (v，e)和一个数 k，是否存在一组 k 点，从 g 中去掉这些点会使得得到的图是二部图。1978 node > { citation
| last = Yannakakis | first = Mihalis | author-link = Mihalis Yannakakis
| last = Yannakakis | first = Mihalis | author-link = Mihalis Yannakakis
最后 = yannakis | first = Mihalis | author-link = Mihalis yannakis
| contribution = Node-and edge-deletion NP-complete problems
| contribution = Node-and edge-deletion NP-complete problems
| 贡献 = 节点和边删除 np 完全问题
| doi = 10.1145/800133.804355
| doi = 10.1145/800133.804355
| doi = 10.1145/800133.804355
| pages = 253–264
| pages = 253–264
| 页 = 253-264
| title = Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78)
| title = Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78)
| title = 第十届 ACM 计算理论研讨会论文集(STOC’78)
| year = 1978| title-link = Symposium on Theory of Computing }}</ref> The problem is [[Parameterized complexity|fixed-parameter tractable]], meaning that there is an algorithm whose running time can be bounded by a polynomial function of the size of the graph multiplied by a larger function of ''k''.<ref name=reed2004finding>{{citation
| year = 1978| title-link = Symposium on Theory of Computing }}</ref> The problem is fixed-parameter tractable, meaning that there is an algorithm whose running time can be bounded by a polynomial function of the size of the graph multiplied by a larger function of k.<ref name=reed2004finding>{{citation
这个问题是固定参数可处理的，这意味着有一个算法，其运行时间可以由图的大小乘以一个更大的函数 k 的多项式函数来限定
| last1 = Reed | first1 = Bruce | author1-link = Bruce Reed (mathematician)
| last1 = Reed | first1 = Bruce | author1-link = Bruce Reed (mathematician)
1 = Reed | first1 = Bruce | author1-link = Bruce Reed (数学家)
| last2 = Smith | first2 = Kaleigh
| last2 = Smith | first2 = Kaleigh
2 = Smith | first2 = Kaleigh
| last3 = Vetta | first3 = Adrian
| last3 = Vetta | first3 = Adrian
3 = Vetta | first3 = Adrian
| doi = 10.1016/j.orl.2003.10.009
| doi = 10.1016/j.orl.2003.10.009
10.1016/j.orl. 2003.10.009
| issue = 4
| issue = 4
第四期
| journal = Operations Research Letters
| journal = Operations Research Letters
| 日志 = 运筹学快报
| mr = 2057781
| mr = 2057781
2057781先生
| pages = 299–301
| pages = 299–301
| 页数 = 299-301
| title = Finding odd cycle transversals
| title = Finding odd cycle transversals
| title = 查找奇怪的循环横截
| volume = 32
| volume = 32
32
| year = 2004| citeseerx = 10.1.1.112.6357}}.</ref> The name ''odd cycle transversal'' comes from the fact that a graph is bipartite if and only if it has no odd [[Cycle (graph theory)|cycles]]. Hence, to delete vertices from a graph in order to obtain a bipartite graph, one needs to "hit all odd cycle", or find a so-called odd cycle [[Transversal (combinatorics)|transversal]] set. In the illustration, every odd cycle in the graph contains the blue (the bottommost) vertices, so removing those vertices kills all odd cycles and leaves a bipartite graph.
| year = 2004| citeseerx = 10.1.1.112.6357}}.</ref> The name odd cycle transversal comes from the fact that a graph is bipartite if and only if it has no odd cycles. Hence, to delete vertices from a graph in order to obtain a bipartite graph, one needs to "hit all odd cycle", or find a so-called odd cycle transversal set. In the illustration, every odd cycle in the graph contains the blue (the bottommost) vertices, so removing those vertices kills all odd cycles and leaves a bipartite graph.
10.1.1.112.6357}.名称奇圈横截来自于这样一个事实: 一个图是二部图当且仅当它没有奇圈。因此，要从图中删除顶点以得到二部图，就需要“遍历所有奇圈” ，或者找到一个所谓的奇圈横截集。在图中，图中的每个奇数圈都包含蓝色(最底部的)顶点，因此去掉这些顶点会杀死所有奇数圈并留下一个二部图。
The ''edge bipartization'' problem is the algorithmic problem of deleting as few edges as possible to make a graph bipartite and is also an important problem in graph modification algorithmics. This problem is also [[fixed-parameter tractable]], and can be solved in time ''O''(2<sup>''k''</sup> ''m''<sup>2</sup>),<ref name=guo2006compression>{{citation
The edge bipartization problem is the algorithmic problem of deleting as few edges as possible to make a graph bipartite and is also an important problem in graph modification algorithmics. This problem is also fixed-parameter tractable, and can be solved in time O(2<sup>k</sup> m<sup>2</sup>),<ref name=guo2006compression>{{citation
边双分问题是为了构造一个二部图而删除尽可能少的边的计算问题问题，也是图修正算法中的一个重要问题。这个问题也是固定参数易于处理的，可以在 o (2 < sup > k </sup > m < sup > 2 </sup >) ，< ref name = guo2006compression > { citation > 中解决
| last1 = Guo | first1 = Jiong
| last1 = Guo | first1 = Jiong
1 = Guo | first1 = Jiong
| last2 = Gramm | first2 = Jens
| last2 = Gramm | first2 = Jens
2 = Gramm | first2 = Jens
| last3 = Hüffner | first3 = Falk
| last3 = Hüffner | first3 = Falk
| last3 = Hüffner | first3 = Falk
| last4 = Niedermeier | first4 = Rolf
| last4 = Niedermeier | first4 = Rolf
4 = Rolf
| last5 = Wernicke | first5 = Sebastian
| last5 = Wernicke | first5 = Sebastian
5 = Wernicke | first5 = Sebastian
| doi = 10.1016/j.jcss.2006.02.001
| doi = 10.1016/j.jcss.2006.02.001
| doi = 10.1016/jcss. 2006.02.001
| journal = Journal of Computer and System Sciences
| journal = Journal of Computer and System Sciences
计算机与系统科学杂志
| volume = 72
| volume = 72
72
| issue = 8
| issue = 8
第8期
| pages = 1386–1396
| pages = 1386–1396
| 页数 = 1386-1396
| title = Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
| title = Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
| title = 基于压缩的反馈顶点集和边双分离的固定参数算法
| year = 2006}}</ref> where ''k'' is the number of edges to delete and ''m'' is the number of edges in the input graph.
| year = 2006}}</ref> where k is the number of edges to delete and m is the number of edges in the input graph.
| year = 2006} </ref > 其中 k 是要删除的边数，m 是输入图中的边数。
===Matching===
{{main|Matching (graph theory)}}
A [[Matching (graph theory)|matching]] in a graph is a subset of its edges, no two of which share an endpoint. [[Polynomial time]] algorithms are known for many algorithmic problems on matchings, including [[maximum matching]] (finding a matching that uses as many edges as possible), [[maximum weight matching]], and [[stable marriage]].<ref>{{citation
A matching in a graph is a subset of its edges, no two of which share an endpoint. Polynomial time algorithms are known for many algorithmic problems on matchings, including maximum matching (finding a matching that uses as many edges as possible), maximum weight matching, and stable marriage.<ref>{{citation
图中的匹配是其边的一个子集，没有两条边共享一个端点。多项式时间算法已知的许多算法问题的匹配，包括最大匹配(寻找匹配，使用尽可能多的边) ，最大权重匹配，和稳定的婚姻。< ref > { citation
| last1 = Ahuja | first1 = Ravindra K.
| last1 = Ahuja | first1 = Ravindra K.
1 = Ahuja | first1 = Ravindra k.
| last2 = Magnanti | first2 = Thomas L.
| last2 = Magnanti | first2 = Thomas L.
2 = Magnanti | first2 = Thomas l.
| last3 = Orlin | first3 = James B.
| last3 = Orlin | first3 = James B.
3 = Orlin | first3 = James b.
| contribution = 12. Assignments and Matchings
| contribution = 12. Assignments and Matchings
12.作业和匹配
| pages = 461–509
| pages = 461–509
| 页数 = 461-509
| publisher = Prentice Hall
| publisher = Prentice Hall
普伦蒂斯 · 霍尔
| title = Network Flows: Theory, Algorithms, and Applications
| title = Network Flows: Theory, Algorithms, and Applications
| title = 网络流: 理论、算法和应用
| year = 1993}}.</ref> In many cases, matching problems are simpler to solve on bipartite graphs than on non-bipartite graphs,<ref>{{harvtxt|Ahuja|Magnanti|Orlin|1993}}, p. 463: "Nonbipartite matching problems are more difficult to solve because they do not reduce to standard network flow problems."</ref> and many matching algorithms such as the [[Hopcroft–Karp algorithm]] for maximum cardinality matching<ref>{{citation|first1=John E.|last1=Hopcroft|author1-link=John Hopcroft|first2=Richard M.|last2=Karp|author2-link=Richard Karp|title=An ''n''<sup>5/2</sup> algorithm for maximum matchings in bipartite graphs|journal=SIAM Journal on Computing|volume=2|issue=4|pages=225–231|year=1973|doi=10.1137/0202019}}.</ref> work correctly only on bipartite inputs.
| year = 1993}}.</ref> In many cases, matching problems are simpler to solve on bipartite graphs than on non-bipartite graphs, and many matching algorithms such as the Hopcroft–Karp algorithm for maximum cardinality matching work correctly only on bipartite inputs.
1993}}.在许多情况下，二部图上的匹配问题比非二部图上的匹配问题更容易解决，而且许多匹配算法，如最大基数匹配的霍普克罗夫特-卡普算法，只能在二部图输入上正确工作。
As a simple example, suppose that a set <math>P</math> of people are all seeking jobs from among a set of <math>J</math> jobs, with not all people suitable for all jobs. This situation can be modeled as a bipartite graph <math>(P,J,E)</math> where an edge connects each job-seeker with each suitable job.<ref>{{harvtxt|Ahuja|Magnanti|Orlin|1993}}, Application 12.1 Bipartite Personnel Assignment, pp. 463–464.</ref> A [[perfect matching]] describes a way of simultaneously satisfying all job-seekers and filling all jobs; [[Hall's marriage theorem]] provides a characterization of the bipartite graphs which allow perfect matchings. The [[National Resident Matching Program]] applies graph matching methods to solve this problem for [[Medical education in the United States|U.S. medical student]] job-seekers and [[Residency (medicine)|hospital residency]] jobs.<ref>{{citation
As a simple example, suppose that a set <math>P</math> of people are all seeking jobs from among a set of <math>J</math> jobs, with not all people suitable for all jobs. This situation can be modeled as a bipartite graph <math>(P,J,E)</math> where an edge connects each job-seeker with each suitable job. A perfect matching describes a way of simultaneously satisfying all job-seekers and filling all jobs; Hall's marriage theorem provides a characterization of the bipartite graphs which allow perfect matchings. The National Resident Matching Program applies graph matching methods to solve this problem for U.S. medical student job-seekers and hospital residency jobs.<ref>{{citation
举个简单的例子，假设一组人都在一组工作中找工作，并不是所有的人都适合所有的工作。这种情况可以模拟为一个二部图 < math > (p，j，e) </math > 其中一条边连接每个求职者和每个合适的工作。完美匹配描述了一种同时满足所有求职者和填补所有工作岗位的方法; 霍尔的婚姻定理提供了二部图的角色塑造，这些图允许完美匹配。国家住院医生匹配计划(National Resident Matching Program)应用图形匹配方法来解决美国医学生求职者和医院住院医生工作的这一问题。< ref > { citation
|last = Robinson
|last = Robinson
| last = Robinson
|first = Sara
|first = Sara
第一名: 莎拉
|date = April 2003
|date = April 2003
| date = April 2003
|issue = 3
|issue = 3
第三期
|journal = SIAM News
|journal = SIAM News
日志 = SIAM 新闻
|page = 36
|page = 36
36
|title = Are Medical Students Meeting Their (Best Possible) Match?
|title = Are Medical Students Meeting Their (Best Possible) Match?
| title = 医学生是否达到了他们的(最佳可能的)匹配？
|url = http://www.siam.org/pdf/news/305.pdf
|url = http://www.siam.org/pdf/news/305.pdf
Http://www.siam.org/pdf/news/305.pdf
|access-date = 2012-08-27
|access-date = 2012-08-27
| access-date = 2012-08-27
|archive-url = https://web.archive.org/web/20161118115832/http://www.siam.org/pdf/news/305.pdf
|archive-url = https://web.archive.org/web/20161118115832/http://www.siam.org/pdf/news/305.pdf
| archive-url = https://web.archive.org/web/20161118115832/http://www.siam.org/pdf/news/305.pdf
|archive-date = 2016-11-18
|archive-date = 2016-11-18
| archive-date = 2016-11-18
|url-status = dead
|url-status = dead
地位 = 死亡
}}.</ref>
}}.</ref>
} . </ref >
The [[Dulmage–Mendelsohn decomposition]] is a structural decomposition of bipartite graphs that is useful in finding maximum matchings.<ref>{{harvtxt|Dulmage|Mendelsohn|1958}}.</ref>
The Dulmage–Mendelsohn decomposition is a structural decomposition of bipartite graphs that is useful in finding maximum matchings.
Dulmage-Mendelsohn 分解是二部图的一种结构分解，它有助于找到最大匹配。
==Additional applications==
Bipartite graphs are extensively used in modern [[coding theory]], especially to decode [[codeword]]s received from the channel. [[Factor graph]]s and [[Tanner graph]]s are examples of this. A Tanner graph is a bipartite graph in which the vertices on one side of the bipartition represent digits of a codeword, and the vertices on the other side represent combinations of digits that are expected to sum to zero in a codeword without errors.<ref>{{citation
Bipartite graphs are extensively used in modern coding theory, especially to decode codewords received from the channel. Factor graphs and Tanner graphs are examples of this. A Tanner graph is a bipartite graph in which the vertices on one side of the bipartition represent digits of a codeword, and the vertices on the other side represent combinations of digits that are expected to sum to zero in a codeword without errors.<ref>{{citation
二部图在现代编码理论中得到了广泛的应用，特别是在信道码字的译码方面。因子图和坦纳图就是这方面的例子。图是一个二部图，其中一边的顶点代表一个码字的数字，另一边的顶点代表一个码字中期望和为零的数字组合。< ref > { citation
| last = Moon | first = Todd K.
| last = Moon | first = Todd K.
| last = Moon | first = Todd k.
| isbn = 9780471648000
| isbn = 9780471648000
9780471648000
| page = 638
| page = 638
638
| publisher = John Wiley & Sons
| publisher = John Wiley & Sons
2012年3月24日 | publisher = 约翰威立
| title = Error Correction Coding: Mathematical Methods and Algorithms
| title = Error Correction Coding: Mathematical Methods and Algorithms
| title = 纠错编码: 数学方法和算法
| url = https://books.google.com/books?id=adxb8CRx5vQC&pg=PA638
| url = https://books.google.com/books?id=adxb8CRx5vQC&pg=PA638
Https://books.google.com/books?id=adxb8crx5vqc&pg=pa638
| year = 2005}}.</ref> A factor graph is a closely related [[belief network]] used for probabilistic decoding of [[LDPC]] and [[turbo codes]].<ref>{{harvtxt|Moon|2005}}, p. 686.</ref>
| year = 2005}}.</ref> A factor graph is a closely related belief network used for probabilistic decoding of LDPC and turbo codes.
2005}}.因子图是一种密切相关的置信网络，用于 LDPC 码和 turbo 码的概率译码。
In computer science, a [[Petri net]] is a mathematical modeling tool used in analysis and simulations of concurrent systems. A system is modeled as a bipartite directed graph with two sets of nodes: A set of "place" nodes that contain resources, and a set of "event" nodes which generate and/or consume resources. There are additional constraints on the nodes and edges that constrain the behavior of the system. Petri nets utilize the properties of bipartite directed graphs and other properties to allow mathematical proofs of the behavior of systems while also allowing easy implementation of simulations of the system.<ref>{{citation
In computer science, a Petri net is a mathematical modeling tool used in analysis and simulations of concurrent systems. A system is modeled as a bipartite directed graph with two sets of nodes: A set of "place" nodes that contain resources, and a set of "event" nodes which generate and/or consume resources. There are additional constraints on the nodes and edges that constrain the behavior of the system. Petri nets utilize the properties of bipartite directed graphs and other properties to allow mathematical proofs of the behavior of systems while also allowing easy implementation of simulations of the system.<ref>{{citation
在计算机科学中，Petri 网是一种用于并发系统分析和仿真的数学建模工具。一个系统被建模为由两组节点组成的二分有向图: 一组包含资源的“位置”节点和一组生成和/或消耗资源的“事件”节点。在节点和边上有额外的约束，约束系统的行为。Petri 网利用二部有向图的性质和其他性质，允许对系统的行为进行数学证明，同时也允许容易地实现系统的模拟。< ref > { citation
| last1 = Cassandras | first1 = Christos G.
| last1 = Cassandras | first1 = Christos G.
1 = Cassandras | first1 = Christos g.
| last2 = Lafortune | first2 = Stephane
| last2 = Lafortune | first2 = Stephane
2 = Lafortune | first2 = Stephane
| edition = 2nd
| edition = 2nd
2nd
| isbn = 9780387333328
| isbn = 9780387333328
9780387333328
| page = 224
| page = 224
224
| publisher = Springer
| publisher = Springer
| publisher = Springer
| title = Introduction to Discrete Event Systems
| title = Introduction to Discrete Event Systems
| title = 离散事件系统导论
| url = https://books.google.com/books?id=AxguNHDtO7MC&pg=PA224
| url = https://books.google.com/books?id=AxguNHDtO7MC&pg=PA224
Https://books.google.com/books?id=axgunhdto7mc&pg=pa224
| year = 2007}}.</ref>
| year = 2007}}.</ref>
| year = 2007} . </ref >
In [[projective geometry]], [[Levi graph]]s are a form of bipartite graph used to model the incidences between points and lines in a [[configuration (geometry)|configuration]]. Corresponding to the geometric property of points and lines that every two lines meet in at most one point and every two points be connected with a single line, Levi graphs necessarily do not contain any cycles of length four, so their [[girth (graph theory)|girth]] must be six or more.<ref>{{citation
In projective geometry, Levi graphs are a form of bipartite graph used to model the incidences between points and lines in a configuration. Corresponding to the geometric property of points and lines that every two lines meet in at most one point and every two points be connected with a single line, Levi graphs necessarily do not contain any cycles of length four, so their girth must be six or more.<ref>{{citation
在射影几何中，Levi 图是二部图的一种形式，用来模拟配置中点和线之间的冲突。对应于点和线的几何性质，每两条直线最多相交一点，每两点与一条直线相连，Levi 图不一定包含任何长度为4的圈，所以它们的周长必须是6或更多。< ref > { citation
| last = Grünbaum | first = Branko | author-link = Branko Grünbaum
| last = Grünbaum | first = Branko | author-link = Branko Grünbaum
| last = Grünbaum | first = Branko | author-link = Branko Grünbaum
| isbn = 9780821843086
| isbn = 9780821843086
9780821843086
| page = 28
| page = 28
28
| publisher = [[American Mathematical Society]]
| publisher = American Mathematical Society
美国数学学会
| series = [[Graduate Studies in Mathematics]]
| series = Graduate Studies in Mathematics
数学研究生课程
| title = Configurations of Points and Lines
| title = Configurations of Points and Lines
| title = 点和线的配置
| url = https://books.google.com/books?id=mRw571GNa5UC&pg=PA28
| url = https://books.google.com/books?id=mRw571GNa5UC&pg=PA28
Https://books.google.com/books?id=mrw571gna5uc&pg=pa28
| volume = 103
| volume = 103
103
| year = 2009}}.</ref>
| year = 2009}}.</ref>
2009} . </ref >
==See also==
*[[Bipartite dimension]], the minimum number of complete bipartite graphs whose union is the given graph
*[[Bipartite double cover]], a way of transforming any graph into a bipartite graph by doubling its vertices
*[[Bipartite hypergraph]], a generalization of bipartiteness to [[hypergraph]]s.
*[[Bipartite matroid]], a class of matroids that includes the [[graphic matroid]]s of bipartite graphs
*[[Bipartite network projection]], a weighting technique for compressing information about bipartite networks
*[[Convex bipartite graph]], a bipartite graph whose vertices can be ordered so that the vertex neighborhoods are contiguous
*[[Multipartite graph]], a generalization of bipartite graphs to more than two subsets of vertices
*[[Parity graph]], a generalization of bipartite graphs in which every two [[induced path]]s between the same two points have the same parity
*[[Quasi-bipartite graph]], a type of Steiner tree problem instance in which the terminals form an independent set, allowing approximation algorithms that generalize those for bipartite graphs
*[[Split graph]], a graph in which the vertices can be partitioned into two subsets, one of which is independent and the other of which is a clique
*[[Zarankiewicz problem]] on the maximum number of edges in a bipartite graph with forbidden subgraphs
==References==
{{Reflist|colwidth=30em}}
==External links==
* {{springer|title=Graph, bipartite|id=p/g044880}}
* [http://www.graphclasses.org/ Information System on Graph Classes and their Inclusions]: [http://www.graphclasses.org/classes/gc_69.html bipartite graph]
* {{mathworld | title = Bipartite Graph | urlname = BipartiteGraph}}
* [https://academic.oup.com/gigascience/article/7/4/giy014/4875933/ Bipartite graphs in systems biology and medicine]
[[Category:Graph families]]
Category:Graph families
类别: 图族
[[Category:Bipartite graphs| ]]
[[Category:Parity (mathematics)]]
Category:Parity (mathematics)
分类: 奇偶校验(数学)
<noinclude>
<small>This page was moved from [[wikipedia:en:Bipartite graph]]. Its edit history can be viewed at [[二分图/edithistory]]</small></noinclude>
[[Category:待整理页面]]
[[Image:Simple-bipartite-graph.svg|thumb|Example of a bipartite graph without cycles]]
Example of a bipartite graph without cycles
没有圈的二部图的例子
[[File:Biclique K 3 5.svg|thumbnail|A [[complete bipartite graph]] with m = 5 and n = 3]]
A [[complete bipartite graph with m = 5 and n = 3]]
A [[ m = 5和 n = 3的完全二分图]
In the [[mathematics|mathematical]] field of [[graph theory]], a '''bipartite graph''' (or '''bigraph''') is a [[Graph (discrete mathematics)|graph]] whose [[vertex (graph theory)|vertices]] can be divided into two [[disjoint sets|disjoint]] and [[Independent set (graph theory)|independent sets]] <math>U</math> and <math>V</math> such that every [[edge (graph theory)|edge]] connects a vertex in <math>U</math> to one in <math>V</math>. Vertex sets <math>U</math> and <math>V</math> are usually called the ''parts'' of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length [[cycle (graph theory)|cycles]].<ref name=diestel2005graph>{{cite book|last=Diestel|first=Reinard|title=Graph Theory, Grad. Texts in Math|year=2005|publisher=Springer|isbn=978-3-642-14278-9|url=http://diestel-graph-theory.com/}}</ref><ref>{{citation
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets <math>U</math> and <math>V</math> such that every edge connects a vertex in <math>U</math> to one in <math>V</math>. Vertex sets <math>U</math> and <math>V</math> are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.<ref>{{citation
在图论的数学领域中，二部图(或称二部图)是一种图，它的顶点可以分为两个不相交的独立集合。顶点集 < math > u </math > 和 < math > v </math > 通常被称为图的部分。等价地，二部图是一个不包含任何奇数长度圈的图
| last1 = Asratian
| last1 = Asratian
1 = Asratian
| first1 = Armen S.
| first1 = Armen S.
1 = Armen s.
| last2 = Denley
| last2 = Denley
2 = Denley
| first2 = Tristan M. J.
| first2 = Tristan M. J.
2 = Tristan m. j.
| last3 = Häggkvist
| last3 = Häggkvist
| last3 = Häggkvist
| first3 = Roland
| first3 = Roland
3 = Roland
| isbn = 9780521593458
| isbn = 9780521593458
9780521593458
| publisher = Cambridge University Press
| publisher = Cambridge University Press
剑桥大学出版社
| series = Cambridge Tracts in Mathematics
| series = Cambridge Tracts in Mathematics
| 系列 = 剑桥数学丛书
| title = Bipartite Graphs and their Applications
| title = Bipartite Graphs and their Applications
| title = 二部图及其应用
| volume = 131
| volume = 131
131
| year = 1998
| year = 1998
1998年
| url-access = registration
| url-access = registration
| url-access = registration
| url = https://archive.org/details/bipartitegraphst0000asra
| url = https://archive.org/details/bipartitegraphst0000asra
Https://archive.org/details/bipartitegraphst0000asra
}}.</ref>
}}.</ref>
} . </ref >
The two sets <math>U</math> and <math>V</math> may be thought of as a [[graph coloring|coloring]] of the graph with two colors: if one colors all nodes in <math>U</math> blue, and all nodes in <math>V</math> green, each edge has endpoints of differing colors, as is required in the graph coloring problem.<ref name="adh98-7"/><ref name="s12">{{citation
The two sets <math>U</math> and <math>V</math> may be thought of as a coloring of the graph with two colors: if one colors all nodes in <math>U</math> blue, and all nodes in <math>V</math> green, each edge has endpoints of differing colors, as is required in the graph coloring problem.<ref name="s12">{{citation
这两个集合 < math > u </math > 和 < math > v </math > 可以被看作是两种颜色的图的着色: 如果 < math > u </math > 蓝色中的所有节点都有一种颜色，而 < math > v </math > 绿色中的所有节点都有一种颜色，那么每个边的端点都有不同颜色的端点，就像图着色问题中所要求的那样。12"> { citation
| last = Scheinerman | first = Edward R. | authorlink = Ed Scheinerman
| last = Scheinerman | first = Edward R. | authorlink = Ed Scheinerman
作者: Ed Scheinerman | last = Scheinerman | first = Edward r | authorlink = Ed Scheinerman
| edition = 3rd
| edition = 3rd
3 rd
| isbn = 9780840049421
| isbn = 9780840049421
9780840049421
| page = 363
| page = 363
363
| publisher = Cengage Learning
| publisher = Cengage Learning
2012年3月24日 | publisher = 圣智学习出版公司
| title = Mathematics: A Discrete Introduction
| title = Mathematics: A Discrete Introduction
| title = 数学: 离散介绍
| url = https://books.google.com/books?id=DZBHGD2sEYwC&pg=PA363
| url = https://books.google.com/books?id=DZBHGD2sEYwC&pg=PA363
Https://books.google.com/books?id=dzbhgd2seywc&pg=pa363
| year = 2012}}.</ref> In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a [[Gallery of named graphs|triangle]]: after one node is colored blue and another green, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color.
| year = 2012}}.</ref> In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a triangle: after one node is colored blue and another green, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color.
2012}}.相比之下，对于非二部图，如三角形，这样的着色是不可能的: 在一个节点被着成蓝色和另一个绿色之后，三角形的第三个顶点连接到两种颜色的顶点上，这样就不能给它分配任何一种颜色。
One often writes <math>G=(U,V,E)</math> to denote a bipartite graph whose partition has the parts <math>U</math> and <math>V</math>, with <math>E</math> denoting the edges of the graph. If a bipartite graph is not [[connected graph|connected]], it may have more than one bipartition;<ref>{{citation
One often writes <math>G=(U,V,E)</math> to denote a bipartite graph whose partition has the parts <math>U</math> and <math>V</math>, with <math>E</math> denoting the edges of the graph. If a bipartite graph is not connected, it may have more than one bipartition;<ref>{{citation
人们经常用 < math > g = (u，v，e) </math > 来表示一个二部图，其分区由 < math > u </math > 和 < math > v </math > 组成，用 < math > e </math > 表示图的边。如果一个二部图是不连通的，它可能有一个以上的二部图
| last1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand
| last1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand
1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand
| last2 = Zhang | first2 = Ping | author2-link = Ping Zhang (graph theorist)
| last2 = Zhang | first2 = Ping | author2-link = Ping Zhang (graph theorist)
| last2 = Zhang | first2 = Ping | author2-link = Ping Zhang (图论学家)
| isbn = 9781584888000
| isbn = 9781584888000
9781584888000
| page = 223
| page = 223
223
| publisher = CRC Press
| publisher = CRC Press
| publisher = CRC Press
| series = Discrete Mathematics And Its Applications
| series = Discrete Mathematics And Its Applications
系列 = 离散数学及其应用
| title = Chromatic Graph Theory
| title = Chromatic Graph Theory
彩色图论
| url = https://books.google.com/books?id=_l4CJq46MXwC&pg=PA223
| url = https://books.google.com/books?id=_l4CJq46MXwC&pg=PA223
Https://books.google.com/books?id=_l4cjq46mxwc&pg=pa223
| volume = 53
| volume = 53
53
| year = 2008}}.</ref> in this case, the <math>(U,V,E)</math> notation is helpful in specifying one particular bipartition that may be of importance in an application. If <math>|U|=|V|</math>, that is, if the two subsets have equal [[cardinality]], then <math>G</math> is called a ''balanced'' bipartite graph.<ref name="adh98-7">{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 7.</ref> If all vertices on the same side of the bipartition have the same [[Degree (graph theory)|degree]], then <math>G</math> is called [[biregular graph|biregular]].
| year = 2008}}.</ref> in this case, the <math>(U,V,E)</math> notation is helpful in specifying one particular bipartition that may be of importance in an application. If <math>|U|=|V|</math>, that is, if the two subsets have equal cardinality, then <math>G</math> is called a balanced bipartite graph. If all vertices on the same side of the bipartition have the same degree, then <math>G</math> is called biregular.
2008}}.在这种情况下，< math > (u，v，e) </math > 符号有助于指定一个特定的双分区，这个双分区在应用程序中可能非常重要。如果 < math > | u | = | v | </math > ，也就是说，如果两个子集具有相等的基数，那么 < math > g </math > 被称为平衡二部图。如果二分区同一侧的所有顶点都具有相同的度数，那么 < math > g </math > 称为二正则。
==Examples==
When modelling [[heterogeneous relation|relations]] between two different classes of objects, bipartite graphs very often arise naturally. For instance, a graph of football players and clubs, with an edge between a player and a club if the player has played for that club, is a natural example of an ''affiliation network'', a type of bipartite graph used in [[social network analysis]].<ref>{{citation
When modelling relations between two different classes of objects, bipartite graphs very often arise naturally. For instance, a graph of football players and clubs, with an edge between a player and a club if the player has played for that club, is a natural example of an affiliation network, a type of bipartite graph used in social network analysis.<ref>{{citation
当建立两类不同对象之间的模型关系时，二部图往往自然而然地出现。例如，一个足球运动员和俱乐部的图，如果一个运动员为一个俱乐部效力，那么该运动员和俱乐部之间就有一条边，这是一个隶属关系网络的自然例子，这是一种用于社会网络分析的二部图。< ref > { citation
| last1 = Wasserman | first1 = Stanley
| last1 = Wasserman | first1 = Stanley
1 = Wasserman | first1 = Stanley
| author-link1= Stanley Wasserman
| author-link1= Stanley Wasserman
1 = Stanley Wasserman
| last2 = Faust | first2 = Katherine
| last2 = Faust | first2 = Katherine
| last2 = Faust | first2 = Katherine
| isbn = 9780521387071
| isbn = 9780521387071
9780521387071
| pages = 299–302
| pages = 299–302
| 页数 = 299-302
| publisher = Cambridge University Press
| publisher = Cambridge University Press
剑桥大学出版社
| series = Structural Analysis in the Social Sciences
| series = Structural Analysis in the Social Sciences
系列 = 社会科学中的结构分析
| title = Social Network Analysis: Methods and Applications
| title = Social Network Analysis: Methods and Applications
社会网络分析: 方法和应用
| url = https://books.google.com/books?id=CAm2DpIqRUIC&pg=PA299
| url = https://books.google.com/books?id=CAm2DpIqRUIC&pg=PA299
Https://books.google.com/books?id=cam2dpiqruic&pg=pa299
| volume = 8
| volume = 8
8
| year = 1994}}.</ref>
| year = 1994}}.</ref>
| year = 1994} . </ref >
Another example where bipartite graphs appear naturally is in the ([[NP-complete]]) railway optimization problem, in which the input is a schedule of trains and their stops, and the goal is to find a set of train stations as small as possible such that every train visits at least one of the chosen stations. This problem can be modeled as a [[dominating set]] problem in a bipartite graph that has a vertex for each train and each station and an edge for
Another example where bipartite graphs appear naturally is in the (NP-complete) railway optimization problem, in which the input is a schedule of trains and their stops, and the goal is to find a set of train stations as small as possible such that every train visits at least one of the chosen stations. This problem can be modeled as a dominating set problem in a bipartite graph that has a vertex for each train and each station and an edge for
二部图自然出现的另一个例子是在(np 完全)铁路最佳化问题，其中输入的是列车及其停靠时刻表，目标是找到一组尽可能小的火车站，使每列火车至少到达一个选定的车站。这个问题可以被建模为一个二部图中的支配集问题，这个二部图中每列车和每个车站都有一个顶点，每个车站都有一条边
each pair of a station and a train that stops at that station.<ref name=niedermeier2006invitiation>{{cite book|last=Niedermeier|first=Rolf|title=Invitation to Fixed Parameter Algorithms (Oxford Lecture Series in Mathematics and Its Applications)|year=2006|publisher=Oxford|isbn=978-0-19-856607-6|pages=20–21}}</ref>
each pair of a station and a train that stops at that station.
每一对车站和停在那个车站的火车。
A third example is in the academic field of numismatics. Ancient coins are made using two positive impressions of the design (the obverse and reverse). The charts numismatists produce to represent the production of coins are bipartite graphs.<ref name=bracey2012>{{cite article|last=Bracey|first=Robert|title=On the Graphical Interpreation of Herod's Coinage in Judaea and Rome in Coins|year=2012|url=https://www.academia.edu/2078897|pages=65–84}}</ref>
A third example is in the academic field of numismatics. Ancient coins are made using two positive impressions of the design (the obverse and reverse). The charts numismatists produce to represent the production of coins are bipartite graphs.
第三个例子是钱币学领域。古代硬币的制作是基于对设计的正面印象(正面与背面)。钱币收藏家制作的表示硬币产量的图表是二部图。
More abstract examples include the following:
More abstract examples include the following:
更抽象的例子包括:
* Every [[tree (graph theory)|tree]] is bipartite.<ref name="s12"/>
* [[Cycle graph]]s with an even number of vertices are bipartite.<ref name="s12"/>
* Every [[planar graph]] whose [[Glossary of graph theory#Genus|faces]] all have even length is bipartite.<ref>{{citation|first=Alexander|last=Soifer|authorlink=Alexander Soifer|year=2008|title=The Mathematical Coloring Book|title-link= The Mathematical Coloring Book |publisher=Springer-Verlag|isbn=978-0-387-74640-1|pages=136–137}}. This result has sometimes been called the "two color theorem"; Soifer credits it to a famous 1879 paper of [[Alfred Kempe]] containing a false proof of the [[four color theorem]].</ref> Special cases of this are [[grid graph]]s and [[squaregraph]]s, in which every inner face consists of 4 edges and every inner vertex has four or more neighbors.<ref>{{citation|title=Combinatorics and geometry of finite and infinite squaregraphs|first1=H.-J.|last1=Bandelt|first2=V.|last2=Chepoi|first3=D.|last3=Eppstein|author3-link=David Eppstein|arxiv=0905.4537|journal=[[SIAM Journal on Discrete Mathematics]]|volume=24|issue=4|pages=1399–1440|year=2010|doi=10.1137/090760301}}.</ref>
* The [[complete bipartite graph]] on ''m'' and ''n'' vertices, denoted by ''K<sub>n,m</sub>'' is the bipartite graph <math>G = (U, V, E)</math>, where ''U'' and ''V'' are disjoint sets of size ''m'' and ''n'', respectively, and ''E'' connects every vertex in ''U'' with all vertices in ''V''. It follows that ''K<sub>m,n</sub>'' has ''mn'' edges.<ref>{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 11.</ref> Closely related to the complete bipartite graphs are the [[crown graph]]s, formed from complete bipartite graphs by removing the edges of a [[perfect matching]].<ref>{{citation
| last1 = Archdeacon | first1 = D. | author1-link = Dan Archdeacon
| last1 = Archdeacon | first1 = D. | author1-link = Dan Archdeacon
1 = Archdeacon | first1 = d | author1-link = Dan Archdeacon
| last2 = Debowsky | first2 = M.
| last2 = Debowsky | first2 = M.
2 = Debowsky | first2 = m.
| last3 = Dinitz | first3 = J. | author3-link = Jeff Dinitz
| last3 = Dinitz | first3 = J. | author3-link = Jeff Dinitz
3 = j.| author3-link = Jeff Dinitz
| last4 = Gavlas | first4 = H.
| last4 = Gavlas | first4 = H.
4 = Gavlas | first4 = h.
| doi = 10.1016/j.disc.2003.11.021
| doi = 10.1016/j.disc.2003.11.021
| doi = 10.1016/j.disc. 2003.11.021
| issue = 1–3
| issue = 1–3
第一季，第三集
| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
| journal = Discrete Mathematics
2012年3月24日 | 日志 = 离散数学
| pages = 37–43
| pages = 37–43
| 页数 = 37-43
| title = Cycle systems in the complete bipartite graph minus a one-factor
| title = Cycle systems in the complete bipartite graph minus a one-factor
| title = 完全二分图的循环系统减去一个因子
| volume = 284
| volume = 284
284
| year = 2004| doi-access = free
| year = 2004| doi-access = free
2004 | doi-access = free
}}.</ref>
}}.</ref>
} . </ref >
* [[Hypercube graph]]s, [[partial cube]]s, and [[median graph]]s are bipartite. In these graphs, the vertices may be labeled by [[bitvector]]s, in such a way that two vertices are adjacent if and only if the corresponding bitvectors differ in a single position. A bipartition may be formed by separating the vertices whose bitvectors have an even number of ones from the vertices with an odd number of ones. Trees and squaregraphs form examples of median graphs, and every median graph is a partial cube.<ref>{{citation|first=Sergei|last=Ovchinnikov|title=Graphs and Cubes|series=Universitext|publisher=Springer|year=2011}}. See especially Chapter 5, "Partial Cubes", pp. 127–181.</ref>
==Properties==
===Characterization===
Bipartite graphs may be characterized in several different ways:
Bipartite graphs may be characterized in several different ways:
二部图可以用几种不同的方式来表示:
* A graph is bipartite [[if and only if]] it does not contain an [[Cycle (graph theory)|odd cycle]].<ref>{{harvtxt|Asratian|Denley|Häggkvist|1998}}, 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]].</ref>
* A graph is bipartite if and only if it is 2-colorable, (i.e. its [[chromatic number]] is less than or equal to 2).<ref name="adh98-7"/>
* The [[Spectral graph theory|spectrum]] of a graph is symmetric if and only if it's a bipartite graph.<ref>{{citation
| last = Biggs | first = Norman
| last = Biggs | first = Norman
| last = Biggs | first = Norman
| edition = 2nd
| edition = 2nd
2nd
| isbn = 9780521458979
| isbn = 9780521458979
9780521458979
| page = 53
| page = 53
53
| publisher = Cambridge University Press
| publisher = Cambridge University Press
剑桥大学出版社
| series = Cambridge Mathematical Library
| series = Cambridge Mathematical Library
| series = Cambridge Mathematical Library
| title = Algebraic Graph Theory
| title = Algebraic Graph Theory
| title = 代数图论
| url = https://books.google.com/books?id=6TasRmIFOxQC&pg=PA53
| url = https://books.google.com/books?id=6TasRmIFOxQC&pg=PA53
Https://books.google.com/books?id=6tasrmifoxqc&pg=pa53
| year = 1994}}.</ref>
| year = 1994}}.</ref>
| year = 1994} . </ref >
===Kőnig's theorem and perfect graphs===
In bipartite graphs, the size of [[minimum vertex cover]] is equal to the size of the [[maximum matching]]; this is [[Kőnig's theorem (graph theory)|Kőnig's theorem]].<ref>{{cite journal
In bipartite graphs, the size of minimum vertex cover is equal to the size of the maximum matching; this is Kőnig's theorem.<ref>{{cite journal
在二部图中，最小顶点覆盖的大小等于最大匹配的大小，这就是 k-nig 定理。{ cite journal
| author = Kőnig, Dénes
| author = Kőnig, Dénes
作者: k nig，d é nes
| authorlink = Dénes Kőnig
| authorlink = Dénes Kőnig
| authorlink = d é nes k nig
| title = Gráfok és mátrixok
| title = Gráfok és mátrixok
| title = Gráfok és mátrixok
| journal = Matematikai és Fizikai Lapok
| journal = Matematikai és Fizikai Lapok
| journal = Matematikai és Fizikai Lapok
| volume = 38
| volume = 38
38
| year = 1931
| year = 1931
1931年
| pages = 116–119}}.</ref><ref>{{citation
| pages = 116–119}}.</ref><ref>{{citation
116-119} . </ref > < ref > { citation
| last1 = Gross | first1 = Jonathan L.
| last1 = Gross | first1 = Jonathan L.
1 = Gross | first1 = Jonathan l.
| last2 = Yellen | first2 = Jay
| last2 = Yellen | first2 = Jay
2 = Yellen | first2 = Jay
| edition = 2nd
| edition = 2nd
2nd
| isbn = 9781584885054
| isbn = 9781584885054
9781584885054
| page = 568
| page = 568
568
| publisher = CRC Press
| publisher = CRC Press
| publisher = CRC Press
| series = Discrete Mathematics And Its Applications
| series = Discrete Mathematics And Its Applications
系列 = 离散数学及其应用
| title = Graph Theory and Its Applications
| title = Graph Theory and Its Applications
| title = 图论及其应用
| url = https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA568
| url = https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA568
Https://books.google.com/books?id=-7q_pogh-2cc&pg=pa568
| year = 2005}}.</ref> An alternative and equivalent form of this theorem is that the size of the [[maximum independent set]] plus the size of the maximum matching is equal to the number of vertices.
| year = 2005}}.</ref> An alternative and equivalent form of this theorem is that the size of the maximum independent set plus the size of the maximum matching is equal to the number of vertices.
2005}}.</ref > 这个定理的另一种等价形式是最大独立集的大小加上最大匹配的大小等于顶点的数目。
In any graph without [[isolated vertex|isolated vertices]] the size of the [[minimum edge cover]] plus the size of a maximum matching equals the number of vertices.<ref>{{citation
In any graph without isolated vertices the size of the minimum edge cover plus the size of a maximum matching equals the number of vertices.<ref>{{citation
在任何没有孤立顶点的图中，最小边覆盖的大小加上最大匹配的大小等于顶点的数目。< ref > { citation
| last1 = Chartrand | first1 = Gary
| last1 = Chartrand | first1 = Gary
1 = Chartrand | first1 = Gary
| last2 = Zhang | first2 = Ping
| last2 = Zhang | first2 = Ping
2 = Zhang | first2 = Ping
| isbn = 9780486483689
| isbn = 9780486483689
9780486483689
| pages = 189–190
| pages = 189–190
| 页数 = 189-190
| publisher = Courier Dover Publications
| publisher = Courier Dover Publications
2012年10月21日 | 出版商 = 多佛出版社
| title = A First Course in Graph Theory
| title = A First Course in Graph Theory
图论第一课
| url = https://books.google.com/books?id=ocIr0RHyI8oC&pg=PA189
| url = https://books.google.com/books?id=ocIr0RHyI8oC&pg=PA189
Https://books.google.com/books?id=ocir0rhyi8oc&pg=pa189
| year = 2012}}.</ref> Combining this equality with Kőnig's theorem leads to the facts that, in bipartite graphs, the size of the minimum edge cover is equal to the size of the maximum independent set, and the size of the minimum edge cover plus the size of the minimum vertex cover is equal to the number of vertices.
| year = 2012}}.</ref> Combining this equality with Kőnig's theorem leads to the facts that, in bipartite graphs, the size of the minimum edge cover is equal to the size of the maximum independent set, and the size of the minimum edge cover plus the size of the minimum vertex cover is equal to the number of vertices.
2012}}.</ref > 将这个等式与 k nig 定理结合起来得到这样一个结论: 在二部图中，最小边覆盖的大小等于最大独立集的大小，最小边覆盖的大小加上最小顶点覆盖的大小等于顶点的数目。
Another class of related results concerns [[perfect graph]]s: every bipartite graph, the [[complement (graph theory)|complement]] of every bipartite graph, the [[line graph]] of every bipartite graph, and the complement of the line graph of every bipartite graph, are all perfect. Perfection of bipartite graphs is easy to see (their [[chromatic number]] is two and their [[maximum clique]] size is also two) but perfection of the [[complement (graph theory)|complements]] of bipartite graphs is less trivial, and is another restatement of Kőnig's theorem. This was one of the results that motivated the initial definition of perfect graphs.<ref>{{citation|title=Modern Graph Theory
Another class of related results concerns perfect graphs: every bipartite graph, the complement of every bipartite graph, the line graph of every bipartite graph, and the complement of the line graph of every bipartite graph, are all perfect. Perfection of bipartite graphs is easy to see (their chromatic number is two and their maximum clique size is also two) but perfection of the complements of bipartite graphs is less trivial, and is another restatement of Kőnig's theorem. This was one of the results that motivated the initial definition of perfect graphs.<ref>{{citation|title=Modern Graph Theory
另一类相关结果涉及完美图: 每一个二部图、每一个二部图的补图、每一个二部图的线图以及每一个二部图的线图的补图都是完美的。二部图的完美性是显而易见的(它们的色数是2，它们的最大团大小也是2) ，但二部图的补图的完美性是不那么琐碎的，是对 k nig 定理的另一种重述。这是激发完美图最初定义的结果之一
|volume= 184 |series= Graduate Texts in Mathematics
|volume= 184 |series= Graduate Texts in Mathematics
184 | series = 数学研究生教材
|author=Béla Bollobás|publisher =Springer|year= 1998
|author=Béla Bollobás|publisher =Springer|year= 1998
1998年
|isbn= 9780387984889|url=https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA165|page=165|author-link= Béla Bollobás }}.</ref> Perfection of the complements of line graphs of perfect graphs is yet another restatement of Kőnig's theorem, and perfection of the line graphs themselves is a restatement of an earlier theorem of Kőnig, that every bipartite graph has an [[edge coloring]] using a number of colors equal to its maximum degree.
|isbn= 9780387984889|url=https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA165|page=165|author-link= Béla Bollobás }}.</ref> Perfection of the complements of line graphs of perfect graphs is yet another restatement of Kőnig's theorem, and perfection of the line graphs themselves is a restatement of an earlier theorem of Kőnig, that every bipartite graph has an edge coloring using a number of colors equal to its maximum degree.
9780387984889 | url = https://books.google.com/books?id=sbzksz-1qrwc&pg=pa165|page=165|author-link= · 贝拉 · 博洛巴斯}。完全图的线图的补图的完美性是对 k nig 定理的又一次重申，线图本身的完美性是对 k nig 早期定理的重申，即每个二部图都有一个边着色，其颜色数等于它的最大度。
According to the [[strong perfect graph theorem]], the perfect graphs have a [[forbidden graph characterization]] resembling that of bipartite graphs: a graph is bipartite if and only if it has no odd cycle as a subgraph, and a graph is perfect if and only if it has no odd cycle or its [[complement (graph theory)|complement]] as an [[induced subgraph]]. The bipartite graphs, line graphs of bipartite graphs, and their complements form four out of the five basic classes of perfect graphs used in the proof of the strong perfect graph theorem.<ref>{{citation
According to the strong perfect graph theorem, the perfect graphs have a forbidden graph characterization resembling that of bipartite graphs: a graph is bipartite if and only if it has no odd cycle as a subgraph, and a graph is perfect if and only if it has no odd cycle or its complement as an induced subgraph. The bipartite graphs, line graphs of bipartite graphs, and their complements form four out of the five basic classes of perfect graphs used in the proof of the strong perfect graph theorem.<ref>{{citation
根据完美图问题，完美图有一个类似于二部图的禁止图: 一个图是二部图的当且仅当它作为一个子图没有奇圈，并且一个图是完美的当且仅当它没有奇圈或它作为诱导子图的补图。二部图，二部图的线图，以及它们的补图在完美图问题证明中的5个基本类型的完美图中的4个。< ref > { citation
| last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky
| last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky
1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky
| last2 = Robertson | first2 = Neil | author2-link = Neil Robertson (mathematician)
| last2 = Robertson | first2 = Neil | author2-link = Neil Robertson (mathematician)
| last2 = Robertson | first2 = Neil | author2-link = Neil Robertson (数学家)
| last3 = Seymour | first3 = Paul | author3-link = Paul Seymour (mathematician)
| last3 = Seymour | first3 = Paul | author3-link = Paul Seymour (mathematician)
3 = Seymour | first3 = Paul | author3-link = Paul Seymour (数学家)
| last4 = Thomas | first4 = Robin | author4-link = Robin Thomas (mathematician)
| last4 = Thomas | first4 = Robin | author4-link = Robin Thomas (mathematician)
| last4 = Thomas | first4 = Robin | author4-link = Robin Thomas (数学家)
| doi = 10.4007/annals.2006.164.51
| doi = 10.4007/annals.2006.164.51
2006.164.51
| issue = 1
| issue = 1
1
| journal = [[Annals of Mathematics]]
| journal = Annals of Mathematics
2012年3月24日 | 日志 = 数学纪事
| pages = 51–229
| pages = 51–229
| 页数 = 51-229
| title = The strong perfect graph theorem
| title = The strong perfect graph theorem
纽约完美图问题
| volume = 164
| volume = 164
164
| year = 2006| citeseerx = 10.1.1.111.7265| arxiv = math/0212070}}.</ref>
| year = 2006| citeseerx = 10.1.1.111.7265| arxiv = math/0212070}}.</ref>
2006 | citeseerx = 10.1.1.111.7265 | arxiv = math/0212070}} . </ref >
===Degree===
For a vertex, the number of adjacent vertices is called the [[degree (graph theory)|degree]] of the vertex and is denoted <math>\deg(v)</math>.
For a vertex, the number of adjacent vertices is called the degree of the vertex and is denoted <math>\deg(v)</math>.
对于一个顶点，相邻顶点的数目称为顶点的度数，表示为 < math > deg (v) </math > 。
The ''degree sum formula'' for a bipartite graph states that
The degree sum formula for a bipartite graph states that
二部图的度和公式表明:
:<math>\sum_{v \in V} \deg(v) = \sum_{u \in U} \deg(u) = |E|\, .</math>
<math>\sum_{v \in V} \deg(v) = \sum_{u \in U} \deg(u) = |E|\, .</math>
<math>\sum_{v \in V} \deg(v) = \sum_{u \in U} \deg(u) = |E|\, .</math>
The degree sequence of a bipartite graph is the pair of lists each containing the degrees of the two parts <math>U</math> and <math>V</math>. For example, the complete bipartite graph ''K''<sub>3,5</sub> has degree sequence <math>(5,5,5),(3,3,3,3,3)</math>. Isomorphic bipartite graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a bipartite graph; in some cases, non-isomorphic bipartite graphs may have the same degree sequence.
The degree sequence of a bipartite graph is the pair of lists each containing the degrees of the two parts <math>U</math> and <math>V</math>. For example, the complete bipartite graph K<sub>3,5</sub> has degree sequence <math>(5,5,5),(3,3,3,3,3)</math>. Isomorphic bipartite graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a bipartite graph; in some cases, non-isomorphic bipartite graphs may have the same degree sequence.
二部图的度序列是一对列表，每一个列表包含两部分的度。例如，完全二分图 k < sub > 3,5 </sub > 具有度序列 < math > (5,5,5) ，(3,3,3,3,3,3) </math > 。同构二部图具有相同的度序列。然而，度序列通常不能唯一地识别二部图，在某些情况下，不同构的二部图可能具有相同的度序列。
The [[bipartite realization problem]] is the problem of finding a simple bipartite graph with the degree sequence being two given lists of natural numbers. (Trailing zeros may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the digraph.)
The bipartite realization problem is the problem of finding a simple bipartite graph with the degree sequence being two given lists of natural numbers. (Trailing zeros may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the digraph.)
二部实现问题是寻找度序列为两个给定自然数列表的简单二部图的问题。(尾随零可能被忽略，因为它们通过向有向图添加适当数量的孤立顶点来实现。)
===Relation to hypergraphs and directed graphs===
The [[Adjacency matrix of a bipartite graph|biadjacency matrix]] of a bipartite graph <math>(U,V,E)</math> is a [[(0,1) matrix]] of size <math>|U|\times|V|</math> that has a one for each pair of adjacent vertices and a zero for nonadjacent vertices.<ref>{{harvtxt|Asratian|Denley|Häggkvist|1998}}, p. 17.</ref> Biadjacency matrices may be used to describe equivalences between bipartite graphs, hypergraphs, and directed graphs.
The biadjacency matrix of a bipartite graph <math>(U,V,E)</math> is a (0,1) matrix of size <math>|U|\times|V|</math> that has a one for each pair of adjacent vertices and a zero for nonadjacent vertices. Biadjacency matrices may be used to describe equivalences between bipartite graphs, hypergraphs, and directed graphs.
二部图的二邻接矩阵 < math > (u，v，e) </math > 是一个大小为 < math > | u | times | v | </math > 的(0,1)矩阵，每对相邻顶点有一个1，对不相邻顶点有一个0。双邻接矩阵可以用来描述二部图、超图和有向图之间的等价关系。
A [[hypergraph]] is a combinatorial structure that, like an undirected graph, has vertices and edges, but in which the edges may be arbitrary sets of vertices rather than having to have exactly two endpoints. A bipartite graph <math>(U,V,E)</math> may be used to model a hypergraph in which {{mvar|U}} is the set of vertices of the hypergraph, {{mvar|V}} is the set of hyperedges, and {{mvar|E}} contains an edge from a hypergraph vertex {{mvar|v}} to a hypergraph edge {{mvar|e}} exactly when {{mvar|v}} is one of the endpoints of {{mvar|e}}. Under this correspondence, the biadjacency matrices of bipartite graphs are exactly the [[incidence matrix|incidence matrices]] of the corresponding hypergraphs. As a special case of this correspondence between bipartite graphs and hypergraphs, any [[multigraph]] (a graph in which there may be two or more edges between the same two vertices) may be interpreted as a hypergraph in which some hyperedges have equal sets of endpoints, and represented by a bipartite graph that does not have multiple adjacencies and in which the vertices on one side of the bipartition all have [[degree (graph theory)|degree]] two.<ref>{{SpringerEOM|title=Hypergraph|author=A. A. Sapozhenko}}</ref>
A hypergraph is a combinatorial structure that, like an undirected graph, has vertices and edges, but in which the edges may be arbitrary sets of vertices rather than having to have exactly two endpoints. A bipartite graph <math>(U,V,E)</math> may be used to model a hypergraph in which is the set of vertices of the hypergraph, is the set of hyperedges, and contains an edge from a hypergraph vertex to a hypergraph edge exactly when is one of the endpoints of . Under this correspondence, the biadjacency matrices of bipartite graphs are exactly the incidence matrices of the corresponding hypergraphs. As a special case of this correspondence between bipartite graphs and hypergraphs, any multigraph (a graph in which there may be two or more edges between the same two vertices) may be interpreted as a hypergraph in which some hyperedges have equal sets of endpoints, and represented by a bipartite graph that does not have multiple adjacencies and in which the vertices on one side of the bipartition all have degree two.
一个超图是一个组合结构，就像一个无向图，有顶点和边，但其中的边可能是任意的顶点集，而不是必须有正好两个端点。二部图 < math > (u，v，e) </math > 可以用来建模一个超图，其中超图的顶点集是超边的集合，它包含一条从超图顶点到超图边的边，而这条边恰好是超图的端点之一。在此对应关系下，二部图的二邻接矩阵正好是对应超图的关联矩阵。作为二部图和超图之间对应关系的一种特殊情形，任何多重图(在同一两个顶点之间可能有两条或更多条边的图)都可以被解释为一个超图，其中一些超边具有相等的端点集，并由一个不具有多重邻接的二部图表示，在这个超图中，二部分一边的顶点都具有二次。
A similar reinterpretation of adjacency matrices may be used to show a one-to-one correspondence between [[directed graph]]s (on a given number of labeled vertices, allowing self-loops) and balanced bipartite graphs, with the same number of vertices on both sides of the bipartition. For, the adjacency matrix of a directed graph with {{mvar|n}} vertices can be any [[(0,1) matrix]] of size <math>n\times n</math>, which can then be reinterpreted as the adjacency matrix of a bipartite graph with {{mvar|n}} vertices on each side of its bipartition.<ref>{{citation
A similar reinterpretation of adjacency matrices may be used to show a one-to-one correspondence between directed graphs (on a given number of labeled vertices, allowing self-loops) and balanced bipartite graphs, with the same number of vertices on both sides of the bipartition. For, the adjacency matrix of a directed graph with vertices can be any (0,1) matrix of size <math>n\times n</math>, which can then be reinterpreted as the adjacency matrix of a bipartite graph with vertices on each side of its bipartition.<ref>{{citation
一个类似的邻接矩阵翻唱可以用来显示有向图(在给定数量的标号顶点上，允许自循环)和平衡二部图之间的双射，二部图的两边顶点数相同。因为，顶点有向图的邻接矩阵可以是任意大小的(0,1)矩阵 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n 次 n。< ref > { citation
| last1 = Brualdi | first1 = Richard A.
| last1 = Brualdi | first1 = Richard A.
1 = Brualdi | first1 = Richard a.
| last2 = Harary | first2 = Frank | author2-link = Frank Harary
| last2 = Harary | first2 = Frank | author2-link = Frank Harary
2 = Harary | first2 = Frank | author2-link = Frank Harary
| last3 = Miller | first3 = Zevi
| last3 = Miller | first3 = Zevi
3 = Miller | first3 = Zevi
| doi = 10.1002/jgt.3190040107
| doi = 10.1002/jgt.3190040107
| doi = 10.1002/jgt. 3190040107
| mr = 558453
| mr = 558453
558453先生
| issue = 1
| issue = 1
1
| journal = Journal of Graph Theory
| journal = Journal of Graph Theory
| Journal = Journal of Graph Theory
| pages = 51–73
| pages = 51–73
| 页数 = 51-73
| title = Bigraphs versus digraphs via matrices
| title = Bigraphs versus digraphs via matrices
| title = Bigraphs vs 通过矩阵的有向图
| volume = 4
| volume = 4
4
| year = 1980}}. Brualdi et al. credit the idea for this equivalence to {{citation
| year = 1980}}. Brualdi et al. credit the idea for this equivalence to {{citation
1980}}.布鲁迪等人。把这个等价的概念归功于{ citation
| doi = 10.4153/CJM-1958-052-0
| doi = 10.4153/CJM-1958-052-0
| doi = 10.4153/CJM-1958-052-0
| last1 = Dulmage | first1 = A. L.
| last1 = Dulmage | first1 = A. L.
1 = Dulmage | first1 = A.l.
| last2 = Mendelsohn | first2 = N. S. | author2-link = Nathan Mendelsohn
| last2 = Mendelsohn | first2 = N. S. | author2-link = Nathan Mendelsohn
2 = Mendelsohn | first2 = n. s. | author2-link = Nathan Mendelsohn
| mr = 0097069
| mr = 0097069
0097069先生
| journal = Canadian Journal of Mathematics
| journal = Canadian Journal of Mathematics
加拿大数学杂志
| pages = 517–534
| pages = 517–534
| 页数 = 517-534
| title = Coverings of bipartite graphs
| title = Coverings of bipartite graphs
| title = 二部图的覆盖
| volume = 10
| volume = 10
10
| year = 1958}}.</ref> In this construction, the bipartite graph is the [[bipartite double cover]] of the directed graph.
| year = 1958}}.</ref> In this construction, the bipartite graph is the bipartite double cover of the directed graph.
| year = 1958}。 </ref > 在这个结构中，二部图是有向图的二部双覆盖。
==Algorithms==
===Testing bipartiteness===
It is possible to test whether a graph is bipartite, and to return either a two-coloring (if it is bipartite) or an odd cycle (if it is not) in [[linear time]], using [[depth-first search]]. The main idea is to assign to each vertex the color that differs from the color of its parent in the depth-first search forest, assigning colors in a [[preorder traversal]] of the depth-first-search forest. This will necessarily provide a two-coloring of the [[spanning forest]] consisting of the edges connecting vertices to their parents, but it may not properly color some of the non-forest edges. In a depth-first search forest, one of the two endpoints of every non-forest edge is an ancestor of the other endpoint, and when the depth first search discovers an edge of this type it should check that these two vertices have different colors. If they do not, then the path in the forest from ancestor to descendant, together with the miscolored edge, form an odd cycle, which is returned from the algorithm together with the result that the graph is not bipartite. However, if the algorithm terminates without detecting an odd cycle of this type, then every edge must be properly colored, and the algorithm returns the coloring together with the result that the graph is bipartite.<ref>{{citation
It is possible to test whether a graph is bipartite, and to return either a two-coloring (if it is bipartite) or an odd cycle (if it is not) in linear time, using depth-first search. The main idea is to assign to each vertex the color that differs from the color of its parent in the depth-first search forest, assigning colors in a preorder traversal of the depth-first-search forest. This will necessarily provide a two-coloring of the spanning forest consisting of the edges connecting vertices to their parents, but it may not properly color some of the non-forest edges. In a depth-first search forest, one of the two endpoints of every non-forest edge is an ancestor of the other endpoint, and when the depth first search discovers an edge of this type it should check that these two vertices have different colors. If they do not, then the path in the forest from ancestor to descendant, together with the miscolored edge, form an odd cycle, which is returned from the algorithm together with the result that the graph is not bipartite. However, if the algorithm terminates without detecting an odd cycle of this type, then every edge must be properly colored, and the algorithm returns the coloring together with the result that the graph is bipartite.<ref>{{citation
我们可以用深度优先搜索来检验一个图是否是二部图，并且可以在线性时间内返回一个双染色(如果是二部图)或一个奇循环(如果不是)。其主要思想是在深度优先搜索森林中为每个顶点分配与其父顶点颜色不同的颜色，在深度优先搜索森林的前序遍历中分配颜色。这将必然提供一个双着色的跨森林组成的边连接顶点到他们的父母，但它可能不适当的颜色一些非森林边。在深度优先搜索森林中，每个非森林边缘的两个端点中的一个是另一个端点的祖先，当深度首次搜索发现这种类型的边缘时，应该检查这两个顶点是否有不同的颜色。如果不是这样，那么森林中从祖先到后代的路径与错误着色的边一起形成一个奇循环，这个奇循环由算法返回，并得到图不是二部图的结果。然而，如果算法在没有检测到奇圈的情况下终止，那么每条边都必须正确着色，并且算法返回着色结果和图是二部图的结果。< ref > { citation
| last = Sedgewick | first = Robert | author-link = Robert Sedgewick (computer scientist)
| last = Sedgewick | first = Robert | author-link = Robert Sedgewick (computer scientist)
罗伯特·塞奇威克: 计算机科学家
| edition = 3rd
| edition = 3rd
3 rd
| pages = 109–111
| pages = 109–111
| pages = 109-111
| publisher = Addison Wesley
| publisher = Addison Wesley
艾迪生 · 韦斯利
| title = Algorithms in Java, Part 5: Graph Algorithms
| title = Algorithms in Java, Part 5: Graph Algorithms
Java 中的算法，第五部分: 图算法
| year = 2004}}.</ref>
| year = 2004}}.</ref>
| year = 2004} . </ref >
Alternatively, a similar procedure may be used with [[breadth-first search]] in place of depth-first search. Again, each node is given the opposite color to its parent in the search forest, in breadth-first order. If, when a vertex is colored, there exists an edge connecting it to a previously-colored vertex with the same color, then this edge together with the paths in the breadth-first search forest connecting its two endpoints to their [[lowest common ancestor]] forms an odd cycle. If the algorithm terminates without finding an odd cycle in this way, then it must have found a proper coloring, and can safely conclude that the graph is bipartite.<ref>{{citation
Alternatively, a similar procedure may be used with breadth-first search in place of depth-first search. Again, each node is given the opposite color to its parent in the search forest, in breadth-first order. If, when a vertex is colored, there exists an edge connecting it to a previously-colored vertex with the same color, then this edge together with the paths in the breadth-first search forest connecting its two endpoints to their lowest common ancestor forms an odd cycle. If the algorithm terminates without finding an odd cycle in this way, then it must have found a proper coloring, and can safely conclude that the graph is bipartite.<ref>{{citation
或者，类似的方法也可以用广度优先搜索替代深度优先搜索。同样，在搜索林中，每个节点以与其父节点相反的颜色按广度优先的顺序给出。如果，当一个顶点着色时，存在一条边将其与先前着色的顶点用同样的颜色连接起来，那么这条边与广度优先搜索森林中连接其两个端点与它们的最近公共祖先的路径一起形成一个奇怪的循环。如果算法以这种方式终止而不发现奇循环，那么它一定已经发现了一个适当的着色，并且可以安全地得出图是二部图的结论。< ref > { citation
| last1 = Kleinberg | first1 = Jon | author1-link = Jon Kleinberg
| last1 = Kleinberg | first1 = Jon | author1-link = Jon Kleinberg
1 = Kleinberg | first1 = Jon | author1-link = Jon Kleinberg
| last2 = Tardos | first2 = Éva | author2-link = Éva Tardos
| last2 = Tardos | first2 = Éva | author2-link = Éva Tardos
| last2 = Tardos | first2 = Éva | author2-link = Éva Tardos
| pages = 94–97
| pages = 94–97
94-97
| publisher = Addison Wesley
| publisher = Addison Wesley
艾迪生 · 韦斯利
| title = Algorithm Design
| title = Algorithm Design
算法设计
| year = 2006}}.</ref>
| year = 2006}}.</ref>
| year = 2006} . </ref >
For the [[intersection graph]]s of <math>n</math> [[line segment]]s or other simple shapes in the [[Euclidean plane]], it is possible to test whether the graph is bipartite and return either a two-coloring or an odd cycle in time <math>O(n\log n)</math>, even though the graph itself may have up to <math>O(n^2)</math> edges.<ref>{{citation
For the intersection graphs of <math>n</math> line segments or other simple shapes in the Euclidean plane, it is possible to test whether the graph is bipartite and return either a two-coloring or an odd cycle in time <math>O(n\log n)</math>, even though the graph itself may have up to <math>O(n^2)</math> edges.<ref>{{citation
对于 < math > n </math > 线段的交叉图或欧几里德平面上其他简单形状，即使图本身可能有 < math > o (n ^ 2) </math > 边，也可以检验图是否为二部图，并在时间上返回一个双染色或奇循环。< ref > { citation
| last = Eppstein | first = David | author-link = David Eppstein
| last = Eppstein | first = David | author-link = David Eppstein
最后 = Eppstein | 第一 = David | author-link = David Eppstein
| arxiv = cs.CG/0307023
| arxiv = cs.CG/0307023
| arxiv = cs.CG/0307023
| doi = 10.1145/1497290.1497291
| doi = 10.1145/1497290.1497291
10.1145/1497290.1497291
| issue = 2
| issue = 2
2
| journal = ACM Transactions on Algorithms
| journal = ACM Transactions on Algorithms
关于算法的 ACM 汇刊
| mr = 2561751
| mr = 2561751
2561751先生
| page = Art. 15
| page = Art. 15
| page = Art.15
| title = Testing bipartiteness of geometric intersection graphs
| title = Testing bipartiteness of geometric intersection graphs
| title = 几何交图的测试双分性
| volume = 5
| volume = 5
5
| year = 2009}}.</ref>
| year = 2009}}.</ref>
2009} . </ref >
===Odd cycle transversal===
{{main|Odd cycle transversal}}
[[File:Odd Cycle Transversal of size 2.png|thumb|A graph with an odd cycle transversal of size 2: removing the two blue bottom vertices leaves a bipartite graph.]]
A graph with an odd cycle transversal of size 2: removing the two blue bottom vertices leaves a bipartite graph.
一个具有大小为2的奇圈横截的图: 去掉两个蓝色底顶点后得到一个二部图。
[[Odd cycle transversal]] is an [[NP-complete]] [[algorithm]]ic problem that asks, given a graph ''G'' = (''V'',''E'') and a number ''k'', whether there exists a set of ''k'' vertices whose removal from ''G'' would cause the resulting graph to be bipartite.<ref name=yannakakis1978node>{{citation
Odd cycle transversal is an NP-complete algorithmic problem that asks, given a graph G = (V,E) and a number k, whether there exists a set of k vertices whose removal from G would cause the resulting graph to be bipartite.<ref name=yannakakis1978node>{{citation
奇圈横截是一个 np 完全计算问题，它要求给定一个图 g = (v，e)和一个数 k，是否存在一组 k 点，从 g 中去掉这些点会使得得到的图是二部图。1978 node > { citation
| last = Yannakakis | first = Mihalis | author-link = Mihalis Yannakakis
| last = Yannakakis | first = Mihalis | author-link = Mihalis Yannakakis
最后 = yannakis | first = Mihalis | author-link = Mihalis yannakis
| contribution = Node-and edge-deletion NP-complete problems
| contribution = Node-and edge-deletion NP-complete problems
| 贡献 = 节点和边删除 np 完全问题
| doi = 10.1145/800133.804355
| doi = 10.1145/800133.804355
| doi = 10.1145/800133.804355
| pages = 253–264
| pages = 253–264
| 页 = 253-264
| title = Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78)
| title = Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78)
| title = 第十届 ACM 计算理论研讨会论文集(STOC’78)
| year = 1978| title-link = Symposium on Theory of Computing }}</ref> The problem is [[Parameterized complexity|fixed-parameter tractable]], meaning that there is an algorithm whose running time can be bounded by a polynomial function of the size of the graph multiplied by a larger function of ''k''.<ref name=reed2004finding>{{citation
| year = 1978| title-link = Symposium on Theory of Computing }}</ref> The problem is fixed-parameter tractable, meaning that there is an algorithm whose running time can be bounded by a polynomial function of the size of the graph multiplied by a larger function of k.<ref name=reed2004finding>{{citation
这个问题是固定参数可处理的，这意味着有一个算法，其运行时间可以由图的大小乘以一个更大的函数 k 的多项式函数来限定
| last1 = Reed | first1 = Bruce | author1-link = Bruce Reed (mathematician)
| last1 = Reed | first1 = Bruce | author1-link = Bruce Reed (mathematician)
1 = Reed | first1 = Bruce | author1-link = Bruce Reed (数学家)
| last2 = Smith | first2 = Kaleigh
| last2 = Smith | first2 = Kaleigh
2 = Smith | first2 = Kaleigh
| last3 = Vetta | first3 = Adrian
| last3 = Vetta | first3 = Adrian
3 = Vetta | first3 = Adrian
| doi = 10.1016/j.orl.2003.10.009
| doi = 10.1016/j.orl.2003.10.009
10.1016/j.orl. 2003.10.009
| issue = 4
| issue = 4
第四期
| journal = Operations Research Letters
| journal = Operations Research Letters
| 日志 = 运筹学快报
| mr = 2057781
| mr = 2057781
2057781先生
| pages = 299–301
| pages = 299–301
| 页数 = 299-301
| title = Finding odd cycle transversals
| title = Finding odd cycle transversals
| title = 查找奇怪的循环横截
| volume = 32
| volume = 32
32
| year = 2004| citeseerx = 10.1.1.112.6357}}.</ref> The name ''odd cycle transversal'' comes from the fact that a graph is bipartite if and only if it has no odd [[Cycle (graph theory)|cycles]]. Hence, to delete vertices from a graph in order to obtain a bipartite graph, one needs to "hit all odd cycle", or find a so-called odd cycle [[Transversal (combinatorics)|transversal]] set. In the illustration, every odd cycle in the graph contains the blue (the bottommost) vertices, so removing those vertices kills all odd cycles and leaves a bipartite graph.
| year = 2004| citeseerx = 10.1.1.112.6357}}.</ref> The name odd cycle transversal comes from the fact that a graph is bipartite if and only if it has no odd cycles. Hence, to delete vertices from a graph in order to obtain a bipartite graph, one needs to "hit all odd cycle", or find a so-called odd cycle transversal set. In the illustration, every odd cycle in the graph contains the blue (the bottommost) vertices, so removing those vertices kills all odd cycles and leaves a bipartite graph.
10.1.1.112.6357}.名称奇圈横截来自于这样一个事实: 一个图是二部图当且仅当它没有奇圈。因此，要从图中删除顶点以得到二部图，就需要“遍历所有奇圈” ，或者找到一个所谓的奇圈横截集。在图中，图中的每个奇数圈都包含蓝色(最底部的)顶点，因此去掉这些顶点会杀死所有奇数圈并留下一个二部图。
The ''edge bipartization'' problem is the algorithmic problem of deleting as few edges as possible to make a graph bipartite and is also an important problem in graph modification algorithmics. This problem is also [[fixed-parameter tractable]], and can be solved in time ''O''(2<sup>''k''</sup> ''m''<sup>2</sup>),<ref name=guo2006compression>{{citation
The edge bipartization problem is the algorithmic problem of deleting as few edges as possible to make a graph bipartite and is also an important problem in graph modification algorithmics. This problem is also fixed-parameter tractable, and can be solved in time O(2<sup>k</sup> m<sup>2</sup>),<ref name=guo2006compression>{{citation
边双分问题是为了构造一个二部图而删除尽可能少的边的计算问题问题，也是图修正算法中的一个重要问题。这个问题也是固定参数易于处理的，可以在 o (2 < sup > k </sup > m < sup > 2 </sup >) ，< ref name = guo2006compression > { citation > 中解决
| last1 = Guo | first1 = Jiong
| last1 = Guo | first1 = Jiong
1 = Guo | first1 = Jiong
| last2 = Gramm | first2 = Jens
| last2 = Gramm | first2 = Jens
2 = Gramm | first2 = Jens
| last3 = Hüffner | first3 = Falk
| last3 = Hüffner | first3 = Falk
| last3 = Hüffner | first3 = Falk
| last4 = Niedermeier | first4 = Rolf
| last4 = Niedermeier | first4 = Rolf
4 = Rolf
| last5 = Wernicke | first5 = Sebastian
| last5 = Wernicke | first5 = Sebastian
5 = Wernicke | first5 = Sebastian
| doi = 10.1016/j.jcss.2006.02.001
| doi = 10.1016/j.jcss.2006.02.001
| doi = 10.1016/jcss. 2006.02.001
| journal = Journal of Computer and System Sciences
| journal = Journal of Computer and System Sciences
计算机与系统科学杂志
| volume = 72
| volume = 72
72
| issue = 8
| issue = 8
第8期
| pages = 1386–1396
| pages = 1386–1396
| 页数 = 1386-1396
| title = Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
| title = Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
| title = 基于压缩的反馈顶点集和边双分离的固定参数算法
| year = 2006}}</ref> where ''k'' is the number of edges to delete and ''m'' is the number of edges in the input graph.
| year = 2006}}</ref> where k is the number of edges to delete and m is the number of edges in the input graph.
| year = 2006} </ref > 其中 k 是要删除的边数，m 是输入图中的边数。
===Matching===
{{main|Matching (graph theory)}}
A [[Matching (graph theory)|matching]] in a graph is a subset of its edges, no two of which share an endpoint. [[Polynomial time]] algorithms are known for many algorithmic problems on matchings, including [[maximum matching]] (finding a matching that uses as many edges as possible), [[maximum weight matching]], and [[stable marriage]].<ref>{{citation
A matching in a graph is a subset of its edges, no two of which share an endpoint. Polynomial time algorithms are known for many algorithmic problems on matchings, including maximum matching (finding a matching that uses as many edges as possible), maximum weight matching, and stable marriage.<ref>{{citation
图中的匹配是其边的一个子集，没有两条边共享一个端点。多项式时间算法已知的许多算法问题的匹配，包括最大匹配(寻找匹配，使用尽可能多的边) ，最大权重匹配，和稳定的婚姻。< ref > { citation
| last1 = Ahuja | first1 = Ravindra K.
| last1 = Ahuja | first1 = Ravindra K.
1 = Ahuja | first1 = Ravindra k.
| last2 = Magnanti | first2 = Thomas L.
| last2 = Magnanti | first2 = Thomas L.
2 = Magnanti | first2 = Thomas l.
| last3 = Orlin | first3 = James B.
| last3 = Orlin | first3 = James B.
3 = Orlin | first3 = James b.
| contribution = 12. Assignments and Matchings
| contribution = 12. Assignments and Matchings
12.作业和匹配
| pages = 461–509
| pages = 461–509
| 页数 = 461-509
| publisher = Prentice Hall
| publisher = Prentice Hall
普伦蒂斯 · 霍尔
| title = Network Flows: Theory, Algorithms, and Applications
| title = Network Flows: Theory, Algorithms, and Applications
| title = 网络流: 理论、算法和应用
| year = 1993}}.</ref> In many cases, matching problems are simpler to solve on bipartite graphs than on non-bipartite graphs,<ref>{{harvtxt|Ahuja|Magnanti|Orlin|1993}}, p. 463: "Nonbipartite matching problems are more difficult to solve because they do not reduce to standard network flow problems."</ref> and many matching algorithms such as the [[Hopcroft–Karp algorithm]] for maximum cardinality matching<ref>{{citation|first1=John E.|last1=Hopcroft|author1-link=John Hopcroft|first2=Richard M.|last2=Karp|author2-link=Richard Karp|title=An ''n''<sup>5/2</sup> algorithm for maximum matchings in bipartite graphs|journal=SIAM Journal on Computing|volume=2|issue=4|pages=225–231|year=1973|doi=10.1137/0202019}}.</ref> work correctly only on bipartite inputs.
| year = 1993}}.</ref> In many cases, matching problems are simpler to solve on bipartite graphs than on non-bipartite graphs, and many matching algorithms such as the Hopcroft–Karp algorithm for maximum cardinality matching work correctly only on bipartite inputs.
1993}}.在许多情况下，二部图上的匹配问题比非二部图上的匹配问题更容易解决，而且许多匹配算法，如最大基数匹配的霍普克罗夫特-卡普算法，只能在二部图输入上正确工作。
As a simple example, suppose that a set <math>P</math> of people are all seeking jobs from among a set of <math>J</math> jobs, with not all people suitable for all jobs. This situation can be modeled as a bipartite graph <math>(P,J,E)</math> where an edge connects each job-seeker with each suitable job.<ref>{{harvtxt|Ahuja|Magnanti|Orlin|1993}}, Application 12.1 Bipartite Personnel Assignment, pp. 463–464.</ref> A [[perfect matching]] describes a way of simultaneously satisfying all job-seekers and filling all jobs; [[Hall's marriage theorem]] provides a characterization of the bipartite graphs which allow perfect matchings. The [[National Resident Matching Program]] applies graph matching methods to solve this problem for [[Medical education in the United States|U.S. medical student]] job-seekers and [[Residency (medicine)|hospital residency]] jobs.<ref>{{citation
As a simple example, suppose that a set <math>P</math> of people are all seeking jobs from among a set of <math>J</math> jobs, with not all people suitable for all jobs. This situation can be modeled as a bipartite graph <math>(P,J,E)</math> where an edge connects each job-seeker with each suitable job. A perfect matching describes a way of simultaneously satisfying all job-seekers and filling all jobs; Hall's marriage theorem provides a characterization of the bipartite graphs which allow perfect matchings. The National Resident Matching Program applies graph matching methods to solve this problem for U.S. medical student job-seekers and hospital residency jobs.<ref>{{citation
举个简单的例子，假设一组人都在一组工作中找工作，并不是所有的人都适合所有的工作。这种情况可以模拟为一个二部图 < math > (p，j，e) </math > 其中一条边连接每个求职者和每个合适的工作。完美匹配描述了一种同时满足所有求职者和填补所有工作岗位的方法; 霍尔的婚姻定理提供了二部图的角色塑造，这些图允许完美匹配。国家住院医生匹配计划(National Resident Matching Program)应用图形匹配方法来解决美国医学生求职者和医院住院医生工作的这一问题。< ref > { citation
|last = Robinson
|last = Robinson
| last = Robinson
|first = Sara
|first = Sara
第一名: 莎拉
|date = April 2003
|date = April 2003
| date = April 2003
|issue = 3
|issue = 3
第三期
|journal = SIAM News
|journal = SIAM News
日志 = SIAM 新闻
|page = 36
|page = 36
36
|title = Are Medical Students Meeting Their (Best Possible) Match?
|title = Are Medical Students Meeting Their (Best Possible) Match?
| title = 医学生是否达到了他们的(最佳可能的)匹配？
|url = http://www.siam.org/pdf/news/305.pdf
|url = http://www.siam.org/pdf/news/305.pdf
Http://www.siam.org/pdf/news/305.pdf
|access-date = 2012-08-27
|access-date = 2012-08-27
| access-date = 2012-08-27
|archive-url = https://web.archive.org/web/20161118115832/http://www.siam.org/pdf/news/305.pdf
|archive-url = https://web.archive.org/web/20161118115832/http://www.siam.org/pdf/news/305.pdf
| archive-url = https://web.archive.org/web/20161118115832/http://www.siam.org/pdf/news/305.pdf
|archive-date = 2016-11-18
|archive-date = 2016-11-18
| archive-date = 2016-11-18
|url-status = dead
|url-status = dead
地位 = 死亡
}}.</ref>
}}.</ref>
} . </ref >
The [[Dulmage–Mendelsohn decomposition]] is a structural decomposition of bipartite graphs that is useful in finding maximum matchings.<ref>{{harvtxt|Dulmage|Mendelsohn|1958}}.</ref>
The Dulmage–Mendelsohn decomposition is a structural decomposition of bipartite graphs that is useful in finding maximum matchings.
Dulmage-Mendelsohn 分解是二部图的一种结构分解，它有助于找到最大匹配。
==Additional applications==
Bipartite graphs are extensively used in modern [[coding theory]], especially to decode [[codeword]]s received from the channel. [[Factor graph]]s and [[Tanner graph]]s are examples of this. A Tanner graph is a bipartite graph in which the vertices on one side of the bipartition represent digits of a codeword, and the vertices on the other side represent combinations of digits that are expected to sum to zero in a codeword without errors.<ref>{{citation
Bipartite graphs are extensively used in modern coding theory, especially to decode codewords received from the channel. Factor graphs and Tanner graphs are examples of this. A Tanner graph is a bipartite graph in which the vertices on one side of the bipartition represent digits of a codeword, and the vertices on the other side represent combinations of digits that are expected to sum to zero in a codeword without errors.<ref>{{citation
二部图在现代编码理论中得到了广泛的应用，特别是在信道码字的译码方面。因子图和坦纳图就是这方面的例子。图是一个二部图，其中一边的顶点代表一个码字的数字，另一边的顶点代表一个码字中期望和为零的数字组合。< ref > { citation
| last = Moon | first = Todd K.
| last = Moon | first = Todd K.
| last = Moon | first = Todd k.
| isbn = 9780471648000
| isbn = 9780471648000
9780471648000
| page = 638
| page = 638
638
| publisher = John Wiley & Sons
| publisher = John Wiley & Sons
2012年3月24日 | publisher = 约翰威立
| title = Error Correction Coding: Mathematical Methods and Algorithms
| title = Error Correction Coding: Mathematical Methods and Algorithms
| title = 纠错编码: 数学方法和算法
| url = https://books.google.com/books?id=adxb8CRx5vQC&pg=PA638
| url = https://books.google.com/books?id=adxb8CRx5vQC&pg=PA638
Https://books.google.com/books?id=adxb8crx5vqc&pg=pa638
| year = 2005}}.</ref> A factor graph is a closely related [[belief network]] used for probabilistic decoding of [[LDPC]] and [[turbo codes]].<ref>{{harvtxt|Moon|2005}}, p. 686.</ref>
| year = 2005}}.</ref> A factor graph is a closely related belief network used for probabilistic decoding of LDPC and turbo codes.
2005}}.因子图是一种密切相关的置信网络，用于 LDPC 码和 turbo 码的概率译码。
In computer science, a [[Petri net]] is a mathematical modeling tool used in analysis and simulations of concurrent systems. A system is modeled as a bipartite directed graph with two sets of nodes: A set of "place" nodes that contain resources, and a set of "event" nodes which generate and/or consume resources. There are additional constraints on the nodes and edges that constrain the behavior of the system. Petri nets utilize the properties of bipartite directed graphs and other properties to allow mathematical proofs of the behavior of systems while also allowing easy implementation of simulations of the system.<ref>{{citation
In computer science, a Petri net is a mathematical modeling tool used in analysis and simulations of concurrent systems. A system is modeled as a bipartite directed graph with two sets of nodes: A set of "place" nodes that contain resources, and a set of "event" nodes which generate and/or consume resources. There are additional constraints on the nodes and edges that constrain the behavior of the system. Petri nets utilize the properties of bipartite directed graphs and other properties to allow mathematical proofs of the behavior of systems while also allowing easy implementation of simulations of the system.<ref>{{citation
在计算机科学中，Petri 网是一种用于并发系统分析和仿真的数学建模工具。一个系统被建模为由两组节点组成的二分有向图: 一组包含资源的“位置”节点和一组生成和/或消耗资源的“事件”节点。在节点和边上有额外的约束，约束系统的行为。Petri 网利用二部有向图的性质和其他性质，允许对系统的行为进行数学证明，同时也允许容易地实现系统的模拟。< ref > { citation
| last1 = Cassandras | first1 = Christos G.
| last1 = Cassandras | first1 = Christos G.
1 = Cassandras | first1 = Christos g.
| last2 = Lafortune | first2 = Stephane
| last2 = Lafortune | first2 = Stephane
2 = Lafortune | first2 = Stephane
| edition = 2nd
| edition = 2nd
2nd
| isbn = 9780387333328
| isbn = 9780387333328
9780387333328
| page = 224
| page = 224
224
| publisher = Springer
| publisher = Springer
| publisher = Springer
| title = Introduction to Discrete Event Systems
| title = Introduction to Discrete Event Systems
| title = 离散事件系统导论
| url = https://books.google.com/books?id=AxguNHDtO7MC&pg=PA224
| url = https://books.google.com/books?id=AxguNHDtO7MC&pg=PA224
Https://books.google.com/books?id=axgunhdto7mc&pg=pa224
| year = 2007}}.</ref>
| year = 2007}}.</ref>
| year = 2007} . </ref >
In [[projective geometry]], [[Levi graph]]s are a form of bipartite graph used to model the incidences between points and lines in a [[configuration (geometry)|configuration]]. Corresponding to the geometric property of points and lines that every two lines meet in at most one point and every two points be connected with a single line, Levi graphs necessarily do not contain any cycles of length four, so their [[girth (graph theory)|girth]] must be six or more.<ref>{{citation
In projective geometry, Levi graphs are a form of bipartite graph used to model the incidences between points and lines in a configuration. Corresponding to the geometric property of points and lines that every two lines meet in at most one point and every two points be connected with a single line, Levi graphs necessarily do not contain any cycles of length four, so their girth must be six or more.<ref>{{citation
在射影几何中，Levi 图是二部图的一种形式，用来模拟配置中点和线之间的冲突。对应于点和线的几何性质，每两条直线最多相交一点，每两点与一条直线相连，Levi 图不一定包含任何长度为4的圈，所以它们的周长必须是6或更多。< ref > { citation
| last = Grünbaum | first = Branko | author-link = Branko Grünbaum
| last = Grünbaum | first = Branko | author-link = Branko Grünbaum
| last = Grünbaum | first = Branko | author-link = Branko Grünbaum
| isbn = 9780821843086
| isbn = 9780821843086
9780821843086
| page = 28
| page = 28
28
| publisher = [[American Mathematical Society]]
| publisher = American Mathematical Society
美国数学学会
| series = [[Graduate Studies in Mathematics]]
| series = Graduate Studies in Mathematics
数学研究生课程
| title = Configurations of Points and Lines
| title = Configurations of Points and Lines
| title = 点和线的配置
| url = https://books.google.com/books?id=mRw571GNa5UC&pg=PA28
| url = https://books.google.com/books?id=mRw571GNa5UC&pg=PA28
Https://books.google.com/books?id=mrw571gna5uc&pg=pa28
| volume = 103
| volume = 103
103
| year = 2009}}.</ref>
| year = 2009}}.</ref>
2009} . </ref >
==See also==
*[[Bipartite dimension]], the minimum number of complete bipartite graphs whose union is the given graph
*[[Bipartite double cover]], a way of transforming any graph into a bipartite graph by doubling its vertices
*[[Bipartite hypergraph]], a generalization of bipartiteness to [[hypergraph]]s.
*[[Bipartite matroid]], a class of matroids that includes the [[graphic matroid]]s of bipartite graphs
*[[Bipartite network projection]], a weighting technique for compressing information about bipartite networks
*[[Convex bipartite graph]], a bipartite graph whose vertices can be ordered so that the vertex neighborhoods are contiguous
*[[Multipartite graph]], a generalization of bipartite graphs to more than two subsets of vertices
*[[Parity graph]], a generalization of bipartite graphs in which every two [[induced path]]s between the same two points have the same parity
*[[Quasi-bipartite graph]], a type of Steiner tree problem instance in which the terminals form an independent set, allowing approximation algorithms that generalize those for bipartite graphs
*[[Split graph]], a graph in which the vertices can be partitioned into two subsets, one of which is independent and the other of which is a clique
*[[Zarankiewicz problem]] on the maximum number of edges in a bipartite graph with forbidden subgraphs
==References==
{{Reflist|colwidth=30em}}
==External links==
* {{springer|title=Graph, bipartite|id=p/g044880}}
* [http://www.graphclasses.org/ Information System on Graph Classes and their Inclusions]: [http://www.graphclasses.org/classes/gc_69.html bipartite graph]
* {{mathworld | title = Bipartite Graph | urlname = BipartiteGraph}}
* [https://academic.oup.com/gigascience/article/7/4/giy014/4875933/ Bipartite graphs in systems biology and medicine]
[[Category:Graph families]]
Category:Graph families
类别: 图族
[[Category:Bipartite graphs| ]]
[[Category:Parity (mathematics)]]
Category:Parity (mathematics)
分类: 奇偶校验(数学)
<noinclude>
<small>This page was moved from [[wikipedia:en:Bipartite graph]]. Its edit history can be viewed at [[二分图/edithistory]]</small></noinclude>
[[Category:待整理页面]]