跳转到内容

二分图:修订间差异

维基百科,自由的百科全书
删除的内容 添加的内容
标签移动版编辑 移动应用程序编辑 Android应用编辑
标签移动版编辑 移动应用程序编辑 Android应用编辑
第62行: 第62行:


===完美圖===
===完美圖===
所有的二分圖和二分圖的[[線圖]],以及它們的[[補圖]]都是[[完美圖]]。很明顯的,二分圖是完美圖,因為他的著色數和最大點團數皆為 2,但另一方面,二分圖的補圖的完美性是相對難以證明的,該性質等價於前面小節的倒數第二個敘述。類似的,二分圖的線圖的補圖的完美性等價於柯尼希定理的敘述,這也是會如此定義完美圖的動機之一。而最後剩下的,是二分圖的線圖的完美性,而這個等價於柯尼希於早些年證明出的定理:二分圖的[[圖著色問題|邊著色數]]等於頂點最大度數。

最小[[邊覆蓋]]集的[[基数 (数学)|基數]]等於最大[[獨立集]]的基數
最小[[邊覆蓋]]集的[[基数 (数学)|基數]]等於最大[[獨立集]]的基數


* 連通的二部圖:
* 連通的二部圖:
** 最小頂點覆蓋集的基數等於最大
** 最小頂點覆蓋集的基數等事實上,於最大


==参考资料==
==参考资料==

2019年2月28日 (四) 08:02的版本

二分圖的範例

二分图又稱雙分圖二部图偶图,指頂點可以分成兩個互斥的独立集,也就是在任兩個同在的頂點不相鄰。

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

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

可以将 当做一個着色 中所有頂點为蓝色, 中所有頂點着绿色,每条边的两个端点的颜色不同,符合图着色问题的要求[1][2]。相反的,非二分圖無法被二著色,例如 (3 個頂點的完全圖),將其中一个顶点着蓝色并且另外一个着绿色后,第三个顶点与上述具有两个颜色的顶点相连,无法再对它着蓝色或绿色。

二分图的一种描述方式为:,包含了独立集 ,以及边 的資訊。假如不是连通图,可能有多種將所有頂點分成 的方式[3];在特定的應用場合中,將頂點的兩部分寫出來是有必要的。如果,則 称为平衡二分图[1]。如果二分图 以及 的顶点分別有相同的度數,則 被稱為是雙正則的英语Bipartite graph

给定一个二分图 ,在 的一个子图 中, 的边集中的任意两条边都沒有共同的端点,则称 是一个匹配

例子

二分圖經常出用來研究兩種不同類型的物件之間的關係。例如,如果要討論足球球員和球隊的關係,可以畫一個二分圖,頂點的兩部分分別是所有球員和所有球隊,如果球員受僱於球隊,則在二者之間連邊。這種二分圖模型叫做附屬網絡英语affiliate network,經常用於社會網絡分析英语social network analysis

另一個例子出現在鐵路規畫問題:給定許多班火車及許多車站,每輛火中途停靠的站不盡相同,問最少個數的車站集合使得每輛火車都停靠至少一個集合中的車站。以圖論的觀點來看,將火車和車站視為頂點,火車有停靠車站則連邊,問題轉化成是二分圖的點覆蓋問題,而事實上,這個問題的難度是NP完全的。

第三個例子出現在古幣學,古代的硬幣有正面及反面之分,不同時期和地區的政府會使用不同的正反面組合,因此,將所有可能的組合畫成圖就是一個二分圖的結構。

其他一般性的例子諸如:

中間圖英语median cube都是二分圖,而且它們的頂點可以被看做是位元向量英语bit vector(一串由0和1組成的字串),使得兩個頂點連邊若且唯若它們只有一個位元是相異的,而它們的二分性的驗證可以藉由考慮兩個獨立集是分別蒐集所有擁有奇數和偶數個1的位元向量。此外,所有的樹和四邊形圖都是中間圖,而所有的中間圖都是部分超方形圖。

特性

匹配的基數。

等價條件

  • 一個圖是二分圖若且唯若它不包含奇作為子圖。
  • 一個圖是二分圖若且唯若它的著色數是 2。
  • 一個圖是二分圖若且唯若它的频谱是正負對稱的。

柯尼希定理

柯尼希定理於1931年,由匈牙利數學家德內斯·柯尼希提出:

一個圖是二分圖若且唯若它的最小頂點覆蓋的頂點數等於最大匹配的邊數。

該定理有一個等價形式,一個圖是二分圖若且唯若它的最大獨立集的頂點數與最大匹配的邊數之和,等於總頂點個數。再配合一個性質,一個沒有孤立頂點的圖會滿足最小邊覆蓋的邊數加上最大匹配的邊數等於總頂點個數,我們有對任何沒有孤立頂點的二分圖,最小邊覆蓋的邊數等於最大獨立集的頂點數,以及最小邊覆蓋的邊數加上最小頂點覆蓋的頂點數等於總頂點數。

完美圖

所有的二分圖和二分圖的線圖,以及它們的補圖都是完美圖。很明顯的,二分圖是完美圖,因為他的著色數和最大點團數皆為 2,但另一方面,二分圖的補圖的完美性是相對難以證明的,該性質等價於前面小節的倒數第二個敘述。類似的,二分圖的線圖的補圖的完美性等價於柯尼希定理的敘述,這也是會如此定義完美圖的動機之一。而最後剩下的,是二分圖的線圖的完美性,而這個等價於柯尼希於早些年證明出的定理:二分圖的邊著色數等於頂點最大度數。

最小邊覆蓋集的基數等於最大獨立集的基數

  • 連通的二部圖:
    • 最小頂點覆蓋集的基數等事實上,於最大

参考资料

  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 .

參見