完美图定理

✍ dations ◷ 2025-07-07 08:51: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)证明,如果一个完全图的所有边被分成三个导出子图,使得任何三个顶点都在其中一个导出子图中连通,且两个导出子图是完美的,则第三个导出子图必然也是完美的。完美图定理是这个结果在其中一个导出子图是空图时的特例。

相关

  • 工团主义工团主义(英语:Syndicalism),又称工联主义,是一种以劳工运动为主导的社会主义,旨在工人阶级团结起来组织工会,通过纯粹的工人组织以及罢工来推翻资本主义和国家,以使企业由资本家主
  • 前青少年期前青少年期(Preadolescence、pre-teen、tween)是人类发展中,在幼儿和青少年期之间的阶段,一般会以青春期的开始认定为前青少年期的结束,也有些会直接用年龄作定义,例如在字典中,前
  • 韦恩县韦恩县 (Wayne County, Georgia)是美国乔治亚州东南部的一个县,成立于1803年。面积1,680平方公里,人口26,565 (美国2000年人口普查)。首府耶苏普。
  • 战间期战间期,指的是自第一次世界大战结束到第二次世界大战爆发的这段时期。这一时期,世界局势仍然十分动荡。欧洲在这一时期仍然处于从第一次世界大战所带来的巨大创伤恢复的时期。
  • 永信药品永信药品工业股份有限公司(英语:YUNGSHIN PHARM IND. CO., LTD.,简称永信药品),是台湾的一间制药公司,于1965年创立,目前为永信国际投资控股股份有限公司之全额控股子公司。于美国
  • 房颤心房颤动(英语:Atrial fibrillation,简称:Af 或 A-fib),又称为心房微颤、房颤、心房纤维性颤动、心房纤颤、房性纤颤等,是心脏不正常节律/心律不整的一种,特色是心脏快速而不规则的
  • 狮甲狮甲站是高雄捷运红线的一座捷运车站,位于高雄市前镇区中山二路及复兴三路、民权二路一带,古代为戏狮甲庄的大林尾聚落;而古代戏狮甲庄的戏狮甲聚落位于今一心路于文横至林森路
  • 杭瑞高速杭州—瑞丽高速公路,简称杭瑞高速,中国国家高速公路网编号为G56,起点在杭州,途经黄山、景德镇、九江、咸宁、岳阳、常德、吉首、遵义、毕节、六盘水、曲靖、昆明、大理,终点在瑞
  • 朝鲜音乐朝鲜传统音乐或韩国传统音乐分为民俗音乐和宫廷音乐两种。朝鲜传统民俗音乐形式多样,主要包括盘索里、农乐和散调等。其中盘索里作为一种朝鲜传统曲艺形式列入了人类非物质文
  • 歌林歌林(Kolin)是台湾家电品牌,创立于1963年,已超过50年历史。歌林家电商品,涵盖液晶电视、电冰箱、洗衣机、移动式冷气以及各种小家电。歌林品牌过去是由歌林股份有限公司(Kolin Inc