图的同构[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。

图的同构

• Abstract
• 图的同构
  • 为什么要研究图的同构
  • 满足什么条件的图才是图的同构
    • 同构的图案例
  • 任意两个图形，如何判定图的同构
    • 图同构的必要条件，也就是说两个图如果同构，会存在的特征
    • 图同构的必要条件举例

Abstract

声明：本文只为我闲暇时候学习所做笔记，仅供我无聊时复习所用，若文中有错，误导了读者，敬请谅解！！！ 图的同构参见我的语雀：图论：https://www.yuque.com/jhongtao/mai/sabavx

图的同构

为什么要研究图的同构

• 图的结构决定图的本质特征，结构相同的图会有类似的性质，因而需要研究图的同构问题

image.png

满足什么条件的图才是图的同构

image.png

同构的图案例

image.png

任意两个图形，如何判定图的同构

• 判断两个图是否同构，目前没有比较好的方法，但是也可以从一些方面着手
  • 根据节点的度数做初步判定，一度的节点肯定会对应一度的节点，2度节点也肯定对应2度节点
  • 也可以对节点的邻接节点进行判断，一个节点的邻接点是2度和3度节点，那么在另一个图中也应该是一样的

image.png

1. 在图G1中只有一个一度节点e，G2中也只有一个一度节点v5,所以在图的双射关系中，图G1中的e就应该对应图G2中的v5:e->v5
2. 同理，在图G1中的6度节点a,也就应该对应图G2中的6度节点v1:a->v1
3. ·······
4. 当然如果图的节点和度数规模很大的时候，这种对应关系就会变得很多，所以就不好判断了

图同构的必要条件，也就是说两个图如果同构，会存在的特征

• 当图如果不满足下面的条件则这两个图肯定不同构，但是如果满足也不一定同构

image.png

图同构的必要条件举例

image.png

1. 在图G和图G’中，图的节点数都相同，且都拥有3个一度节点，2个2度节点，和1个3度节点
2. 但是可以看到图G中度数为3的节点3，它连接的是1个1度节点（6）和2个2度节点（2和4）
3. 图G’中度数为3的节点d，它连接的是2个1度节点（f和e）和1个2度节点©
4. 所以图G和图G’不是同构的图

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/125190.html原文链接：https://javaforall.cn