补图
在图论里面,一个图G的补图(complement)或者反面(inverse)是一个图有着跟G相同的点,而且这些点之间有边相连当且仅当在G里面他们没有边相连。在制作图的时候,你可以先建立一个有G所有点的完全图,然后清除G里面已经有的边来得到补图。这里的补图并不是图本身的补集;因为只有边的部分合乎补集的概念。
此条目可参照英语维基百科相应条目来扩充。 |
形式化表述
令 是一个图, 包含所有 的二元子集。则图 是 的补图。
应用与范例
许多图论的概念都互相以补图的关系连接:
参考资料
- 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.