1. 全栈程序员必看首页

图的同构[通俗易懂]

全栈程序员-站长 • • 未分类 • 阅读 77

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

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

赞 (0)
全栈程序员-站长的头像全栈程序员-站长
0 0


相关推荐

  • 数组反转两种方法[通俗易懂]

    数组反转两种方法[通俗易懂]

    数组反转两种方法[通俗易懂]//数组反转 for(inti=0;i<arr.length/2;i++){ Stringt=””; t=arr[i]; arr[i]=arr[arr.length-1-i];//length-1 arr[arr.length]=t; } //方法二 for(inti=0,j=arr.length;i<arr.length/2;i++,j–){ Stringt=arr[i..

    全栈程序员-站长的头像 全栈程序员-站长
    2022年5月20日
    36
  • PHP TCPDF导出支持中文的pdf

    PHP TCPDF导出支持中文的pdf

    PHP TCPDF导出支持中文的pdfPHP使用TCPDF导出支持中文的pdf一、下载https://github.com/tecnickcom/tcpdf下载TCPDF压缩包二、使用方法 require_once(‘./TCPDF/tcpdf.php’); $pdf=new\TCPDF(); $pdf->AddPage(); $html=”<p>helloworld你好世界</p>”; $pdf->WriteHtml(20,$html); //四种模式I输出

    全栈程序员-站长的头像 全栈程序员-站长
    2022年9月7日
    0
  • mysql中的varchar_从数据类型varchar转化为

    mysql中的varchar_从数据类型varchar转化为

    mysql中的varchar_从数据类型varchar转化为MySQL数据类型varchar详解更新时间：2014年03月17日11:10:11作者：这篇文章详细介绍了MySQL数据类型varchar,探讨varchar到底能存多长的数据、InnoDB和MyISAM中的varchar等问题,需要的朋友可以参考下1、varchar(N)的逻辑意义从MySQL4.1开始，varchar(N)中的N指的是该字段最多能存储多少个字符(characters…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年9月2日
    3
  • 20行Python代码爬取王者荣耀全英雄皮肤

    20行Python代码爬取王者荣耀全英雄皮肤

    20行Python代码爬取王者荣耀全英雄皮肤引言王者荣耀大家都玩过吧，没玩过的也应该听说过，作为时下最火的手机MOBA游戏，咳咳，好像跑题了。我们今天的重点是爬取王者荣耀所有英雄的所有皮肤，而且仅仅使用20行Python代码即可完成。准备工作爬取皮肤本身并不难，难点在于分析，我们首先得得到皮肤图片的url地址，话不多说，我们马上来到王者荣耀的官网：我们点击英雄资料，然后随意地选择一位英雄，接着F12打开调试台，找到英雄原皮肤的图片…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年5月5日
    68
  • 1024快乐

    1024快乐

    1024快乐1024程序员节日快乐转载于:https://www.cnblogs.com/canmeng/p/9842898.html

    全栈程序员-站长的头像 全栈程序员-站长
    2022年6月24日
    30
  • 使用GAppProxy时安全证书无效的解决办法「建议收藏」

    使用GAppProxy时安全证书无效的解决办法「建议收藏」

    使用GAppProxy时安全证书无效的解决办法「建议收藏」使用GAppProxy做代理，登录Echofon时却老是弹出”api.twitter.com:443使用了无效的安全证书。该证书因为其发行这证书位置而不被信任sec_error_unknown_issuer”的对话框，导致登录失败。搜索了一下，可尝试手动将api地址加入信任列表。以FireFox4.0为例（3.6也差不多）具体做法如下：依次选择选项->高级->加…

    全栈程序员-站长的头像 全栈程序员-站长
    2025年6月20日
    0

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

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