961
个编辑
更改
无编辑摘要
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 | 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.
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 | 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.
通常可以将集合''U''和集合''V''视为被着色的两个图集：如果其中一个所有顶点为蓝色，另外一类为绿色，那么每条连边的两端必须具有不同的颜色。这是二分图必须满足的条件。相反，在非二分图（例如三角形）的情况下，这种着色要求变得不可能：因为一个顶点为蓝色，另一个为绿色，其三角形剩下的第三个顶点将需要同时连接这两个颜色，明显这是无法达到，因为它违背了初始要求：二分图中所有顶点必须分为两个不相交且独立的集合''U''和''V''。即第三个顶点必须为两个颜色当中的一个。
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 | 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.
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 | 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.
对于二分图常用的表达方式是''G=(U,V,E)''，其中''U''和''V''分别代表顶点子集，''E''代表二分图中的连边。如果有一个二分图内部不连通，则它可能具有多个二分图；在这种情况下，''(U,V,E)''标注将有助于指定一个特殊的二分图。在实际的应用当中，这无比重要。如果''|U|=|V|''，即这两个子集具有相同的基数，此时''G''被称为'''<font color="#ff8000"> 均衡二分图Balanced bipartite graph</font>'''。如果在二分图中同一侧（同一个子集）所有的顶点都具有相同的度数，则''G''被称为'''<font color="#ff8000"> 双正则二分图Biregular</font>'''。
* 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.
* 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.
* 在一个完全二分图中，分别有由m和n的顶点（用Km,n表示）组成的两个不相交的集合U和V，连边E由分别在集合U和V的两个顶点连接。该二分图表示为G =（U，V，E），并且具有mn条边。另外完全二分图还包含一个特例，那就是'''<font color="#ff8000"> 冠图Crown graphs</font>'''。冠图是通过将一个完全二分图中所有的完美匹配连边去掉形成的。
* 在一个完全二分图中，分别有由''m''和''n''的顶点（用''Km,n''表示）组成的两个不相交的集合''U''和''V''，连边''E''由分别在集合''U''和''V''的两个顶点连接。该二分图表示为''G =（U，V，E）''，并且具有''mn''条边。另外完全二分图还包含一个特例，那就是'''<font color="#ff8000"> 冠图Crown graphs</font>'''。冠图是通过将一个完全二分图中所有的完美匹配连边去掉形成的。