完美图定理

✍ dations ◷ 2025-07-19 07:02:56 #图论,完美图

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

相关

  • SATC代码S(感觉器)是解剖学治疗学及化学分类系统的一个分类,这是由世界卫生组织药物统计方法整合中心(The WHO Collaborating Centre for Drug Statistics Methodology)所制定的药
  • 倭马亚王朝倭马亚王朝(阿拉伯语:أمويون‎),或译为伍麦叶王朝、奥米雅王朝、奥玛雅王朝,在古中国《旧唐书》中被称为白衣大食,是由倭马亚家族统治的哈里发国,是阿拉伯帝国的第一个世袭王
  • 回避型人格障碍回避性人格障碍(英语: Avoidant Personality Disorder; 简称AvPD或APD),或译畏避型人格障碍、逃避型人格障碍、畏惧型人格违常,属于人格障碍的一种。因为害怕在别人面前丢脸,此类
  • 5f14 7s2 7p12, 8, 18, 32, 32, 8, 3第一:478.6 kJ·mol−1 第二:1428.0 kJ·mol−1 第三:2219.1 kJ·mol六方密堆积主条目:铹的同位素铹符号Lr,元素之一,原子序103,为一人工合成
  • 感染性海绵状脑病传染性海绵状脑病(英语:transmissible spongiform encephalopathies, TSEs),又译为传播性海绵样脑症。而其它常见名称为普利昂疾病或朊毒体疾病(Prion diseases)。是一种会影响人
  • 莱格特安东尼·莱格特爵士,KBE,FRS(英语:Sir Anthony Leggett,1938年3月26日-),英国物理学家,2003年获诺贝尔物理学奖。莱格特教授在低温物理的理论作为世界领先的广泛认可。他塑造了正常和
  • 秦岭细鳞鲑秦岭细鳞鲑(学名:Brachymystax lenok tsinlingensis)也称花鱼、梅花鱼、金板鱼、闾花鱼、五色鱼、闾鱼等,是细鳞鲑的一个亚种。 为中国的特有种,主要分布于秦岭两侧渭河上游及其
  • 濒危野生动植物物种国际贸易公约《濒危野生动植物物种国际贸易公约》(英语:Convention on International Trade in Endangered Species of Wild Fauna and Flora,缩写:CITES)是一个在1963年时由“国际自然与天然
  • 清龈颚塞擦音清龈颚塞擦音是辅音的一种,在国际音标中以表示,有时也会写成(非正式写法),在X-SAMPA中以表示。在汉语、日语、韩语、泰语、克罗地亚语、塞尔维亚语中均有此发音。清龈颚塞擦音特
  • 卡努里语卡努里语(英语:Kanuri)是一种于尼日利亚,尼日尔,乍得和喀麦隆地区,共4百万人使用的方言连续体,于利比亚南部的少数民族及散居于苏丹的人也皆有使用。它属于尼罗-撒哈拉语系中的撒哈