完美图定理

✍ dations ◷ 2025-12-04 19:16:18 #图论,完美图

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

相关

  • 欧阳予欧阳予(1927年7月26日-),中国核反应堆及核电工程专家。1927年生于四川乐山。1948年毕业于国立武汉大学工学院电机系。1957年获苏联莫斯科动力学院技术科学博士学位。2000年当选
  • 高雄 (消歧义)高雄可以指:
  • 海顿弗朗茨·约瑟夫·海顿(德语:Franz Joseph Haydn,1732年3月31日-1809年5月31日),又译海登、海典、偕丁,奥地利作曲家。海顿是继巴赫之后又一位伟大的器乐作曲家,是古典主义音乐的杰出
  • 太常寺太常寺是中国古代掌管宗庙祭祀的机构。北齐始以太常寺为太常机构之称。隋、唐以后因之,为卿寺之一。唐代太常寺下机构甚多,有郊社、太庙、诸陵、太乐、鼓吹、太医、太卜、廪牺
  • 广珠城际铁路.mw-parser-output .RMbox{box-shadow:0 2px 2px 0 rgba(0,0,0,.14),0 1px 5px 0 rgba(0,0,0,.12),0 3px 1px -2px rgba(0,0,0,.2)}.mw-parser-output .RMinline{float:none
  • 德拉瓦特拉华县(英语:Delaware County)是美国奥克拉荷马州东部的一个县,东邻密苏里州和阿肯色州,面积2,052平方公里。根据2010年人口普查,本县共有人口41,487人。本县县治为杰里(Jay)。考
  • 卡洛曼二世 (西法兰克)卡洛曼二世(法语:Carloman II,866年12月6日-884年12月12日),是西法兰克王国加洛林王朝国王路易二世与王后勃艮第的安斯加尔德的幼子,879年其父王死后与兄路易三世同时即位为西法兰
  • 2014年8月逝世人物列表2014年8月逝世人物列表,是用于汇总2014年8月期间逝世人物的列表。
  • 断线双边鱼断线双边鱼为辐鳍鱼纲鲈形目鲈亚目双边鱼科的其中一个种,分布于亚洲大洋洲印尼,菲律宾、新几内亚、瓦努阿图、新喀里多尼亚、澳洲北部与安达曼海的淡水及半咸水水域,体长可达12
  • 卡西·阿弗莱克凯洛柏·卡西·麦奎尔·阿弗莱克-博尔特(英语:Caleb Casey McGuire Affleck-Boldt,1975年8月12日-)或简称卡西·阿弗莱克(英语:Casey Affleck),是一名美国男演员和导演。他常与演员及