深圳坑梓网站建设公司,建立一个app需要多少钱,我的世界做指令的网站,wordpress 响应式产品展示站#x1f4f7;10.4 图的表示和图的同构 1. 图的表示1.1 邻接表1.1.1 简单图的邻接表1.1.2 有向图的邻接表 1.2 邻接矩阵❗在邻接表和邻接矩阵之间取舍1.3 关联矩阵 2. 图同构3. ⚡判断两个简单图是否同构 图的表示方式有很多种#xff0c;选择最方便的表示有助于对图的处理~
… 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
画出具有顶点顺序abcd的邻接矩阵的图 解 无向图 ⇒ 邻接矩阵对称 邻接矩阵对称 ⇏ 无向图
无向图的邻接矩阵一定是对称的而有向图的邻接矩阵不一定对称
❗在邻接表和邻接矩阵之间取舍
当一个简单图包含的边相对较少即该图是一个稀疏图时通常邻接表比邻接矩阵更适合表示它。
需要注意的是稀疏图的邻接矩阵是稀疏矩阵即矩阵中只有少量元素不为0。有专门的技术表示和处理稀疏矩阵
稀疏矩阵可以用邻接表稠密矩阵可以用邻接矩阵表示
1.3 关联矩阵
表示图的另一种常用方式是用关联矩阵
设G (VE)是无向图。设 v1, v2, … , vn 是的图G的顶点而e1e2…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的邻接矩阵 因为AGAH所以 f 是同构的 → G 和 H 是同构的 考试时越长得像的越不是同构
