完美图定理

✍ dations ◷ 2025-10-14 19:32:28 #图论,完美图

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

相关

  • 人均寿命平均寿命、生命期望或预期寿命(英语:life expectancy),指生物群体中衡量单一生命存活平均长度的统计量。预期寿命最常用的测量方法是自出生起算(英语:Life expectancy at birth,LEB
  • 德意志米歇尔德意志米歇尔(Deutscher Michel)是德国的拟人化形象,这个称呼起源于近代,而至今也仍然可以在讽刺画中找到。戴着典型的睡帽(英语:nightcap 德语:Schlafmütze )或者绒球帽的“德意志
  • 菌髓菌随(拉丁语:Trama)是担子菌门真菌的子实体(担子果)中,菌伞与菌褶中心的肉质部分。菌褶的菌髓外侧为子实下层与可产生担孢子的子实层,而某些种类菌伞的菌随外侧有菌盖皮覆盖。菌随
  • Big Hit EntertainmentBig Hit Entertainment(韩语:빅히트엔터테인먼트)是一间韩国经纪娱乐公司。2005年由韩国知名音乐制作人兼作曲家Hitman Bang(本名:房时爀)于韩国创办,主要从事音乐制作、专辑发行、
  • 太阳鸟科太阳鸟科,俗称玄凤(学名:Nectariniidae)是鸟纲雀形目中的一个科。主要生活在热带地区,以花蜜为食,有时也吃昆虫。为留鸟或短途候鸟。
  • JR西日本271系电力动车组271系列车是西日本旅客铁路的一款直流电特急型列车,用于连接关西国际机场至新大阪、京都、米原的“遥号”特急列车。本列车于2020年3月14日投入服务。遥号自1994年开始运营以
  • 陈赏 (宋朝)陈赏,字景申,小名岳孙,本贯福州怀安县,陈襄七世从孙,南宋宝祐四年(1256年)第一甲进士第二名。
  • 古东斯拉夫语古东斯拉夫语,亦称为古俄语及罗斯语(Rusian,来自罗斯一词),是一种在10至15世纪时基辅罗斯及其继承国的东斯拉夫人所使用的语言。古东斯拉夫语的使用者多分布在今白俄罗斯、乌克兰
  • delicious way《delicious way》是日本歌手仓木麻衣出道专辑,于2000年6月28日发行。70 新宿之女/“演歌之星”藤圭子的全集(藤圭子) | 71 You Don't Have to Say You Love Me(艾维斯·普里斯莱
  • 传递闭包传递闭包、即在数学中,在集合 上的二元关系 的传递闭包是包含 的 上的最小的传递关系。例如,如果 是(生或死)人的集合而 是关系“为父子”,则 的传递闭包是关系“ 是