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

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

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


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


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 是同构的


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

相关文章
|
机器学习/深度学习 算法 数据挖掘
图神经网络02-图与图学习(下)
图神经网络02-图与图学习(下)
484 0
图神经网络02-图与图学习(下)
|
算法 容器
图压实算法
## 一、定义 将一个原本较为稀疏的图布局,进行压实操作,从而提高画布空间利用率,便于用户理解。 ## 二、适用场景 1. 图面积最小化:即移除多余的空间,将稀疏图变为紧密图。 1. 布局编译:从符号布局生成蒙版布局,电路板。 1. 重新设计:自动清除违反设计规则的情况。 1. 重新缩放:将蒙版级别的布局从一种技术转换到另一种。 在实际场景中,通常用于电路板的排版中。
290 0
图压实算法
|
5月前
|
人工智能 算法
图搜算算法分类
图搜索算法是计算机科学中用于遍历或搜索图结构(由节点和边组成的数学结构)的技术,常应用于路径规划、网络分析、人工智能等领域。下面是对几种常见图搜索算法的简要说明:
|
7月前
|
机器学习/深度学习 数据可视化 PyTorch
基于TorchViz详解计算图(附代码)
基于TorchViz详解计算图(附代码)
265 0
离散数学_十章-图 ( 2 ):图的术语和几种特殊的图(一)
离散数学_十章-图 ( 2 ):图的术语和几种特殊的图(一)
121 0
|
机器学习/深度学习
离散数学_十章-图 ( 2 ):图的术语和几种特殊的图(二)
离散数学_十章-图 ( 2 ):图的术语和几种特殊的图(二)
2515 0
|
算法 数据中心
离散数学_十章-图 ( 1 ):图的相关定义
离散数学_十章-图 ( 1 ):图的相关定义
179 0
|
Java
离散数学_十章-图 ( 3 ):由旧图构造新图
离散数学_十章-图 ( 3 ):由旧图构造新图
147 0
|
前端开发 算法 JavaScript
【戏玩算法】12-图
在上一篇文章中我们用了很大的篇幅来介绍红黑树,这篇文章我们来简单的学习一下图这个数据结构。
105 0
【戏玩算法】12-图