完美图定理

✍ dations ◷ 2025-06-08 11:00:04 #图论,完美图

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

相关

  • University of Minnesota明尼苏达大学双城分校(英语:University of Minnesota, Twin Cities),是位于美国明尼苏达州双城区(即明尼阿波利斯及圣保罗)的一所公立大学,为明尼苏达大学系统历史最悠久,规模最大的
  • 集体协商集体协商是一个雇主和雇员团体之间敲定薪资范围、工作环境、福利及其它雇员权利的过程。雇员的权益通常由其所属的工会代表。通过集体协商,雇主会与雇员团体之间达成一个设定
  • 计算机工程计算机工程(英语:Computer engineering)一个以电机工程学和计算机科学的部分交叉领域为内容的工程学,其主要任务是设计及实现计算机系统。计算机工程师通常受过专业的电子工程(或
  • bspan style=color:yellow;②/span/b阿克罗蒂里和泽凯利亚主权基地区(英语:Sovereign Base Areas of Akrotiri and Dhekelia)是两个位于地中海极东部岛屿塞浦路斯上的英国特殊属地,共同组成了主权基地区,其中阿克罗
  • 印度标准时间印度标准时间(Indian Standard Time - IST)是在印度全国使用的标准时间,即UTC+5:30。印度的标准时间以通过安拉阿巴德(北方邦城市)东边的东经82.5度做为基准,与格林威治标准时间相
  • 水晶之夜纳粹集中营转移营比利时:布伦东克堡垒 · 梅赫伦转移营法国:居尔集中营 · 德朗西集中营意大利:波尔查诺转移营荷兰:阿默斯福特集中营 · 韦斯特博克转移营挪威:法斯塔德集中营部
  • 否认怀孕否认怀孕是一种少见的情形,是指孕妇否认(英语:denial)自身怀孕的事实。一研究显示否认怀孕的孕妇比例约占孕妇人口的0.26%。否认怀孕和秘密怀孕不同,秘密怀孕的孕妇不知道自身怀
  • Bonaparte夏尔·吕西安·儒勒·劳伦·波拿巴,第二代卡尼诺和穆西格纳诺亲王(法语:Charles Lucien (Carlo) Jules Laurent Bonaparte, 2nd Prince of Canino and Musignano,1803年5月24日-1
  • 欢乐谷战争欢乐谷战争(英语:Pleasant Valley War),或称为当图盆地之争(英语:Tonto Basin Feud)及当图盆地战争(英语:Tonto Basin War),是1882年至1892年间美国两个畜牧家族之间的一场武装私斗。19
  • 四川并殖吸虫四川并殖吸虫(学名:Paragonimus szechuanensis)为并殖科并殖属的动物。在中国大陆,分布于四川、云南、陕西等地,营寄生生活,终末宿主猫、犬、野猫、人工感染终末宿主猫、犬、大白