一个无向图有四个顶点_无向自补图的一些性质和一种构造方法

作者：Monodyee | 2024-05-19 06:38:14

踩

给出4个顶点的自补图

给定一个无向图

$equation?tex=G%3D%3CV%2CE%3E$ ，其自补图为

$equation?tex=G%27%3CV%2CE%27%3E$ 当且仅当

$equation?tex=%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%28u%2Cv%29%5Cin+E%27%26%E8%8B%A5%28u%2Cv%29%5Cnotin+E%5C%5C%28u%2Cv%29%5Cnotin+E%26%E8%8B%A5%28u%2Cv%29%5Cin+E%5C%5C%5Cend%7Bmatrix%7D%5Cright.%5Ctag%2A%7B%7D$

$equation?tex=G%27$ 的点集和

$equation?tex=G$ 相同，边集则是

$equation?tex=E$ 关于点集为

$equation?tex=V$ 的完全图的边集的补集，即

$equation?tex=%3CV%2CE%2BE%27%3E$ 为完全图。

$equation?tex=E%2BE%27$ 意为

$equation?tex=E$ 和

$equation?tex=E%27$ 的并集，因为两集合的交为空，故用加号表示并，本文接下来也沿用如此表示方法。补图是对偶的，

$equation?tex=G$ 和

$equation?tex=G%27$ 互为补图。

可以方便地得到一些简单性质：

独立集在补图中为团（完全子图），团在补图中为独立集。
若图不连通，则其补图一定连通。

对第二条性质简单证明如下：

在不连通的无向图

$equation?tex=G%3D%3CV%2CE%3E$ 中，

$equation?tex=%5Cforall+u%2Cv%5Cin+V$ ，存在两种可能的情况：

$equation?tex=u%2Cv$ 同属一个连通分量；

$equation?tex=u%2Cv$ 不属于一个连通分量。

如果

$equation?tex=u%2Cv$ 两顶点不属于同一个连通分量，则

$equation?tex=%28u%2Cv%29%5Cnotin+E$ ，即意味着

$equation?tex=%28u%2Cv%29%5Cin+E%27$ ，故在补图

$equation?tex=G%27$ 中两顶点属于同一个连通分量。

如果

$equation?tex=u%2Cv$ 两顶点属于同一个连通分量，因为

$equation?tex=G$ 不连通，故

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/591915