完美图定理

✍ dations ◷ 2025-04-02 12:40:46 #图论,完美图

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

相关

  • 电子语音现象电子语音现象(英语:Electronic voice phenomenon、简称EVP),是超心理学和捉鬼(英语:ghost hunting)中用于佐证灵体的存在的一种方法。其是将现场环境(听不到的声音)录起来,然后在播放
  • 乔治三世乔治三世(英语:George III,1738年6月4日-1820年1月29日),全名乔治·威廉·腓特烈(George William Frederick),1760年10月25日登基为大不列颠国王及爱尔兰国王,至1801年1月1日后因大不
  • 麦西热甫麦西热甫(维吾尔语:.mw-parser-output .font-uig{font-family:"UKIJ Tuz","UKIJ Nasq","UKIJ Basma","UKIJ_Mac Basma","UKIJ Zilwa","UKIJ Esliye","UKIJ Tuz Basma","UKIJ T
  • 浊齿龈边塞擦音(Voiced alveolar lateral affricate)是辅音的一种,用于一些口语中。表示此音的国际音标(IPA)是⟨d͡ɮ⟩,并常常被简化为⟨dɮ⟩。浊齿龈边塞擦音的特征包括:浊齿龈
  • 梦魇梦魇可以指:
  • 竹节虫目竹节虫,又称䗛(拼音:xiū,注音:ㄒㄧㄡ,音同“修”)是节肢动物门昆虫纲竹节虫目(又称䗛)的总称。草食性的昆虫,以善于拟态成树枝或树叶著称,可以躲过天敌。全世界约有2,500种。体型修长,
  • font color=white中国大陆/font语言 - 文化 - 体育 - 节日 政府 - 政治 - 法律 - 经济 艺术 - 文学 - 舞蹈 - 戏曲中国大陆高等学校列表列出中华人民共和国的普通高等学校、成人高等学校和军事高等学
  • 洛克洛克可以指:
  • 海蛇函Eucladiidae Sollasiniidae Volchoviidae Rhenosquamidae?海蛇函(ophiocistioids)是一类已灭绝的棘皮动物。身体呈穹窿状,口在下面中央,自口中伸出八对覆有骨板的管足(一说是腕)。
  • 2015年NBA季后赛2015年NBA季后赛是国家篮球协会(NBA)在2014-15 NBA赛季常规赛完毕后举行的七场四胜制淘汰赛,本届是第69届季后赛。 比赛第一轮于当地时间2015年4月18日至5月2日进行,第二轮于5月