二分图

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

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

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

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

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

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

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

特性[编辑]

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

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

参考资料[编辑]

  1. ^ 丁致良. 離散數學. 台灣: 秀才書屋. 2014. ISBN 9789572928097 (繁體中文). 
  2. ^ 2.0 2.1 Asratian, Denley & Häggkvist (1998), p. 7.
  3. ^ Scheinerman, Edward R., Mathematics: A Discrete Introduction. 3rd, Cengage Learning. 2012:  363, ISBN 9780840049421 .
  4. ^ Chartrand, Gary; Zhang, Ping, Chromatic Graph Theory, Discrete Mathematics And Its Applications, 53, CRC Press. 2008:  223, ISBN 9781584888000 .

參見[编辑]