《信息安全数学基础 普通高等教育“十一五”国家级规划教材 教学课件 ppt 作者 裴定一 徐祥1212.handout》由会员分享，可在线阅读，更多相关《信息安全数学基础 普通高等教育“十一五”国家级规划教材 教学课件 ppt 作者 裴定一 徐祥1212.handout（73页珍藏版）》请在金锄头文库上搜索。
1、基本概念 连通性 矩阵表示 树 欧拉图与哈密顿图 M序列 图论 广州大学信息安全研究所 2007-03-15 广州大学信息安全研究所信息安全数学课件 基本概念 连通性 矩阵表示 树 欧拉图与哈密顿图 M序列 有向图和无向图 基本理论 完全图 子图和导出子图 七桥问题 12.1 基本概念 广州大学信息安全研究所信息安全数学课件 基本概念 连通性 矩阵表示 树 欧拉图与哈密顿图 M序列 有向图和无向图 基本理论 完全图 子图和导出子图 七桥问题 有向图和无向图 Defi nition 有向图是一个有序偶 =，其中V 和E是集合，V 中的 元素称为有向图的顶点，E中的元素称为有向图的弧，E中每 条弧
2、连接V 中的一个有序顶点对。 Defi nition 无向图G是一个有序偶G =，其中V 和E是集合，V 中的 元素称为无向图G的顶点，E中的元素称为无向图G的边，G中 每条边是连接V 中的一个无序顶点对。 有向图和无向图统称为图。我们总假设顶点集V 和边(弧) 集E是 有限集且V 非空，即有限图。 广州大学信息安全研究所信息安全数学课件 基本概念 连通性 矩阵表示 树 欧拉图与哈密顿图 M序列 有向图和无向图 基本理论 完全图 子图和导出子图 七桥问题 例子 Example 有向图的弧e E是从一个顶点指向另一个顶点的弧线。若e是 从顶点u指向顶点v，则记e = (u,v)。下图(1)给出一
3、个有向 图1=, 其中V = u,v,w, E = e1= (u,v), e2= (v,u), e3= (v,w), e4= (w,u), e5= (w,w)。 Example 无向图G中的边e E连接顶点u和v，则记成e = (u,v) 或e = (v,u)。下图(2)给出了一个无向图G =，其 中V = u,v,w, E = e1, e2, e3, e4。 广州大学信息安全研究所信息安全数学课件 基本概念 连通性 矩阵表示 树 欧拉图与哈密顿图 M序列 有向图和无向图 基本理论 完全图 子图和导出子图 七桥问题 t - t t I ? ? ? ? k uv w e1 e2 e4e3 e5
4、tt t v ? ? ? ? w u je4 e1e3 e2 (1)(2) 广州大学信息安全研究所信息安全数学课件 基本概念 连通性 矩阵表示 树 欧拉图与哈密顿图 M序列 有向图和无向图 基本理论 完全图 子图和导出子图 七桥问题 Defi nition 一个顶点到它自身的弧(边)，这样的弧称为(边)称为自圈；如果 两个顶点之间的同向弧(边)多于一条，则这些弧(边)，称为平行 弧(边)。具有平行弧(边)的图称为多重图，下面的图(1)就是一个 具有多重弧的有向图。一个无圈无平行弧(边)的图称为简单图。 Defi nition 当把实际问题化成图的时候，有时需要将附加信息放到图的弧或 边上，这些
5、附加信息称为弧或边的权。权可能是数、符号或其它 的量，给每条弧或边赋了权的图称为带权图。下面的图(2) 就是 一个带权的无向图。 广州大学信息安全研究所信息安全数学课件 基本概念 连通性 矩阵表示 树 欧拉图与哈密顿图 M序列 有向图和无向图 基本理论 完全图 子图和导出子图 七桥问题 tt t t t t t ? ? ? ? ? ? ? ? R R vw u e1 e2 e3 e4 e5 vw uz HH HH HH HH 32 2 1 1 (1)(2) Figure: 有向图和无向图 广州大学信息安全研究所信息安全数学课件 基本概念 连通性 矩阵表示 树 欧拉图与哈密顿图 M序列 有向图和
6、无向图 基本理论 完全图 子图和导出子图 七桥问题 Defi nition 在有向图 =中，设u是一个顶点，以u为始点的弧称 为u的引出弧，以u为终点的弧称为u的引入弧。 Defi nition 在有向图 =中, u V , 将u的引出弧的条数称为u的引 出次数，记为od(u)；将u的引入弧的条数称为u的引入次数，记 为id(u); d(u) = od(u) + id(u)称为u的次数。 在无向图中，与顶点u相连的边的条数称为u的次数，也记 为d(u)。 Defi nition 一个含有n个顶点，m条弧(边)的图也称为一个(n,m)图。 广州大学信息安全研究所信息安全数学课件 基本概念 连通性
7、 矩阵表示 树 欧拉图与哈密顿图 M序列 有向图和无向图 基本理论 完全图 子图和导出子图 七桥问题 Theorem 设 =是一个(n,m)图，V = u1,u2, ,un，则 n X i=1 d(ui) = 2m. Proof. 由于每条弧(边)都与两个顶点相连，因此一个图的所有顶点次数 之和一定是个偶数，等于弧(边)数的2倍，证毕。 广州大学信息安全研究所信息安全数学课件 基本概念 连通性 矩阵表示 树 欧拉图与哈密顿图 M序列 有向图和无向图 基本理论 完全图 子图和导出子图 七桥问题 Defi nition 一个无向图G，如果它的所有顶点都具有相同的次数r，则称 图G是一个r次正则图。
8、 在一个无向的(n,m)图中，如果它的任何两个顶点之间都有一条 边，则称这样的图为完全图，记成Kn；若D是一个有向 图，D的任意两个顶点之间都有一条弧，则称D为有向完全图。 Example 图2 (1) 就是一个有三个顶点的二次正则图；图2 (2) 是一个 有6个顶点的三次正则图。 图3给出四个顶点的完全图K4。容易看出，完全图Kn是一个次 数r = n 1的正则图，其边数m = ?n 2 ? = n(n1) 2 。 广州大学信息安全研究所信息安全数学课件 基本概念 连通性 矩阵表示 树 欧拉图与哈密顿图 M序列 有向图和无向图 基本理论 完全图 子图和导出子图 七桥问题 t t t t r
9、r t r t? ? ? ? ? ? ? ? ? ? ? vw u u1 u4 u2u3 u5u6 ? ? H H H (1)(2) Figure: 有向图和无向图 t t t t b a c d ? ? ? ? HH HH HH HH Figure: 完全图 广州大学信息安全研究所信息安全数学课件 基本概念 连通性 矩阵表示 树 欧拉图与哈密顿图 M序列 有向图和无向图 基本理论 完全图 子图和导出子图 七桥问题 Defi nition 如果G1和G2都是图，且G1的顶点集和弧(边)集分别是G2的顶点 集和弧(边)集的子集合，则称G1是G2的子图。 Defi nition 设G1=是G2=的
10、子图。如果E1包含 了E2中所有关联于V1中顶点的弧(边)，即 E1= e|e = (u,v) E2, u,v V1, 则称G1是G2的导出子图，或称G1为G2的由V1导出的子图。 Defi nition 设G1=是G2=的子图。如果G1包含G2的 所有顶嘴，即V1= V2，则称G1是G2的生成子图。 广州大学信息安全研究所信息安全数学课件 基本概念 连通性 矩阵表示 树 欧拉图与哈密顿图 M序列 有向图和无向图 基本理论 完全图 子图和导出子图 七桥问题 哥尼斯堡七桥问题 Example 普雷格尔河横穿哥尼斯堡城，河中有两个小岛，城市的各个部分 由七座桥连接，如图4所示。城中的市民喜欢在河畔
11、沿着桥散 步，渐渐地产生一个问题：从四块陆地中任何一处出发，能否穿 得每座桥一次且仅一次，最后返回原出发地？这个问题看似很简 单，但没有一个人能够解决。1736年，欧拉将上述问题化成如 图5的一个图，最后证明是不可能做到的。这是因为要做到穿行 每座桥一次且仅一次，则每个顶点的次数必为偶数，而图5每个 顶点都是3次的，因此是不可能的。 广州大学信息安全研究所信息安全数学课件 基本概念 连通性 矩阵表示 树 欧拉图与哈密顿图 M序列 有向图和无向图 基本理论 完全图 子图和导出子图 七桥问题 Figure: 哥尼斯堡七桥问题 广州大学信息安全研究所信息安全数学课件 基本概念 连通性 矩阵表示 树
12、欧拉图与哈密顿图 M序列 有向图和无向图 基本理论 完全图 子图和导出子图 七桥问题 t t t t ? ? ? HH HH HH Figure: 哥尼斯堡七桥问题图 广州大学信息安全研究所信息安全数学课件 基本概念 连通性 矩阵表示 树 欧拉图与哈密顿图 M序列 通路 回路 距离 基本理论 无向图的连通性 12.2 连通性 广州大学信息安全研究所信息安全数学课件 基本概念 连通性 矩阵表示 树 欧拉图与哈密顿图 M序列 通路 回路 距离 基本理论 无向图的连通性 通路 Defi nition 在一个有向图中，一串弧a1, a2, , an称为一条通路，如果a1的 终点是a2的起点，a2的终点
13、是a3的起点, , an1的终点是an的 起点。通常将此通路记成(a1, a2, , an)。如果ai= (vi,vi+1), i = 1, 2, , n，则也可将此通路记成(v1, v2, , vn+1)。 Defi nition 在通路(a1, a2, , an) = (v1, v2, , vn+1)中，如果弧a1, a2, , an两两不同，则称此通路为简单通路；如果顶点v1, v2, , vn+1两两不同，则称此通路为基本通路。 注：基本通路一定是简单通路，而简单通路不一定是基本通路。 广州大学信息安全研究所信息安全数学课件 基本概念 连通性 矩阵表示 树 欧拉图与哈密顿图 M序列 通
14、路 回路 距离 基本理论 无向图的连通性 回路 Defi nition 如果一个通路的起点v1与终点vn+1相同，则称此通路为回路。如 果回路中每条弧只出现一次，则称此回路为简单回路；如果(v1, v2, , vn+1)是一个回路，v1, v2, , vn+1是顶点，v1, v2, , vn+1两两不同，v1= vn+1，则称此回路为基本回路。 Defi nition 一条通路P含有n条弧，则称通路P的长度为n，记为|P| = n。 Defi nition 如果u,v是有向图的两个顶点，且有一个通路以u为起点，v为 终点，则称顶点u可以到达顶点v。 广州大学信息安全研究所信息安全数学课件 基本
15、概念 连通性 矩阵表示 树 欧拉图与哈密顿图 M序列 通路 回路 距离 基本理论 无向图的连通性 Theorem 如果从顶点u可以到达v，则存在从u到v的基本通路。 Proof. 在从u到v的所有通路中选取一条最短的，设为(v1, , vt)，其 中v1= u, vt= v。如果它不是基本通路，则有1 i 的两个顶点，从u到v的最短通路的 长度d(u,v)称为u到v的距离，如果不存在从u到v的通路，则 记d(u,v) = 。 Defi nition 在有向图 =中，如果任意两个顶点u和v，从u可以到 达v，从v也可以到达v，则称是连通的。 Defi nition 有向图中一条通过所有顶点的通路
16、称为完备通路；一条通过所有 顶点的回路称为完备回路。 广州大学信息安全研究所信息安全数学课件 基本概念 连通性 矩阵表示 树 欧拉图与哈密顿图 M序列 通路 回路 距离 基本理论 无向图的连通性 Theorem 如果从u可以到达v，从v可以到达w，则 d(u,w) d(u,v) + d(v,w). Proof. 设d(u,v) = s, d(v,w) = t, 且(u, v2, , vs, v)是从u到v的最短通 路，(v, vs+1, , vs+t1, w)是从v到w的最短通路。则(u, v2, , v, vs+1, , vs+t1, w)是从u到w的一条通路，其长度 为s + t，故d(u,w) s + t = d(u,v) + d(v,w)。 广州大学信
