完美图定理

✍ dations ◷ 2025-09-14 09:40:52 #图论,完美图

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

相关

  • 医疗卫生人体解剖学 - 人体生理学 组织学 - 胚胎学 人体寄生虫学 - 免疫学 病理学 - 病理生理学 细胞学 - 营养学 流行病学 - 药理学 - 毒理学医疗卫生,又称健康照护(英语:Health care
  • 嫘萦嫘萦(léi yíng/ㄌㄟˊ ㄧㄥˊ),英文Rayon或Viscose,又译人造丝,中文译名是发想自中国传说中发明养蚕的嫘祖而来。嫘萦是一种人工制造的纤维。由天然的植物棉加工制造而成,所以属
  • 华姓(阴平音或去声韵,作姓氏使用时不作阳平音。ㄏㄨㄚˋ,不念作ㄏㄨㄚˊ、ㄏㄨㄚ,粤语读waa6(话))为汉字姓氏之一,在《百家姓》中排名第28位。在当代中国姓氏中排名第196位,人数约
  • 高雄捷运红线.mw-parser-output .RMbox{box-shadow:0 2px 2px 0 rgba(0,0,0,.14),0 1px 5px 0 rgba(0,0,0,.12),0 3px 1px -2px rgba(0,0,0,.2)}.mw-parser-output .RMinline{float:none
  • 拐值拐点(Inflection point)或称反曲点,是一条连续曲线改变凹凸性的点,或者等价地说,是使切线穿越曲线的点。决定曲线的拐点有助于理解曲线的外形,这在描绘曲线图形时特别有用。若曲线
  • 凡察凡察,明朝建州女真人,生卒年不详。建州左卫掌卫猛哥帖木儿的弟弟。猛哥帖木儿死后,掌建州左卫。1437年明朝授猛哥帖木儿之子董山指挥使一职,自此叔侄俩人争印。1442年析置建州右
  • Cornell University Law School康奈尔法学院(Cornell Law School)是一所自1887年起在美国纽约州伊萨卡创设的法学院,附属于康奈尔大学。 该学院的师生比是10.4比1,是美国律师协会认证的所有184所法学院里第三
  • OSCE欧洲安全与合作组织(简称欧安组织;英文:Organization for Security and Co-operation in Europe,缩写:OSCE)是世界上主要的国际组织之一,前身是1975年于冷战期间成立的“欧洲安全与
  • 正三角形镶嵌在几何学中,正三角形镶嵌、又称为正三角方格是一种正多边形在平面上的密铺,又称正镶嵌图。康威称正三角形镶嵌为deltille。deltille一词来自于外形为三角形的希腊字母 Delta (
  • 硝酸铈铵硝酸铈铵是化学物质的一种,外观为呈现橘红色的晶体,分子式为 (NH4)2Ce(NO3)6,通常在有机合成中作为氧化剂及生产其它含铈化合物。硝酸铈铵溶于水时,完全电离,生成NH+ 4、Ce4+和NO