当前位置: 首页 > news >正文

图的同态Graph Homomorphism与同构Graph Isomorphism

  • 图的同态Graph Homomorphism

图的同态(Graph Homomorphism)是图论中的一个重要概念,用于描述图之间的一种映射关系。图的同态描述了一个图如何通过映射保留其边的结构。

### 图的同态定义

设有两个图 \( G = (V_G, E_G) \) 和 \( H = (V_H, E_H) \)。一个从图 \( G \) 到图 \( H \) 的映射 \( f: V_G \to V_H \) 被称为图的同态,如果对于 \( G \) 中的每一条边 \( (u, v) \in E_G \),在 \( H \) 中对应的边 \( (f(u), f(v)) \) 也在 \( E_H \) 中,即:
\[ \forall (u, v) \in E_G, (f(u), f(v)) \in E_H \]

这个定义意味着,图的同态映射保留了边的存在性,但不要求完全保留顶点间的连接关系。

### 例子

#### 例子 1:简单图的同态

**图 \( G \)(完全图 \( K_3 \))**:
- 顶点集合 \( V_G = \{a, b, c\} \)
- 边集合 \( E_G = \{(a, b), (b, c), (c, a)\} \)

**图 \( H \)(具有两个顶点和一条边的图)**:
- 顶点集合 \( V_H = \{x, y\} \)
- 边集合 \( E_H = \{(x, y)\} \)

**映射 \( f \)**:
- \( f(a) = x \)
- \( f(b) = x \)
- \( f(c) = y \)

**验证同态**:
- 对于 \( G \) 中的每一条边:
  - 边 \( (a, b) \) 映射到 \( (x, x) \),但 \( E_H \) 中只有边 \( (x, y) \),因此这条边的映射不是有效的。
  - 边 \( (b, c) \) 映射到 \( (x, y) \),这是有效的。
  - 边 \( (c, a) \) 映射到 \( (y, x) \),这也是有效的。

在这个例子中,映射 \( f \) 并没有完全保留边的结构,因为 \( (a, b) \) 在 \( H \) 中并没有对应的边。因而,\( f \) 并不是一个有效的同态。

#### 例子 2:完整图的同态

**图 \( G \)(有三个顶点和两条边的图)**:
- 顶点集合 \( V_G = \{1, 2, 3\} \)
- 边集合 \( E_G = \{(1, 2), (2, 3)\} \)

**图 \( H \)(有四个顶点和两条边的图)**:
- 顶点集合 \( V_H = \{a, b, c, d\} \)
- 边集合 \( E_H = \{(a, b), (b, c)\} \)

**映射 \( f \)**:
- \( f(1) = a \)
- \( f(2) = b \)
- \( f(3) = c \)

**验证同态**:
- 对于 \( G \) 中的每一条边:
  - 边 \( (1, 2) \) 映射到 \( (a, b) \),这在 \( H \) 中是存在的。
  - 边 \( (2, 3) \) 映射到 \( (b, c) \),这在 \( H \) 中也是存在的。

在这个例子中,映射 \( f \) 是一个有效的同态,因为每条边在 \( G \) 中都有相应的边在 \( H \) 中与之对应。

### 总结

- 图的同态保留了边的存在性,但不要求顶点间的连接关系完全一致。
- 同态映射可以用来研究图的结构特性和图的简化问题。
- 在第一个例子中,映射并不是有效的同态,因为并不是所有边都可以映射到目标图中;而在第二个例子中,映射是有效的同态,因为所有边在目标图中都有对应的边。

  • 同构Graph Isomorphism

图的同构(Graph Isomorphism)是图论中的一个核心概念,用于描述两个图在结构上的完全等价关系。两个图 \( G \) 和 \( H \) 被称为同构的,如果存在一个顶点的双射(双向一一映射) \( f: V_G \to V_H \),使得对于 \( G \) 中的每一条边 \( (u, v) \in E_G \),在 \( H \) 中有一条边 \( (f(u), f(v)) \in E_H \),且这种映射保留了图的边的连接关系。即:
\[ \forall (u, v) \in E_G, (f(u), f(v)) \in E_H \]

### 例子

#### 例子 1:三角形图的同构

**图 \( G \)(完全图 \( K_3 \))**:
- 顶点集合 \( V_G = \{a, b, c\} \)
- 边集合 \( E_G = \{(a, b), (b, c), (c, a)\} \)

**图 \( H \)(另外一个完全图 \( K_3 \))**:
- 顶点集合 \( V_H = \{x, y, z\} \)
- 边集合 \( E_H = \{(x, y), (y, z), (z, x)\} \)

**同构映射 \( f \)**:
- \( f(a) = x \)
- \( f(b) = y \)
- \( f(c) = z \)

**验证同构**:
- 对于 \( G \) 中的每一条边:
  - 边 \( (a, b) \) 映射到 \( (x, y) \),这在 \( H \) 中存在。
  - 边 \( (b, c) \) 映射到 \( (y, z) \),这在 \( H \) 中存在。
  - 边 \( (c, a) \) 映射到 \( (z, x) \),这在 \( H \) 中存在。

在这个例子中,映射 \( f \) 是一个有效的同构映射,因为它保留了边的结构,说明图 \( G \) 和图 \( H \) 是同构的。

#### 例子 2:具有不同标签的同构图

**图 \( G \)(两个三角形共享一个公共边)**:
- 顶点集合 \( V_G = \{a, b, c, d, e\} \)
- 边集合 \( E_G = \{(a, b), (b, c), (c, a), (b, d), (d, e), (e, b)\} \)

**图 \( H \)(另一个具有相同结构的图)**:
- 顶点集合 \( V_H = \{1, 2, 3, 4, 5\} \)
- 边集合 \( E_H = \{(1, 2), (2, 3), (3, 1), (2, 4), (4, 5), (5, 2)\} \)

**同构映射 \( f \)**:
- \( f(a) = 1 \)
- \( f(b) = 2 \)
- \( f(c) = 3 \)
- \( f(d) = 4 \)
- \( f(e) = 5 \)

**验证同构**:
- 对于 \( G \) 中的每一条边:
  - 边 \( (a, b) \) 映射到 \( (1, 2) \),这在 \( H \) 中存在。
  - 边 \( (b, c) \) 映射到 \( (2, 3) \),这在 \( H \) 中存在。
  - 边 \( (c, a) \) 映射到 \( (3, 1) \),这在 \( H \) 中存在。
  - 边 \( (b, d) \) 映射到 \( (2, 4) \),这在 \( H \) 中存在。
  - 边 \( (d, e) \) 映射到 \( (4, 5) \),这在 \( H \) 中存在。
  - 边 \( (e, b) \) 映射到 \( (5, 2) \),这在 \( H \) 中存在。

在这个例子中,映射 \( f \) 是一个有效的同构映射,因为它保留了边的结构,说明图 \( G \) 和图 \( H \) 是同构的。

### 总结

- **图的同构** 需要存在一个顶点的双射,使得图的每条边在两个图中都有对应的边,并且这种映射完全保留了图的结构。
- **例子 1** 展示了两个完全图 \( K_3 \) 的同构,它们的结构完全相同,但顶点标签不同。
- **例子 2** 展示了两个具有不同标签但结构相同的图,它们之间的映射也是同构的。

通过这些例子,可以看到图的同构不仅考虑了图的结构,而且还允许不同的顶点标签,只要边的连接关系被保留。

相关文章:

图的同态Graph Homomorphism与同构Graph Isomorphism

图的同态Graph Homomorphism 图的同态(Graph Homomorphism)是图论中的一个重要概念,用于描述图之间的一种映射关系。图的同态描述了一个图如何通过映射保留其边的结构。 ### 图的同态定义 设有两个图 \( G (V_G, E_G) \) 和 \( H (V_H, …...

使用 Python 对雷达卫星 sar 图像进行降噪的三种方法

合成孔径雷达 (SAR) 图像广泛应用于各种领域(航空航天、军事、气象等)。问题是这种图像在其原始格式中受到噪点的影响。虽然这些图像通常也是沉重的文件,但从科学的角度来看,有效地对其进行去噪的任务似乎既具有挑战性,又在现实世界中非常有用。 卫星图像有两大类: 光学…...

C# Unity 面向对象补全计划 之 初识继承方法与多态

本文仅作学习笔记与交流,不作任何商业用途,作者能力有限,如有不足还请斧正 本系列旨在通过补全学习之后,给出任意类图都能实现并做到逻辑上严丝合缝 1.继承方法 C# & Unity 面向对象补全计划 之 继承(字段与属性&…...

突破PyCharm索引瓶颈:提升文件索引速度的策略

突破PyCharm索引瓶颈:提升文件索引速度的策略 PyCharm作为Python开发者的首选IDE,以其强大的功能和灵活的配置而广受好评。然而,当处理大型项目或复杂文件结构时,文件索引慢的问题可能会显著降低开发效率。本文将提供一系列优化技…...

体素相关的快速计算

“体素”通常是指在三维空间中具有固定尺寸和位置的小立方体单元。 体素的优点包括: 易于处理和计算:在计算机图形学和三维建模中,体素的结构相对简单,计算和操作较为方便。能精确表示物体的内部结构:对于一些需要了…...

Python 爬虫项目实战(二):爬取微博热搜榜

前言 网络爬虫(Web Crawler),也称为网页蜘蛛(Web Spider)或网页机器人(Web Bot),是一种按照既定规则自动浏览网络并提取信息的程序。爬虫的主要用途包括数据采集、网络索引、内容抓…...

文件解析漏洞复现

一、IIS 6.X 1.在网站目录创建文件夹名为xxx.asp/xxx.asa 文件夹,里面的任意文件都会被当作asp文件执行 创建1.asp 访问 2.ooo.asp.jpg会被当做asp文件执行 创建一个ooo.asp;.jpg 访问 二、IIS 7.X 上传1.jpg文件在网址后/.php可以成功执行 写一个1.jpg文件内容…...

git push报错 pre-receive hook declined

今天使用git提交的代码的时候,不然报错 pre-receive hook declined提交不上去,昨天还好好的。 经过检查发现,原来对应的分支被leader设置成受保护分支了,导致代码提交不上去。 然后在git管理平台取消分支保护,或者将我…...

打造个性化代码审查工具:在Perl中实现自定义审查的艺术

打造个性化代码审查工具:在Perl中实现自定义审查的艺术 代码审查是软件开发过程中的关键环节,它有助于提高代码质量和发现潜在缺陷。Perl作为一种灵活的编程语言,提供了丰富的特性,使得在Perl中实现自定义的代码审查工具成为可能…...

RabbitMq架构原理剖析及应用

文章目录 RabbitMQ 架构组件1. **Broker** (Broker Server)2. **Exchange**3. **Queue**4. **Producer** (消息生产者)5. **Consumer** (消息消费者)6. **Virtual Hosts** (虚拟主机) 工作流程内部原理1. **队列管理**2. **集群**3. **持久化与内存**4. **性能优化** 高级特性1…...

c# 对接第三方接口实现签名

官网文档要求如下: Sign算法说明 举例:假设请求参数键值对如下 appkey : test2-xx page_no : 0 end_time : 2016-08-01 13:00:00 start_time : 2016-08-01 12:00:00 page_size : 40 sid : test2 timestamp : 1470042310 第一步 对数所有请求参数按照…...

数学建模评价类模型—层次分析法(无数据情况下)

目录 前言 一、评价类问题概述 二、AHP建模流程 1、过程描述 2、层次分析法—Matlab代码 三、权重计算 1、算术平均法 2、几何平均法 3、特征值法 目录 文章目录 前言 一、评价类问题概述 二、AHP建模流程 1、过程描述 2、层次分析法—Matlab代码 三、权重计算 算术平均法 前言…...

模拟实现strcat(字符串追加)

1.我们要知道stcat的作用是什么,字符串追加。 2.我们进行模仿,我们先将arr1不断,直到“\0”,我们加在后面。 //模拟实现strcat(字符串追加) char* my_strcat(char* arr1, const char* arr2) {assert(arr1 && arr2);char ret arr1;…...

HTTP简单概述

一. HTTP HTTP(HyperText Transfer Protocol)是用于在客户端和服务器之间传输超文本数据(如HTML)的应用层协议。它是万维网的基础协议,定义了浏览器和服务器之间如何请求和传输文档。HTTP有多个版本,每个版…...

掌握PyCharm代码片段管理器:提升编码效率的秘诀

掌握PyCharm代码片段管理器:提升编码效率的秘诀 PyCharm作为业界领先的集成开发环境(IDE),提供了许多便利的功能来提升开发者的编码效率,其中之一就是代码片段管理器。代码片段管理器允许开发者保存、管理和重用代码模…...

MyBatis动态代理和映射器

目录 1、映射器简介 (1)什么是mapper动态代理? (2)动态代理的规范 (3)如何使用动态代理 (4)为什么学映射器 (5)映射器与接口 (…...

ShardingSphere中的ShardingJDBC常见分片算法的实现

文章目录 ShardingJDBC快速入门修改雪花算法和分表策略核心概念分片算法简单INLINE分片算法STANDARD标准分片算法COMPLEX_INLINE复杂分片算法CLASS_BASED自定义分片算法HINT_INLINE强制分片算法 注意事项 ShardingJDBC Git地址 快速入门 现在我存在两个数据库,并…...

SpringBoot整合Flink CDC实时同步postgresql变更数据,基于WAL日志

SpringBoot整合Flink CDC实时同步postgresql变更数据,基于WAL日志 一、前言二、技术介绍(Flink CDC)1、Flink CDC2、Postgres CDC 三、准备工作四、代码示例五、总结 一、前言 在工作中经常会遇到要实时获取数据库(postgresql、m…...

ThinkPHP事件的使用

技术说明 1.ThinkPHP版本:支持6.0、8.0 2.使用场景:用户登陆后日志记录、通知消息发送等主流程、次流程分离等场景 3.说明:网上很多帖子说的不明不白的,建议大家自己手动尝试总结一下 4.事件手动绑定的时候,一定要…...

【Nuxt】服务端渲染 SSR

SSR 概述 服务器端渲染全称是:Server Side Render,在服务器端渲染页面,并将渲染好HTML返回给浏览器呈现。 SSR应用的页面是在服务端渲染的,用户每请求一个SSR页面都会先在服务端进行渲染,然后将渲染好的页面&#xf…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏

一、引言 在深度学习中&#xff0c;我们训练出的神经网络往往非常庞大&#xff08;比如像 ResNet、YOLOv8、Vision Transformer&#xff09;&#xff0c;虽然精度很高&#xff0c;但“太重”了&#xff0c;运行起来很慢&#xff0c;占用内存大&#xff0c;不适合部署到手机、摄…...

jdbc查询mysql数据库时,出现id顺序错误的情况

我在repository中的查询语句如下所示&#xff0c;即传入一个List<intager>的数据&#xff0c;返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致&#xff0c;会导致返回的id是从小到大排列的&#xff0c;但我不希望这样。 Query("SELECT NEW com…...