补图

File:Petersen graph complement.svg

佩特森图（左）以及其补图（右）

在图论里面，一个图G的补图（complement）或者反面（inverse）是一个图有着跟G相同的点，而且这些点之间有边相连当且仅当在G里面他们没有边相连。在制作图的时候，你可以先建立一个有G所有点的完全图，然后清除G里面已经有的边来得到补图。这里的补图并不是图本身的补集；因为只有边的部分合乎补集的概念。

形式化表述

令<math>G = (V, E)</math>是一个图，<math>K</math>包含所有<math>V</math>的二元子集。则图<math>H = (V, K \setminus E)</math>是<math>G</math>的补图。

应用与范例

许多图论的概念都互相以补图的关系连接：

• 无边图的补图是完全图，反之亦然。
• 独立集的补图是团，反之亦然。
• triangle-free graph的补图是claw-free graph。
• self-complementary graph是一个与自己的补图同构的图。
• Cograph是由不交并（可参考集合论的不交并）以及补集建立起来图的集合。而且，这个集合是self-complementary；也就是说，任何cograph的补图也必然是cograph（虽然可能不是同构的图）。

参考资料

• Bondy, John Adrian; Murty, U. S. R., Graph Theory with Applications, North-Holland, 1976 [2011-07-29], ISBN 0-444-19451-7, （原始内容存档于2010-04-13） , pages 6 and 29.

• Diestel, Reinhard, Graph Theory 3rd, Springer, 2005, ISBN 3-540-26182-6 . Electronic edition（页面存档备份，存于互联网档案馆）, page 4.