完美图定理

✍ dations ◷ 2025-04-26 12:39:46 #图论,完美图

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

相关

  • 法拉法拉(英语:farad)是电容的国际单位,简称法,单位符号为F。是一种国际单位制导出单位,是以发现电磁感应现象的英国物理学家迈克尔·法拉第(Michael Faraday)的名字而命名的。由
  • 酶原有些酶在刚分泌时是没有催化活性的,这种没有活性的前体物称为酶原。一般生物体会通过肽键的剪切改变酶的构象使酶的活性中心形成或暴露出来而使酶具有活性。酶原的生理意思使
  • 意识社区意识社区(英语:Intentional community),又译为共识社区 (中国)|共识社区]],意愿性社区一种社区聚落,根据团体凝聚力与团队合作而形成。这类型的社区居民,通常拥有类似的社会,政治,宗
  • 费托合成费托合成(Fischer–Tropsch process),又称F-T合成,是以合成气(一氧化碳和氢气的混合气体)为原料在催化剂和适当条件下合成以液态的烃或碳氢化合物(hydrocarbon)的工艺过程。在1925年
  • 广西平话广西平话是中国广西、广东、湖南、云南部分地区的若干类方言的笼统称谓。分南部平话(桂南平话)和北部平话(桂北平话)两大类。桂南平话内部比较一致,具有某些粤语特征,与粤语勾漏片
  • 梦游梦游症(Somnambulism),在神经学上是一种睡眠障碍,症状一般为在半醒状态下在居所内走动,但有些患者会离开居所或作出一些危险的举动,如翻窗、开车甚至一些暴力活动,如杀人等。1846年
  • 施莱辛格施莱辛格(Schlesinger)可以指:
  • 自由落体自由落体运动是指只受重力作用(不存在空气阻力的理想状态)的均匀加速度运动过程。 运动过程中重力势能与动能之和遵守机械能守恒定律。在地球上相同位置与相同高度,自由落体的
  • 黄维 (光电子专家)黄维(1963年5月-),河北唐山人,中国有机光电子专家,西北工业大学常务副校长。1983年毕业于北京大学,1992年在北京大学获博士学位。2011年当选为中国科学院院士。
  • 芭贝尔·柯夫勒芭贝尔·柯夫勒(德语:Bärbel Kofler,1967年5月24日-)是一名德国社会民主党的联邦议员。自2016年3月起,她担任德国联邦政府人权政策与人道援助办公室专员(德语:Beauftragter der Bun