完美图定理

✍ dations ◷ 2025-12-08 12:51:30 #图论,完美图

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

相关

  • 造成疾病致病真菌(英语:Pathogenic Fungi)是引起人类或其他生物产生真菌病的真菌。 已知大约300种真菌对人类具有致病性。虽然真菌是真核生物,但是许多致病真菌也是微生物。对人类致病的
  • 维他命B12维生素B12(Vitamin B12)为B族维生素之一,是一类含钴的复杂有机化合物。分子结构是以钴离子为中心的咕啉环和5,6-二甲基苯并咪唑为碱基组成的核苷酸。化学式为C63H88O14N14PCo,分
  • 海豚海豚(学名:Delphinidae)古称海狶,是鲸类水生哺乳动物,外观大小和中文名称相似的亲属尚有鼠海豚和淡水豚,广泛生活在大陆架附近的浅海里,偶见于淡水之中。海豚大约包括了20几个属中
  • 信风带赤道低压带信风带副热带高压带西风带副极地低压带极地东风带极地高压带信风,又称贸易风,指的是在低空从副热带高压带吹向赤道低压带的风,北半球吹的是东北信风,而南半球吹的是东
  • 枫桦Betula costata Trautv. var. pubescens Liou硕桦(学名:Betula costata),又名枫桦、风桦(东北)、四层桦,为桦木科桦木属的植物。分布在俄罗斯以及中国大陆的河北、东北等地,生长于海
  • 美国贸易代表处美国贸易代表办公室(Office of the United States Trade Representative,英文简称USTR)是美国政府的一个行政部门,美国总统办事机构的一部分,负责在双边和多边的层面上推行美国的
  • 萨蒙·蔡斯萨蒙·波特兰·蔡斯(Salmon Portland Chase,1808年1月13日 - 1873年5月7日),是美国政治家和法学家,曾任美国参议院议员(1849年-1855年)、第23任俄亥俄州州长(1856年-1860年)、第25任
  • 2019冠状病毒病德国疫情2月2月3月3月4月4月过去15日过去15日注释:2019冠状病毒病德国疫情,介绍在2019-2020年冠状病毒病疫情在德国的情况,若无特殊注明,本条目中所有日期均为2020年。疫情最早于中国湖
  • 欧洲LGBT权益女同性恋者、男同性恋者、双性恋者与跨性别者(LGBT)在欧洲的权益受到欧洲联盟与多国法律的保障。全球25个承认同性婚姻的国家中,有15个在欧洲,同时英国的英格兰、威尔士、苏格兰
  • 墙柱墙柱(土耳其语:Örme Dikilitaş),又称君士坦丁方尖碑,位于土耳其伊斯坦布尔的君士坦丁堡赛马场(今苏丹艾哈迈德广场)的南侧,靠近蛇柱。这个方尖碑高32米,用石块建造。其精确的建造日