完美图定理

✍ dations ◷ 2025-11-04 23:50:34 #图论,完美图

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

相关

  • 前臂前臂指的是靠近手的部分。医护人员在对人体进行健康检查时,通常都是从前臂开始找血管打针的。人的左右手都有前臂。另外,前臂也常用在比腕力上,腕力的力量几乎都是从前臂开始出
  • 亚硝酸根亚硝酸盐(Nitrite,NO2−)是亚硝酸组成的盐,主要指亚硝酸钠(NaNO2),含有亚硝酸根离子,化学式NO2−,有一对称阴离子与同等的N–O键长和大约120度的O–N–O键角。亚硝酸盐可被氧化或还原
  • 黄铁矿黄铁矿,主要成分是二硫化亚铁FeS2,是提取硫、制造硫酸的主要矿物原料。其特殊的形态色泽,有观赏价值。一些黄铁矿磨制成宝石也很受欢迎。黄铁矿可经由岩浆分结作用、热水溶液或
  • 弟妇姻亲指基于婚姻关系而生之亲属型态,一方配偶与他方配偶之亲属间,因双方缔结婚姻后,成为相互具法律上亲属关系的情况。《中华民国民法》第969条规定,包括配偶的血亲、血亲的配偶
  • 内克塔内布二世内克塔内布二世(英语:Nectanebo II)埃及第三十王朝末任法老(公元前360年—公元前343年在位),也是最后一个埃及本土出身的法老,于斯巴达国王阿格西劳斯二世协助下篡夺塔科斯王位。他
  • 加拉赫集团加拉赫集团(英语:Gallaher Group),英国大型跨国烟草集团,今日本烟草产业公司旗下子公司。加拉赫集团在2007年4月为日本烟草产业公司收购以前,曾是全球第五大香烟制造商,并曾在伦敦
  • 世界之窗世界之窗可以指:
  • 禹王台禹王台位于河南省开封市城外东南方,占地400多亩,是古代梁园的遗址。禹王台又称古吹台,传说春秋时期晋国有一位双目失明的音乐家名叫师旷,他的音乐造诣很深,是晋平公驾下的一名乐
  • 轮状病毒疫苗轮状病毒疫苗 是用于预防轮状病毒感染的疫苗。 轮状病毒是造成孩童腹泻的最主要原因。 轮状病毒疫苗在发展中国家预防了15%到34%的严重腹泻;在发达国家避免了37%到96%的严重
  • 布鲁诺·拉图尔布鲁诺·拉图尔(法语:Bruno Latour,法语发音:.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","Code2000"