961
个编辑
更改
跳到导航
跳到搜索
第69行：
第69行： + + + + + − −
→Examples 案例
更多抽象的例子:
更多抽象的例子:
* 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. 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 属性 ==