1. 全栈程序员必看首页

图的同构[通俗易懂]

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

图的同构[通俗易懂]图的同构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


相关推荐

  • Java的特点[通俗易懂]

    Java的特点[通俗易懂]

    Java的特点[通俗易懂]Java是一种“简单”、面向对象、分布式、解释型、健壮、安全、体系结构中立、可移植、高性能和动态的编程语言。简单：Java的设计目的是让专业程序员觉得既易学又好用。假设你有编程经历，你将不觉得Java难掌握，如果你已经理解面向对象编程的基本概念，学习Java见更加容易。面向对象：面向对象是现代编程语言的重要特征之一，面向对象技术极大的提高了人们的软件开发能力。分布

    全栈程序员-站长的头像 全栈程序员-站长
    2022年7月7日
    23
  • 项目警告：There are multiple modules with names that only differ in casing.This can lead to unexpected be…

    项目警告：There are multiple modules with names that only differ in casing.This can lead to unexpected be…

    项目警告：There are multiple modules with names that only differ in casing.This can lead to unexpected be…

    全栈程序员-站长的头像 全栈程序员-站长
    2021年6月17日
    114
  • Android开发：bindService的使用方法

    Android开发：bindService的使用方法

    Android开发：bindService的使用方法http://blog.csdn.net/zhou_wenchong/article/details/51302574bindService用于绑定一个服务。这样当bindService(intent,conn,flags)后，就会绑定一个服务。这样做可以获得这个服务对象本身，而用startService(intent)的方法只能启动服务。   bindService方式的一般过程：

    全栈程序员-站长的头像 全栈程序员-站长
    2022年6月8日
    39
  • mysql卸载步骤_系统应用怎么卸载步骤

    mysql卸载步骤_系统应用怎么卸载步骤

    mysql卸载步骤_系统应用怎么卸载步骤重装卸载了一下午，很多方法都尝试了，最后终于找到一个彻底删干净的方法：1.很多大佬都提到的cmd搜索regedit注册表，打开后找到下面三个目录并删除（要是没有不用管）HKEY_LOCAL_MACHINE/SYSTEM/ControlSet001/Services/Eventlog/Application/MySQLHKEY_LOCAL_MACHINE/SYSTEM/ControlSet002/Services/Eventlog/Application/MySQLHKEY_LOCAL_MACHIN

    全栈程序员-站长的头像 全栈程序员-站长
    2022年9月27日
    2
  • java写helloworld_Java编写的第一个程序：HelloWorld

    java写helloworld_Java编写的第一个程序：HelloWorld

    java写helloworld_Java编写的第一个程序：HelloWorld原理：Java文件需要编译后才能运行，编译命令为javacHelloWorld.java(使用javac.exe命令)，编译之后会出现以.class结尾的字节码文件(HelloWorld.class)。运行的是字节码文件，运行命令为javaHelloWorld在桌面上创建一个code文件夹，在code文件夹中创建一个HelloWorld.java文件1、编写代码在HelloWorld.jav…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年7月9日
    27
  • 在虚拟机上安装使用LoadRunner教程

    在虚拟机上安装使用LoadRunner教程

    在虚拟机上安装使用LoadRunner教程记录一下我的安装LoadRunner血泪史1.LoadRunner11在win10上使用总是出问题，后来看到只能在win7在用，就在VMware建了个win7镜像，在msdn(https://msdn.itellyou.cn/）上下了win7的cn_windows_7_enterprise_x64_dvd_x15-70741.iso，后来安装VMwareTools的时候会报“安装程序无法继续。本程序需要您将此虚拟机上安装的操作系统更新到SP1”这个才是能用的镜像：cn_windows_7_enter

    全栈程序员-站长的头像 全栈程序员-站长
    2022年5月23日
    91

发表回复

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

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