补图、同构图、自补图是什么意思

补图、同构图、自补图是什么意思

引用

CSDN

1.

https://m.blog.csdn.net/qq_33919450/article/details/142819511

在图论中，同构图、补图和自补图是三个重要的概念。本文将通过数学定义和直观解释，帮助读者理解这些概念，并通过具体示例进行说明。

同构图

同构图的数学定义为：给定两个图
G=(V,E)
和
G'=(V',E')
，若存在一个双射函数
f:V->V'
，使得对于任意的顶点
u,v∈V
，
(u,v)∈E
当且仅当
(f(u),f(v))∈E'
，则称
G
和
G'
是同构图。

数学定义看上去挺复杂的，但是简而言之就是两张图点相同，边也相同，但是点的位置不一样。这里解释一下什么叫“点相同，边也相同”：一个点的度不变，一条边两端的点也不变。这点数、边数、度序列这些也叫做图的性质。同构图也就是这些图的性质是一样的。

可以看看下面这张非常常见的同构图，你可以看到两张图都是 5 个点、5 条边，每个点的度都是 2，只是位置发生了变化，图的性质并没有发生变化。所以同构图还有个解释是：可以移动点得到图就是同构的。

那么再看看下面这张图，可以发现图的性质已经出现了变化，因为虽然边和点数不变，但是度发生了变化，比如左图的
e
度为 3，右图的
e
的度为 1，这就不同构了。

补图

补图的数学定义为：对于一个给定的图
G=(V,E)
，其补图
G'=(V,E')
是一个具有相同顶点集
V
的图，其中
E'
是
V
中未出现在
E
中的所有可能边的集合。换句话说，
G'
中的边是
G
中不存在的边。

啥意思呢，就是两个简单图，拼在一起就是完全图了，比如上面举的那个图：

他们两拼在一起是完全图。这样的两个图就是互补图。

自补图

自补图就是两个图不光是互补图，还是同构的。

依旧是这个例子，这两个图不光是同构的，还是互补的，所以是自补图。

有时候题目会只给一个图，问是不是自补图。解决这种问题的方法是先补全这个图，然后看画出来的部分和原有部分是不是同构。

希望能帮到有需要的人～