图的同构[通俗易懂]

图的同构[通俗易懂]图的同构Abstract图的同构为什么要研究图的同构满足什么条件的图才是图的同构同构的图案例任意两个图形,如何判定图的同构图同构的必要条件,也就是说两个图如果同构,会存在的特征图同构的必要条件举例Abstract声明:本文只为我闲暇时候学习所做笔记,仅供我无聊时复习所用,若文中有错,误导了读者,敬请谅解!!!图的同构参见我的语雀:图论:https://www.yuque.com/jhongt…

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

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’不是同构的图
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/125190.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号