补图

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

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

形式化表述

令 是一个图， 包含所有 的二元子集。则图 是 的补图。

应用与范例

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

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

参考资料