跳转到内容

补图

维基百科,自由的百科全书
佩特森图(左)以及其补图(右)

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

形式化表述

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

应用与范例

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

参考资料