完美图定理

✍ dations ◷ 2025-05-17 17:42:10 #图论,完美图

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

相关

  • 并系群并系群(英语:Paraphyletic group或 Paraphyly )是支序分类中的一种分类单元,此分类群中的成员皆拥有“最近共同祖先”,但该群中并不包含此最近共同祖先之所有后代。一个类群是否
  • 至人传统宗教仪式:神明秘密社会:中医专著《黄帝内经·上古天真论篇第一》记载:“中古之时,有至人者,淳德全道,和于阴阳,调于四时,去世离俗,积精全神,游行天地之间,视听八远之外,此盖益其寿
  • 起飞起飞是指航空器在飞行过程中离开地面,进入空中的阶段。对于水平起飞的航空器而言,起飞一般需要在跑道上滑行(rolling),在到达一定速度及升力后再起飞。若是航空气球、直升机或是
  • 大羚羊伊兰羚羊(学名Taurotragus oryx),又名巨羚、大羚羊,是东非及南部非洲大草原及平原的一种羚羊。伊兰羚羊与德氏大羚羊一同被认为是最大的羚羊种,不过它们其实更像牛。雌羊重300-60
  • span class=nowrapCu(ClO)sub2/sub/span次氯酸铜是一种无机化合物,化学式为Cu(ClO)2。有漂白性。氧化铜与次氯酸或氯水反应,或硫酸铜和次氯酸钙在溶液中反应,都可以得到Cu(ClO)2。
  • 万福庵照墙坐标:22°59′46″N 120°12′10″E / 22.996175°N 120.202886°E / 22.996175; 120.202886首貮境万福庵,是位于台湾台南市中西区的齐天大圣庙。其前身为明朝英义伯阮骏之夫
  • 襾部襾部,为汉字索引中的部首之一,康熙字典214个部首中的第一百四十六个(六划的则为第二十九个)。就繁体和简体中文中,襾部归于六划部首。襾部大都只以上方为部字。且无其他部首可用
  • 白眉蓝姬鹟白眉蓝姬鹟(学名:)为鹟科姬鹟属的鸟类。该物种的模式产地在印度。
  • 横江 (金沙江支流)横江亦称关河,位于中国西南,是金沙江下段右岸支流。源出云南省鲁甸县水磨乡大海子,上源为居乐河,与昭鲁大河交汇后称洒渔河,在洛泽河汇入后称横江;在云南省水富县云富镇汇入金沙江
  • 别墅喜剧别墅喜剧 (意大利语:Villa Commedia)是小普林尼拥有的罗马别墅,它在意大利北部科摩湖的岸边。普林尼在科莫湖有几栋别墅,但是他在给朋友小普林尼 (立陶宛语:Plinio)的信中提到,“别