标签：#完美图

完美图定理

在图论中，完美图定理（由洛瓦兹·拉兹洛证明）断言：一个无向图是完美的当且仅当其補圖也是完美的。这个结论一度是提出的猜想。它有时也被称为弱完美图定理，以和强完美图定理作区分。强完美图定理通过禁止导出子图来刻画完美图。 定理叙述 一个完美图是具有下述性质的无向图：在其每个导出子图中，最大团的顶点数都等于对该导出子图的着色的颜色数的最小值。完美图包括了很多重要类型的图，例如二分图、弦圖和。 一个图的补图在某两个顶点之间连一条边当且仅当原图在这…