完美图定理

✍ dations ◷ 2025-12-01 17:27:15 #图论,完美图

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

相关

  • 白介素-1结构 / ECOD介白素-1包括11种细胞因子,在机体控制免疫和炎症反应中具有重要作用。这些细胞因子的发现始于1943年至1948年间,Menkin和Beeson对兔子腹腔细胞释放的致热原蛋白质
  • 裸露癖露体癖(英语:exhibitionism)或阴部显露欲是指偏好在公共或半公共场合对不知情者曝露身体中通常不会暴露的部分的行为,例如暴露乳房、臀部或阴茎。这种行为的动机可能是自身欲望
  • 基因本体基因本体论(Gene ontology ,GO)是一种系统地对物种基因及其产物属性进行注释的方法和过程。它的目标是:1)维护和发展有限的基因及其产物属性描述的词汇;2)注释基因及其产物,同化和传
  • 大高加索山脉大高加索山脉是高加索山脉中两个主要山脉之一,与另一主要山脉小高加索山脉在苏拉姆山脉相连后平行伸延,两者平均相距100公里。大高加索山脉从黑海海岸的塔曼半岛一直向东南方
  • 绿色计算绿色计算指利用各种软件和硬件先进技术,将目前大量计算机系统的工作负载降低,提高其运算效率(如flop/watt指标),减少计算机系统数量,进一步降低系统配套电源能耗,同时,改善计算机系
  • 平顶山事件平顶山惨案(平顶山事件),是一起发生在1932年9月16日负责看守抚顺煤矿的日本军抚顺守备队(井上小队)在扫荡行动之际,对于杨柏堡村附近平顶山村居民的屠杀。地点位于现在的中国辽宁
  • 尼古拉斯·默里·巴特勒尼古拉斯·默里·巴特勒(Nicholas Murray Butler,1862年4月2日-1947年12月7日),美国哲学家、外交官和教育家。他和简·亚当斯一起获得了1931年诺贝尔和平奖。巴特勒1887年创办了
  • 理查德·托尔曼理查德·蔡斯·托尔曼(英语:Richard Chace Tolman,1881年3月4日-1948年9月5日),美国数学物理学家和物理化学家,亦是统计力学的权威学者。他还在爱因斯坦发现了广义相对论后不久为物
  • 日本茶道茶道(日语:茶道/さどう、ちゃどう),起源于中国,后传到日本。成为了日本传统艺道,是将生活消闲活动提升至精神意识层次,成为一种独特传统礼仪,是宣扬文化之媒介。日本茶道是为客人奉茶
  • 约翰·安德森 (政治家)约翰·安德森,第一代威瓦利子爵GCB OM GCSI(英语:Order of the Star of India) GCIE PC PC(英语:Privy Council of Ireland) FRS(英语:John Anderson, 1st Viscount Waverley,1882年7