完美图定理

✍ dations ◷ 2025-12-09 14:34:48 #图论,完美图

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

相关

  • 加速器加速器可能指:
  • 麝香麝香(别名:寸香、原寸、香脐子、当门子;拉丁名:Moschus)为脊索动物门哺乳纲麝科动物,如林麝(Moschus berezovskii)、马麝(Moschus sifanicus)或原麝(Moschus moschiferus)等成熟雄体位于
  • 霍顿汽车霍顿汽车(英语:GM Holden Ltd),是一家澳大利亚的汽车制造厂商,总部位于澳大利亚维多利亚州墨尔本。霍顿汽车是由James Alexander Holden于1856年创立。当时公司纯粹生产马鞍。随
  • 顾八代顾八代(满语:ᡤ᠋ᡡᠪᠠᡩᠠᡳ,穆麟德:Gūbadai,?-1708年),字文起,伊尔根觉罗氏,满洲镶黄旗人。三藩之乱期间,顾八代在广西数次击破吴世琮,后担任礼部尚书,期间曾教授当时还是皇子的雍正
  • 新五代史《新五代史》,北宋欧阳脩撰,是唐代以后唯一私修正史。尹洙与欧阳修打算合撰《新五代史》,但因史观不同而作罢,尹洙后来独撰两卷的《五代春秋》。宋仁宗皇祐五年(1053年)《新五代史
  • 圣母皇太后皇太后是皇帝、天皇、沙皇为其母亲所上的尊号,太后一词最早出现在中国战国时期,秦国秦宣太后芈八子(秦惠文王之妾,秦昭襄王之母)。皇帝在登基初期,尊封前任皇帝的皇后,通常是他的嫡
  • 金喜善金喜善(韩语:김희선,英语:Kim Hee-Seon ,1977年6月11日-),韩国女演员。金喜善就读11级时,参加韩国青春美少女大赛,并开始在电视上演出。她的第一套演出的电视剧是1993年播出的《恐龙先
  • 圣马特奥圣马特奥(San Mateo;当地多译为圣马刁;Saint Matthew“圣玛窦”的西班牙语),是一个位于美国加利福尼亚州圣马特奥县的城市,在临近旧金山的海湾地区。圣马特奥在2010年人口普查时的
  • 革命黑豹党革命黑豹党(英语:Revolutionary Black Panther Party,缩写为RBPP)是美国的一个泛非主义政党。该党成立于1992年。该党的意识形态是共产主义、马克思列宁主义、泛非主义、革命社
  • 2015年1月逝世人物列表2015年1月逝世人物列表,是用于汇总2015年1月期间逝世人物的列表。