完美图定理

✍ dations ◷ 2025-11-15 19:21:46 #图论,完美图

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

相关

  • 阿尔西比亚德斯阿尔西比亚德斯(希腊语:Ἀλκιβιάδης Κλεινίου Σκαμβωνίδης,拉丁语:Alkibiádēs Kleiníou Skambōnidēs,前450年-前404年)是雅典杰出的政治家、演说
  • 数据库理论数据库理论(Database theory)指数据库与数据库管理系统的相关理论与研究。数据管理方面的理论涵盖其他领域,如查询语言的基础、计算复杂性和查询的表达能力(英语:Expressive powe
  • HfClsub4/sub四氯化铪,无机化合物,化学式HfCl4。这种无色固体是大多数有机铪化合物的前体。它可用于多种特定用途,主要集中于材料科学中,或作为催化剂。可以用几种相近的方法来制备HfCl4:铪和
  • 1441年约前1445年,古埃及法老图特摩斯三世打败了米坦尼国王,夺占米坦尼王国位于幼发拉底河西岸的土地。
  • 鱼雷艇鱼雷艇是一种相对于其他种类舰艇小、快速,并以鱼雷为主要武器的海军舰艇。
  • 二氯化铂二氯化铂也称为“氯化亚铂”或“氯化铂(Ⅱ)”,是由氯元素与铂元素组成的无机化合物,分子式为PtCl2。二氯化铂能以两种晶型存在,这两种晶体都具有反磁性,皆为无味、不溶于水的淡
  • 卡伦·鲁索卡伦·鲁索,(英语:Cullen Russo,1994年2月1日-),出生于美国,现役美国职业篮球运动员,曾效力于ABL联盟的宝岛梦想家,场上位置为前锋。
  • 林永昇林永升(1853年-1894年9月17日),又名翼昇,字锺卿,福建侯官人。清朝北洋海军将领,左翼左营副将。1894年甲午战争黄海海战中为巡洋舰经远号管带,在战事中被日军炮弹击中殉国。1867年考
  • 乔瓦尼·贝利尼乔瓦尼·贝利尼(意大利语:Giovanni Bellini,1430年-1516年),意大利文艺复兴时期艺术家。雅科波·贝利尼(Jacopo Bellini)的小儿子。他的姐姐嫁给了安德烈亚·曼泰尼亚(Andrea Mantegn
  • 东方省 (蒙古国)东方省(蒙古语:Дорнод аймаг,转写:Dornod aimag)位于蒙古国最东部,面积123,597平方公里,人口69,552(2011年)。首府乔巴山。辽代时期属乌古敌烈部都统军司管辖。后地入塔塔