补图

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

佩特森图(左)以及其补图(右)

形式化表述

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

应用与范例

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

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

参考资料