证明:简单图的同构是等价关系
时间: 2024-05-25 15:16:00 浏览: 21
要证明简单图的同构是等价关系,需要证明以下三个性质:
1. 自反性:任何一个简单图都与自己同构。
2. 对称性:如果图G与图H同构,则图H与图G也同构。
3. 传递性:如果图G与图H同构,图H与图K同构,则图G与图K也同构。
证明:
1. 自反性:对于任何一个简单图G,它的顶点集和边集都与自己相同,因此可以构造出一个恒等映射f(x)=x,使得对于任何一个顶点v∈G,f(v)=v,对于任何一条边e=(u, v)∈G,f(e)=(f(u), f(v))=(u, v)。这说明恒等映射f是一个图G到自己的同构映射,因此简单图的同构具有自反性。
2. 对称性:假设图G与图H同构,即存在一个双射f:V(G)→V(H),使得对于任何一条边(u, v)∈G,都有(f(u), f(v))∈H。由于f是双射,因此存在一个反函数f^{-1}:V(H)→V(G),使得对于任何一个顶点v∈H,都有f^{-1}(v)∈G。同样地,对于任何一条边(u, v)∈H,都有(f^{-1}(u), f^{-1}(v))∈G。因此,可以构造出一个双射g:V(H)→V(G),使得对于任何一条边(u, v)∈H,都有(g(u), g(v))=(f^{-1}(u), f^{-1}(v))∈G。这说明g是一个图H到图G的同构映射,因此简单图的同构具有对称性。
3. 传递性:假设图G与图H同构,图H与图K同构,即存在双射f:V(G)→V(H)和双射g:V(H)→V(K),使得对于任何一条边(u, v)∈G,都有(f(u), f(v))∈H,对于任何一条边(u', v')∈H,都有(g(u'), g(v'))∈K。由于f和g都是双射,因此可以定义一个双射h:V(G)→V(K),使得对于任何一条边(u, v)∈G,都有(h(u), h(v))=(g(f(u)), g(f(v)))∈K。这说明h是一个图G到图K的同构映射,因此简单图的同构具有传递性。
综上所述,简单图的同构是等价关系。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)