完美图定理

✍ dations ◷ 2025-12-05 19:59:45 #图论,完美图

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

相关

  • 易索普益普索(Ipsos),是一家位于法国巴黎的市场研究公司。成立于1975年。不同于其他市场研究公司,益普索是少数专注于“市场营销研究”与“个案研究”的公司。Ipsos 五大核心研究领域
  • 切萨皮克湾切萨皮克湾(英语:Chesapeake Bay),是美国面积最大的河口湾,位于美国大西洋海岸中部,为马里兰州和弗吉尼亚州三面环绕,仅南部与大西洋连通。其名来自阿尔冈金印第安语,意为“大贝壳湾
  • 生殖系统疾病生殖系统性问题是指男女生殖系统出现的毛病。包茎、阴茎硬结症,阴茎发育不全等所有严重的全身性急、慢性疾病。如男性性欲低下、肝硬化、慢性肾功能衰竭、慢性活动性肝炎等生
  • 鳕角鳕鱼角(英语:Cape Cod),是美国东北部马萨诸塞州伸入大西洋的一个半岛,面积1033平方公里。1914年,美国在该半岛与大陆连接处开掘鳕鱼角运河,使鳕鱼角实际上成为了一个岛屿。
  • 汽油机汽油引擎(Gasoline Engine、Petrol Engine)是使用汽油作为燃料的内燃机。1883年德国人G.戴姆勒成功制造汽油机。二战前,汽油机用作1千瓦以下的农业、园艺机具的动力,大到数千瓦
  • 里霍博斯人巴斯特人(英语:Basters),是纳米比亚共和国中一个由荷兰男人与布须曼人和黑人妇女混血产生的族群,说南非语。他们通常被认为是纳米比亚阿非利卡人一个次群体,更偏远的有色人。自19
  • 皮耶罗·斯拉法皮耶罗·斯拉法(意大利语:Piero Sraffa,1898年8月5日-1983年9月3日),生于意大利都灵,著名经济学家,专长于政治经济学。他是新李嘉图学派的建立者,对剑桥学派有很大的影响力。皮耶罗·
  • 黄金时代 (1946年电影)《黄金时代》("The Best Years of Our Lives")是一部1946年的美国电影。影片由威廉·惠勒执导,弗雷德里克·马区、玛娜·洛伊、达纳·安德鲁斯(英语:Dana Andrews)、特雷莎·怀特(
  • 傀儡牵姻缘《傀儡牵姻缘》是三立台湾台《戏说台湾》的连续剧,于2015年2月2日至2月13日播出,由俞昊翔、徐紫淇、吴帆、简家玮、等主演。每周一至五晚上7:30播出。傀儡尪仔杨状元动了凡心,却
  • 安德烈·根纳季耶维奇·卡尔洛夫安德烈·根纳季耶维奇·卡尔洛夫(俄语:Андрей Геннадьевич Карлов,1954年2月4日-2016年12月19日),前苏联及俄罗斯联邦外交官,2013年7月12日起担任俄罗斯联