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

离散数学_十章-图 ( 4 ):图的表示和图的同构

📷10.4 图的表示和图的同构

  • 1. 图的表示
    • 1.1 邻接表
      • 1.1.1 简单图的邻接表
      • 1.1.2 有向图的邻接表
    • 1.2 邻接矩阵
    • ❗在邻接表和邻接矩阵之间取舍
    • 1.3 关联矩阵
  • 2. 图同构
  • 3. ⚡判断两个简单图是否同构

图的表示方式有很多种,选择最方便的表示有助于对图的处理~

有时,两个图具有完全相同的形式,从某种意义上就是两个图的顶点之间存在着一 一对应,这个对应保持边的对应关系。在这种情形下,就说这两个图是同构的。

1. 图的表示

1.1 邻接表

表示不带多重边的图的一种方式是列出这个图的所有边。

另一种表示不带多重边的图的方式是邻接表,它给出了与图中每个顶点相邻的顶点。

注意,终点的个数 = 起点的出度数

1.1.1 简单图的邻接表

在这里插入图片描述

1.1.2 有向图的邻接表

在这里插入图片描述

1.2 邻接矩阵

假设图 G = (V, E) 是一个简单图,其中 |V| = n( 顶点集元素的个数(顶点的个数)为n ) 假设把G 的顶点任意排列成 v1, v2, … , vn。G 的邻接矩阵 A(或AG) 是一个n × n 的 0-1矩阵,它满足这样的性质:当 vi 和 vj 相邻时第( i, j )项是1,否则为0

若邻接矩阵是AG = [ aij ],则在这里插入图片描述
注意!
邻接矩阵外面是方括号“ [ ] ”,不可写成“ | | ”(这样就是行列式了)

例题1:
用邻接矩阵表示图3所示的图。
在这里插入图片描述
🔴解:
把顶点排列成a, b, c, d,表示这个图的矩阵是:
在这里插入图片描述
例题2:

画出具有顶点顺序a,b,c,d的邻接矩阵的图
在这里插入图片描述
🔴解:
在这里插入图片描述
无向图 ⇒ 邻接矩阵对称
邻接矩阵对称 ⇏ 无向图

无向图的邻接矩阵一定是对称的,而有向图的邻接矩阵不一定对称

❗在邻接表和邻接矩阵之间取舍

当一个简单图包含的边相对较少,即该图是一个稀疏图时,通常邻接表比邻接矩阵更适合表示它

需要注意的是,稀疏图的邻接矩阵是稀疏矩阵,即矩阵中只有少量元素不为0。(有专门的技术表示和处理稀疏矩阵

👉稀疏矩阵可以用邻接表,稠密矩阵可以用邻接矩阵表示

1.3 关联矩阵

表示图的另一种常用方式是用关联矩阵

设G = (V,E)是无向图。设 v1, v2, … , vn 是的图G的顶点,而e1,e2,…,em 是该图的边。相对于V和E的这个顺序的关联矩阵是n×m的矩阵M=[mij],

其中在这里插入图片描述
任意一列有且仅有两个1(简单图)
每行" 1 "的个数 = 该行对应点的度

例题1:
用关联矩阵表示图6所示的图
在这里插入图片描述

🔴解:

在这里插入图片描述

例题2:
用关联矩阵表示图7所示的伪图:
在这里插入图片描述
🔴解:

在这里插入图片描述

2. 图同构

图的同构 类似于 “相似”

定义:简单图G1 = (V1, E1) 和 G2 = (V2, E2) 是简单图,若存在一对一的映上的从 V1到 V2的函数 f ,且 f 具有这样的性质:对 V1 中所有的a和b来说, a和b在 G1 相邻当且仅当 f(a) 和 f (b) 在 G2 中相邻,则称 G1 和 G2 是同构的。 这样的函数 f 称为同构

两个不同构的简单图称为非同构的

当两个简单图同构时,两个图的顶点之间具有保持相邻关系的一 一对应。所以,图的同构是一个等价关系。

在这里插入图片描述

在这里插入图片描述

3. ⚡判断两个简单图是否同构

证明两个图不同构并不困难。如果能找到某个属性,两个图中只有一个图具有这个属性,但该属性应该在同构时保持,就可以说这两个图不同构。

这种在图的同构中保持的属性称为图形不变量。比如同构的简单图必须有相同顶点数、相同边数,对应顶点的度相同,邻接矩阵相同。

① 顶点个数、对应顶点的度、边数相等

② 回路中顶点个数相等

③ 图G中顶点w、v相邻 iff 在图H中 f(w) 、f(v)相邻

例题1:
判定图 G 和 H 是否同构。

在这里插入图片描述

🔴解:

G的邻接矩阵:
在这里插入图片描述
H的邻接矩阵:

在这里插入图片描述
因为AG=AH,所以 f 是同构的 → G 和 H 是同构的

!!!( 考试时,越长得像的越不是同构 )

相关文章:

离散数学_十章-图 ( 4 ):图的表示和图的同构

📷10.4 图的表示和图的同构 1. 图的表示1.1 邻接表1.1.1 简单图的邻接表1.1.2 有向图的邻接表 1.2 邻接矩阵❗在邻接表和邻接矩阵之间取舍1.3 关联矩阵 2. 图同构3. ⚡判断两个简单图是否同构 图的表示方式有很多种,选择最方便的表示有助于对图的处理~ …...

MySQL锁的分类

MySQL锁的分类 全局锁 表级锁 ● 表锁 ● 元数据锁,Meta Data Lock,MDL锁 ● 意向锁 ● AUTO_INC 锁 行级锁(Innodb引擎牛比的地方) ● record lock,记录锁,也就是仅仅把一条记录给锁上了 ● gap lock,间隙锁&#xff…...

程序员如何给变量起名字

程序员如何给变量起名字 在编写代码时,为变量命名是非常重要的。良好的命名习惯可以提高代码的可读性和可维护性,使得其他开发者能够更容易地理解你的代码。在这篇文章中,我们将讨论程序员如何为变量选择合适的名称。 规范 首先&#xff0…...

隔板法(求解的组数)

文章目录 隔板法(求解的组数)隔板法扩展 例题 隔板法(求解的组数) 文章首发于我的个人博客:欢迎大佬们来逛逛 隔板法 隔板法能够解决的问题: 求线性不定方程的解的组数求相同元素分组的方案数 给我们 …...

智能文档处理黑科技,拥抱更高效的数字世界

目录 0 写在前面1 为何要关注智慧文档?2 图像弯曲矫正3 手写板反光擦除4 版面元素检测5 文档篡改检测总结 0 写在前面 近期,中国图象图形学学会文档图像分析与识别专业委员会与上海合合信息科技有限公司联合打造了《文档图像智能分析与处理》高峰论坛。…...

vue ts写法

Vue.js 和 TypeScript 结合使用可以让你的项目更加健壮和易于维护。在 Vue 3 中,你可以使用 Vue.js 的 Composition API 和 TypeScript 一起使用。以下是一个简单的 Vue.js 和 TypeScript 结合使用的例子: 首先,确保你已经安装了 Vue.js 和 T…...

Unity中的PostProcessBuild:深入解析与实用案例

Unity中的PostProcessBuild:深入解析与实用案例 在Unity游戏开发中,我们经常需要在构建完成后对生成的应用程序进行一些额外的处理。这时,我们可以使用Unity提供的PostProcessBuild功能。本文将详细介绍Unity中的PostProcessBuild方法&#…...

SimpleCG绘图函数(4)--绘制圆

在前一篇教程我们利用绘制矩形功能绘制了一个城市,接下来我们讲解另外一个同样重要且基础的图形----圆形。并一起看看该图形能绘制哪些应用呢。 绘制圆形相关函数如下: //圆心坐标(nXCenter,nYCenter),半径为nRatio//绘无填充制圆 void circle( int nXCenter, int …...

打包和优化

私人博客 许小墨のBlog —— 菜鸡博客直通车 系列文章完整版,配图更多,CSDN博文图片需要手动上传,因此文章配图较少,看不懂的可以去菜鸡博客参考一下配图! 系列文章目录 前端系列文章——传送门 后端系列文章——传送…...

linuxOPS基础_Linux文件管理

Linux下文件命名规则 可以使用哪些字符&#xff1f; 理论上除了字符“/”之外&#xff0c;所有的字符都可以使用&#xff0c;但是要注意&#xff0c;在目录名或文件名中&#xff0c;不建议使用某些特殊字符&#xff0c;例如&#xff0c; <、>、&#xff1f;、* 等&…...

C语言——数据在内存中的存储(上)

数据在内存中的存储 1. 数据类型的介绍 之前已经介绍过C语言中的基本数据类型了&#xff0c;主要有&#xff1a; char //字符数据类型short //短整型int //整形long //长整型long long //更长的整形float //单精度浮点数double //双精度浮点数 注意&#xff1a;C语言中是是没…...

LinkedIn 国际版怎么在国内登录?怎么使用领英国际版?

自从去年底国内用户使用LinkedIn就只能跳转到领英职场&#xff0c;而且就只是一个简单的招聘求职平台&#xff0c;没办法搜索添加国外客户&#xff0c;开发客户资源的效率大打折扣。但是国际版领英就不受影响&#xff0c;东哥今天就给各位做外贸的朋友分享如何使用国际版领英。…...

QThread Class

QThread QThread类枚举类型成员函数可重写函数公共槽信号静态成员函数保护函数静态保护函数QThread简单案例1QThread简单案例2 QThread类 标准头文件&#xff1a;#include <QThread> qmake: QT core 继承(父): QObject枚举类型 线程的优先级 enum Priority { IdlePri…...

C语言中的运算符及其优先级详解

引言&#xff1a; 在C语言中&#xff0c;运算符是用于进行各种数学和逻辑运算的符号。了解不同类型的运算符及其优先级对于正确理解和编写C语言代码至关重要。本文将详细介绍C语言中常用的运算符&#xff0c;包括算术运算符、赋值运算符、比较运算符、逻辑运算符等&#xff0c;…...

【C语言】语言篇——数组和字符串

C站的小伙伴们&#xff0c;大家好呀&#x1f61d;&#x1f61d;&#xff01;我最近在阅读学习刘汝佳老师的《算法竞赛入门经典》&#xff0c;今天将整理本书的第三章——数组和字符串的一些习题&#xff0c;本章习题较多&#xff0c;下选取部分习题进行练习总结&#xff0c;在这…...

Js写的二级联动和三级联动

二级联动的实现 第一步 在HTML页面创建两个 select 下拉列表元素&#xff0c;并设置id为 ‘province’和id ‘city’ <!--省份--> <select id"province" onchange"getCity()"></select><!--城市--> <select id"city&qu…...

一文带你了解UI自动化测试框架

PythonSeleniumUnittestDdtHTMLReport分布式数据驱动自动化测试框架结构 1、Business&#xff1a;公共业务模块&#xff0c;如登录模块&#xff0c;可以把登录模块进行封装供调用 ------login_business.py from Page_Object.Common_Page.login_page import Login_Page from H…...

【Linux】守护进程

守护进程&#xff08;Daemon&#xff09;是一种在后台运行的特殊进程。它通常在操作系统启动时启动&#xff0c;并一直运行直至系统关闭。它不与任何终端关联&#xff0c;并且没有标准输入、输出和错误流。它的主要作用是在系统启动后执行一些特定的任务或者提供某些服务&#…...

Vue中组件和插件有什么区别?

Vue中组件和插件有什么区别&#xff1f; 组件是什么 组件就是把图形、非图形的各种逻辑均抽象为一个统一的概念&#xff08;组件&#xff09;来实现开发的模式&#xff0c;在Vue中每一个.vue文件都可以视为一个组件 组件的优势 降低整个系统的耦合度&#xff0c;在保持接口…...

第五章 图像处理

文章目录 前言一、图像金字塔1.高斯金字塔2.拉普拉斯金字塔 二、图像轮廓1. 轮廓提取2. 轮廓绘制3. 轮廓特征4. 轮廓近似5. 轮廓标记 三、模板匹配四、直方图1. 对比度2. 绘制直方图3. 均衡化3.1 理论3.2 代码 4. CLAHE 五、图像傅里叶变换5.1 正弦平面波5.2 二维傅里叶变换5.3…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...

C++_哈希表

本篇文章是对C学习的哈希表部分的学习分享 相信一定会对你有所帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、基础概念 1. 哈希核心思想&#xff1a; 哈希函数的作用&#xff1a;通过此函数建立一个Key与存储位置之间的映射关系。理想目标&#xff1a;实现…...

pgsql:还原数据库后出现重复序列导致“more than one owned sequence found“报错问题的解决

问题&#xff1a; pgsql数据库通过备份数据库文件进行还原时&#xff0c;如果表中有自增序列&#xff0c;还原后可能会出现重复的序列&#xff0c;此时若向表中插入新行时会出现“more than one owned sequence found”的报错提示。 点击菜单“其它”-》“序列”&#xff0c;…...

基于 HTTP 的单向流式通信协议SSE详解

SSE&#xff08;Server-Sent Events&#xff09;详解 &#x1f9e0; 什么是 SSE&#xff1f; SSE&#xff08;Server-Sent Events&#xff09; 是 HTML5 标准中定义的一种通信机制&#xff0c;它允许服务器主动将事件推送给客户端&#xff08;浏览器&#xff09;。与传统的 H…...