补图
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/2/2f/Petersen_graph_complement.svg/300px-Petersen_graph_complement.svg.png)
![]() | 此条目可参照英语维基百科相应条目来扩充。 |
在图论里面,一个图G的补图(complement)或者反面(inverse)是一个图有着跟G相同的点,而且这些点之间有边相连当且仅当在G里面他们没有边相连。在制作图的时候,你可以先建立一个有G所有点的完全图,然后清除G里面已经有的边来得到补图。这里的补图并不是图本身的补集;因为只有边的部分合乎补集的概念。
形式化表述
令是一个图,包含所有的二元子集。则图是的补图。
应用与范例
许多图论的概念都互相以补图的关系连接:
- 无边图的补图是完全图,反之亦然。
- 独立集的补图是团,反之亦然。
- 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.
![]() | 这是一篇小作品。您可以通过编辑或修订扩充其内容。 |
|