完美图定理

✍ dations ◷ 2025-08-13 02:26:31 #图论,完美图

在图论中,完美图定理(由洛瓦兹·拉兹洛证明László Lovász (1972a, 1972b))断言:一个无向图是完美的当且仅当其补图也是完美的。这个结论一度是Claude Berge(英语:Claude Berge)提出的猜想。它有时也被称为弱完美图定理,以和强完美图定理作区分。强完美图定理通过禁止导出子图来刻画完美图。

一个完美图是具有下述性质的无向图:在其每个导出子图中,最大团的顶点数都等于对该导出子图的着色的颜色数的最小值。完美图包括了很多重要类型的图,例如二分图、弦图和可比图(英语:comparability graph)。

一个图的补图在某两个顶点之间连一条边当且仅当原图在这两个顶点之间没有连边。从而原图中的团成为其补图中的独立集,而原图的一个染色成为其补图的一个团覆盖。

完美图定理断言:完美图的补图也是完美的。

等价地,在完美图中,最大独立集的顶点数等于其团覆盖中团个数的最小值。

令是一个长度为大于3的奇数的循环图(洞),则G的任何染色需要至少3种颜色,但G不含有三角形,所以它不是完美的。由完美图定理,G的补图(一个奇数长度的反洞)肯定也不是完美的。如果G是一个长度为5的圈,则它是一个自补图(英语:Self-complementary graph),但此性质对更大的奇数长度不再成立,而对于奇数个顶点的反洞计算其团数和色数也不像对于奇数个顶点的循环图那么容易。强完美图定理指出,奇数长度的洞和反洞是完美图的最小的禁止导出子图。

在一个非平凡的二分图中,由定义染色所需的颜色数最小是2,而由于二分图中不含有三角形,其团数也是2。而二分图的任何导出子图还是二分图。所以二分图是完美的。在有n个顶点的二分图中,一个最小团覆盖需要一个最大匹配加上另一些团,每个对应于一个未匹配顶点,其中团的个数等于n-M,这里M是最大匹配的边数。于是在这个例子中完美图定理可以推出柯尼希定理 (图论),即有n个顶点的二分图的最大独立集的顶点数也是n-M

Chudnovsky等人(2006)得到的强完美图定理断言一个图是完美的当且仅当其所有导出子图和它们的补图都不是长度为大于等于5的奇数的循环图。由于此条件在取补图后不变,强完美图定理可以直接推出(弱)完美图定理。

Cameron, Edmonds & Lovász(1986)证明,如果一个完全图的所有边被分成三个导出子图,使得任何三个顶点都在其中一个导出子图中连通,且两个导出子图是完美的,则第三个导出子图必然也是完美的。完美图定理是这个结果在其中一个导出子图是空图时的特例。

相关

  • 烟酸维生素 B3,维生素 PP烟酸(英语:niacin、nicotinic acid,也称维他命B3、维他命PP、吡啶-3羧酸),分子式:C6H5NO2,耐热,能升华。首次描述于Hugo Weidel于1873年对尼古丁的研究。它是人体
  • 对比浴对比浴(contrast bath therapy),又称为冷热交替疗法(Hot/Cold Immersion therapy),。属于物理治疗中水疗的特殊疗法之一。 由于水温低时会使皮肤下的血管收缩,而水温高时则会使血
  • 克劳迪奥·蒙台威尔第克劳迪奥·乔瓦尼·安东尼奥·蒙特威尔第(意大利语:Claudio Giovanni Antonio Monteverdi,1567年5月15日-1643年11月29日),意大利作曲家、制琴师。出生于意大利北部克雷莫纳市的他
  • 美国宪法第一修正案宪法正文I ∙ II ∙ III ∙ IV ∙ V ∙ VI ∙ VII其它修正案 XI ∙ XII ∙ XIII ∙ XIV ∙ XV XVI ∙ XVII ∙ XVIII ∙ XIX ∙ XX XXI ∙ XXII ∙ XXIII ∙
  • 宫颈息肉宫颈息肉(英语:cervical polyp)是一种常见的原发型息肉或肿物,通常生长于子宫颈管(英语:Canal of the cervix)表面。并发原因不明,但与宫颈炎相关。慢性炎症长期刺激使宫颈管局部黏
  • 维多利亚尼罗河白尼罗河(阿拉伯语:النيل الأبيض‎,英语:White Nile)是尼罗河的两条主要支流之一(另外一条是青尼罗河)。狭义上,白尼罗河发源于诺湖杰贝勒河和加扎勒河的汇流处;广义上,白
  • 赵 钥赵钥,字阆仙,山东莱阳县人,清朝政治人物。顺治十五年(1658年)戊戌科进士,官至太常寺少卿。工诗,有《因树屋集》。
  • 亚洲地区八纮一宇是大日本帝国第二次世界大战时期的国家格言,日本政府宣传部门的解释是天下一家、世界大同的意思,但在当时的氛围下,实质上是服务军方的侵略扩张政策,从军备、政治体制、
  • 闵希豪森男爵闵希豪森男爵(德语:Baron Münchhausen)是德国作家鲁道尔夫·埃里希·拉斯伯创造的一个虚构人物,原型是一个德国贵族。他是一个“吹牛大王”,他参军回家后,向人们讲述了很多虚构的
  • 卡蒂诺·莫布里卡蒂诺·拉肖恩·莫布利(英语:Cuttino Rashawn Mobley,1975年9月1日-),美国NBA联盟前职业篮球运动员。他在1998年的NBA选秀中第2轮第41顺位被休斯顿火箭选中。因罹患肥厚性心肌症