完美图定理

✍ dations ◷ 2025-11-25 23:46:39 #图论,完美图

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

相关

  • 简单重复序列微卫星(英语:Microsatellite,亦称为简单重复序列(英语:Simple Sequence Repeats,SSRs)或短串联重复序列(英语:short tandem repeats,STRs))是多型性的一种类型。指两个或多个核苷酸重复
  • 英国医学期刊英国医学期刊(British Medical Journal,简称 BMJ),是一份同行评审性质的综合医学期刊,也是最古老的医学期刊之一。由BMJ出版集团公司(BMJ Publishing Group Ltd)(属于英国医学协会(Br
  • 乔治·丘克乔治·杜威·丘克(George Dewey Cukor,1899年7月7日-1983年1月24日),生于美国纽约,犹太人,美国电影导演,著名影星奥黛丽·赫本主演的经典轻喜剧电影《窈窕淑女》即是由他导演,并获得
  • 王崇简王崇简(1602年12月10日-1678年12月30曰),字敬哉,一作敬斋,明末清初宛平(今属北京市)人。早年加入复社,喜郊游,工山水画,师法米芾。崇祯十六年(1643年)中癸未科进士,未及授官,李自成陷北京。
  • 南海郡南海郡,是从秦朝至唐朝的郡,位于汉地九州域内。郡治番禺县在今广东省广州市越秀区。秦朝平定岭南后设桂林、象郡、南海三郡。南海郡下辖四县(番禺、四会、博罗、龙川),另一说为六
  • NSC国家安全委员会(英语:National Security Council),简称国安会(NSC),是由美国总统主持的最高级别国家安全及外交事务决策委员会,依据《1947年国家安全法》设立,自成立以来的主要任务是
  • 约瑟 (旧约圣经)约瑟(天主教会译为“若瑟”,但与《新约》中耶稣的养父不同)(SPIRIT公元前 ? ~ 公元前1657年)(希伯来语:יוֹסֵף‎,标准 Tiberian ;"He(主)加添/将增添",阿拉伯语:يوسف‎;古希腊
  • 肉燥肉臊、卤肉或是卤肉燥是台湾料理或小吃中常见的配料,是由猪肉的绞肉加酱油熬煮后而成,有时也会加入肥肉或猪皮一同熬煮,或是先将肉燥炒香后再熬煮。许多台湾小吃中会加入肉燥,例
  • 约翰·麦克尤恩约翰·麦克尤恩爵士(Sir John "Black Jack" McEwen), GCMG CH (1900年3月29日-1980年11月20日),农场主、政治家、澳大利亚总理(1967—1968年)。1934年—1971年为众议院议员,第二次
  • 约瑟夫·海勒 (动物学家)约瑟夫·亚历山大·海勒(1941年4月10日-),生于澳大利亚悉尼,是以色列的动物学家,贝类学家。海勒是耶路撒冷希伯来大学理学院, 西尔弗曼生命科学院生态学,进化和行为系的名誉副教授。