961
个编辑
更改
跳到导航
跳到搜索
第39行：
第39行： − + − + − 当建立两类不同对象之间的模型关系时，二部图往往自然而然地出现。例如，一个足球运动员和俱乐部的图，如果一个运动员为一个俱乐部效力，那么该运动员和俱乐部之间就有一条边，这是一个隶属关系网络的自然例子，这是一种用于社会网络分析的二部图。+ − + − + − 二部图自然出现的另一个例子是在(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. − − 每一对车站和停在那个车站的火车。 第67行：
第61行： − 第三个例子是钱币学领域。古代硬币的制作是基于对设计的正面印象(正面与背面)。钱币收藏家制作的表示硬币产量的图表是二部图。+ 第75行：
第69行： − 更抽象的例子包括:+ + + + + + + +
→Examples
== Examples ==
== 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]].
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]].
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
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.
在建立两类不同对象之间的关系时，二分图往往自然而然地就出现了。比如说足球运动员和俱乐部的关系图，如果该球员曾为该俱乐部效力，则在运动员和俱乐部之间就形成了一条连边，这是隶属关系网络的示例。在社交网络分析中，隶属关系便形成一种二分图。
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 each pair of a station and a train that stops at that station.[7]
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 each pair of a station and a train that stops at that station.[7]
二分图自然形成的另一个例子是（NP-完全问题）铁路优化问题，其中输入的是火车的时间表及其停靠点，目标是找到尽可能小的火车站集合，以便每个火车都可以停靠至少一个选定的火车站。这个问题可以被建模为一个二分图中的主导集合问题，该图中每辆列车和每个车站都被看作是一个顶点，而当某列车停靠在某车站的时候，其形成的关系被视为一条连边。
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.
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"/>
* Every [[tree (graph theory)|tree]] is bipartite.<ref name="s12"/>
每棵树都是二分的。
* [[Cycle graph]]s with an even number of vertices are 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.
* 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.
平面图（图论）中，所有面都具有偶数条边的平面图是二分的。特殊情况是网格图和方图，其中每个内面都由4个边组成，每个内顶点都有4个或更多的相邻点。
* 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.
* 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.
在一个完全二分图中，分别有由m和n的顶点（用Km,n表示）组成的两个不相交的集合U和V，连边E由分别在集合U和V的两个顶点连接。该二分图表示为G =（U，V，E），并且具有mn条边。另外完全二分图还包含一个特例，那就是冠图Crown graphs。冠图是通过将一个完全二分图中所有的完美匹配连边去掉形成的。
* [[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>
* [[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==
==Properties==