二分图

维基百科,自由的百科全书
跳转至: 导航搜索
二分圖的範例

二分图又稱雙分圖二部图偶图,指頂點可以分成兩個不相交的( and 皆为独立集英语Independent_set_(graph_theory)independent sets),使得在同一個集內的頂點不相鄰(沒有共同邊)的

二分图又称作二部图,是图论中的一种特殊模型。 设 是一个无向图,如果顶点V可分割为两个互不相交的子集 ,并且图中的每条边 所关联的两个顶点 分别属于这两个不同的顶点集 ( in , in ),则称图 为一个二分图。

无向图 为二分图的充分必要条件是, 至少有两个顶点,且其所有回路的长度均为偶数。

可以将 当做 着色图 中所有节点为蓝色, 中所有节点着绿色,每条边的两个端点的颜色不同,符合图着色问题的要求[1][2]。相反,用这样的着色方式对非二分图是行不通的,根据triangle:其中一个顶点着蓝色并且另一个着绿色后,三角形的第三个顶点与上述具有两个颜色的顶点相连,无法再对其着蓝色或绿色。

二分图的一种描述方式为:,表示有独立顶点集 ,以及边 组成的图。假如一个二分图不是连通图,其可能包含多个二分图;[3]这种情况下, 有利于指定应用中一个特定的二分图。如果(这两个子集有相同的),那么 称为平衡二分图。[1]如果二分图同一侧的顶点有相同的 degree,那么 是一个biregular

给定一个二分图 ,在 的一个子图 中, 的边集中的任意两条边都不依附于同一个顶点,则称 是一个匹配。

特性[编辑]

  • 最小邊覆蓋集的基數等於最大獨立集的基數
  • 最大獨立集的基數與最大匹配的基數之和,等於頂點數目
  • 連通的二部圖:
    • 最小頂點覆蓋集的基數等於最大匹配的基數

圖為二分图若且唯若[编辑]

参考资料[编辑]

  1. ^ 1.0 1.1 Asratian, Denley & Häggkvist (1998), p. 7.
  2. ^ Scheinerman, Edward R., Mathematics: A Discrete Introduction 3rd, Cengage Learning: 363, 2012, ISBN 9780840049421 .
  3. ^ Chartrand, Gary; Zhang, Ping, Chromatic Graph Theory, Discrete Mathematics And Its Applications 53, CRC Press: 223, 2008, ISBN 9781584888000 .

參見[编辑]