526
个编辑
更改
跳到导航
跳到搜索
第73行：
第73行： − + − + − +
→Examples 案例
* Every [[planar graph]] whose [[Glossary of graph theory#Genus|faces]] all have even length is bipartite. 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. 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个相邻点。
* 在平面图中，所有面都具有偶数条边，该图为二分图。特殊情况是网格图和方图，其中每个内面都有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.
* 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>'''。冠图是将一个完全二分图中所有的完美匹配连边去掉后形成的。
* [[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.
* [[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.
* '''<font color="#ff8000"> 超立方体图Hypercube graph</font>'''，'''<font color="#ff8000"> 局部立方体Partial cube</font>'''和'''<font color="#ff8000"> 中位数图Median graph</font>'''均为二分图。判别方法是将这些图中的顶点用'''<font color="#ff8000"> 位向量Bitvector</font>'''（二进制位组成的向量）进行标记，然后对比其中两个顶点的位向量，发现当且仅当位向量中只有一个位元是不同的时候，该两个顶点相邻。另外判定该图的二分性可以通过观察每个顶点的位向量，奇数位向量和偶数位向量分别为该图的二分顶点子集。树图和方图都是中位数图，而所有中位数图都是局部立方体。
* '''<font color="#ff8000"> 超立方体图Hypercube graph</font>'''，'''<font color="#ff8000"> 局部立方体Partial cube</font>'''和'''<font color="#ff8000"> 中位数图Median graph</font>'''均为二分图。判别方法是将这些图中的顶点用'''<font color="#ff8000"> 位向量Bitvector</font>'''（二进制位组成的向量）进行标记，然后对比其中两个顶点的位向量，发现当且仅当位向量中只有一个位元是不同的时候，该两个顶点相邻。另外判定该图的二分性可以通过观察每个顶点的位向量，奇数位向量和偶数位向量分别为该图的二分顶点子集。树状图和方图都是中位数图，而所有中位数图都是局部立方体。
== Properties 属性 ==
== Properties 属性 ==