完美图定理

✍ dations ◷ 2025-03-04 15:44:44 #图论,完美图

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

相关

  • 议会制君主立宪制议会制君主立宪制是君主立宪的一种形式,特点是议会是国家的最高权力机关和立法机关,以政府首脑(通常为首相和总理大臣)为首的内阁是国家的行政机构,内阁由议会议员产生并对议会负
  • 大阪2019冠状病毒病大阪府疫情(日语:大阪府における2019年コロナウイルス感染症の流行/おおさかふにおける2019ねんコロナウイルスかんせんしょうのりゅうこう),介绍日本的2019冠状病
  • 库仑力电磁力(英语:electromagnetic force)是处于电场、磁场或电磁场的带电粒子所受到的作用力。大自然的四种基本力中,电磁力是其中一种,其它三种是强作用力、弱作用力、引力。光子是
  • 罗莎·帕克斯罗莎·路易丝·麦考利·帕克斯(英语:Rosa Louise McCauley Parks,1913年2月4日-2005年10月24日)是一位美国黑人民权行动主义者。1955年,她在公车上拒绝让座给白人乘客,因此遭逮捕,引
  • 石岩街道石岩街道是中国广东省深圳市宝安区下辖的一个街道,位于宝安区中西部,介乎龙华街道与西乡街道之间。石岩街道属一个小山村,介乎龙华街道与西乡街道之间,南接南山区西丽街道。伴随
  • 真理报《真理报》(俄语:Пра́вда),创刊于1912年5月5日,前身为托洛茨基于1908年10月3日在维也纳创办的同名报纸,是1918年至1991年间苏联共产党中央委员会的机关报。在苏联于1991年
  • 捷豹XF捷豹XF(Jaguar XF),是由捷豹销售的一种四门轿车。2007年1月宣布的概念车之基础上,设计发生了重大变化,同年9月首次在举行的法兰克福车展上发布,并于2008年在欧洲市场上大量发售。
  • 军夫军夫或者军伕可以指:
  • 左潜左潜(1846年-1874年),字壬叔,一作壬叟。左宗棠从子,清朝数学家。早年中秀才,曾钻研天文历法,校勘出版唐代《开元占经》,补县学生,于诗、古文辞无不深造,尤明算理。与丁取忠为忘年交。早
  • 彩虹桥国家纪念区彩虹桥国家纪念区(rainbow bridge national monument)是位于美国犹他州南部格伦谷国家养护区的一个国家纪念区。彩虹桥是世界最高的天然桥梁。彩虹桥的拱长71米,顶部厚13米,宽10