完美图定理

✍ dations ◷ 2025-11-29 23:47:32 #图论,完美图

在图论中,完美图定理(由洛瓦兹·拉兹洛证明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)证明,如果一个完全图的所有边被分成三个导出子图,使得任何三个顶点都在其中一个导出子图中连通,且两个导出子图是完美的,则第三个导出子图必然也是完美的。完美图定理是这个结果在其中一个导出子图是空图时的特例。

相关

  • 接合孢子接合孢子是接合菌的有性孢子,由菌丝长出形态相同或略有不同地配子囊接合而成。接合孢子是由菌丝生出的结构基本相似,形态相同或略有不同的两个配子囊接合而成。首先,两个化学
  • 失乐失乐(英语:Anhedonia)是指对原本能够带来快乐的活动(爱好、社交、交媾等)失去兴趣的现象。虽然早期对于失乐的定义强调“快感”,近年来人们更多地强调需要考虑这些快感行为的其他
  • 轻度狂躁轻度狂躁,英文Hypomania,是指一个人持续升高(欣快)或者急躁的心境状态以及在这个状态之下产生的相应的想法或者行为。许多轻度狂躁者都有性欲亢进的表现。一个人处于轻度狂躁状
  • 聚德霍夫托马斯·聚德霍夫(德语:Thomas C. Südhof,1955年12月22日-),美籍德国生物化学家,以研究突触传递知名。聚德霍夫生于德国哥廷根。童年时光在哥廷根与汉诺威度过。年轻时曾学习过音
  • 托莱多托莱多(西班牙语:Toledo,西班牙语:.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","Code2000","Gentium"
  • 山猫山猫可以指:
  • 语意所指(英语:signifié),在语言学上,指发出讯息者想要表示或传达给发现者或接收者的理念;亦或发现者或接收者由该语境所推断的结果。在大多数语言中,有些字往往会有多种不同涵义;因此
  • 亚洲诺贝尔奖得主列表诺贝尔奖是自1901年开始颁发的年度国际奖项,颁发给对化学、物理、文学、和平和生理及医学这五方面有着杰出贡献的人士或组织。诺贝尔经济学奖则是于1968年设立,以表扬在经济方
  • 埃及第九王朝第 八第 十埃及第九王朝(英文:Ninth dynasty of Egypt)为埃及历史上的一个朝代,确切时间可能在前2160年—前2130年,是一个短暂的王朝,建立后不久灭亡,接替它的是第十王朝。都城在底
  • 金弼淳金弼淳(韩语:김필순,1878年-1919年),朝鲜半岛最早拥有行医执照的西医,世福兰斯医学院最早的韩方负责人,韩国独立运动家,中国第一位影帝金焰的父亲。:30-33:156-157:175金弼淳1878年出