《离散数学课件图论(3)演示课件》由会员分享，可在线阅读，更多相关《离散数学课件图论(3)演示课件（46页珍藏版）》请在金锄头文库上搜索。
1、第四部分图论,图 论,实例1： 多用户操作系统中的进程状态变换,实例2： “七桥问题” 哥尼斯堡城的普雷格尔河,图 论,V=A, B, C, D E=e1, e2, e3, e4, e5 , e6, e7,后来欧拉证明这样的路径根本不存在。,图 论,实例3：在机械加工中，经常需要在一块金属薄板上钻若干孔 （或者是机械手在印刷电路板上安装电子元件）,问如何确定钻孔的次序,使之加工的时间最短？ 类似的问题： 旅行最优问题, 工程最优问题, 成本最低.,第十四章 图的基本概念,主要内容 图 通路与回路 图的连通性 图的矩阵表示,14-1 图,定义一个图表示为 G=, 其中 V(G): G的结点的非空
2、集合，简记成V。 E(G): 是G的边的集合， 有时简记成E。 结点(Vertices)：用 表示, 旁边标上该结点的名称。 边(Edges) 有向边: 带箭头的弧线。 从u到v的边表示成 无向边:不带箭头的弧线。 u和v间的边表示成 (u,v),14-1 图,实例 1. 设 V1= v1, v2, ,v5, E1 = (v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 则 G1 = 为一无向图,2. 设 V2 = a, b, c, d, E2 = , , , 则 G2 = 为一有向图,14-1 图,相关概念： 1. 图
3、可用G泛指图（无向的G或有向的D ） V(G), E(G), V(D), E(D) n阶图 2. n 阶零图与平凡图（ n 为顶点个数） 3. 用 ek 表示无向边或有向边 4. 顶点与边的关联关系 关联、关联次数 环 孤立点 5. 顶点之间的相邻与邻接关系,14-1 图,6. 邻域与关联集 vV(G) (G为无向图),v 的关联集, vV(D) (D为有向图),7. 标定图与非标定图 8. 基图,14-1 图,多重图与简单图 简单图：不含有环和平行边的图。 多重图：含有平行边的图。,14-1 图,定义 (1) 设G=为无向图, vV, d(v)v的度数, 简称度 (2) 设D=为有向图, v
4、V, d+(v)v的出度 d(v)v的入度 d(v)v的度或度数 (3) (G), (G) (4) +(D), +(D), (D), (D), (D), (D) (5) 奇度顶点与偶度顶点,14-1 图,握手定理,定理14-1.1 设G=为任意无向图，V=v1,v2,vn, |E|=m, 则,证明： G中每条边 (包括环) 均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，m 条边共提供 2m 度。,定理14-1.2 设D=为任意有向图，V=v1,v2,vn, |E|=m, 则,推论 任何图 (无向或有向) 中，奇度顶点的个数是偶数。,14-1 图,无向图的结点度序列,V=v1,
5、 v2, , vn为无向图G的顶点集，称d(v1), d(v2), , d(vn)为G的度数序列。 非负整数列d=(d1, d2, , dn)是可图化的，是可简单图化的。,n阶k正则图 一个无向简单图G中,如果(G)=(G)=k，则称G为k-正则图。,Kn是 n1正则图,14-1 图,练习: 1.下面哪些数的序列，可能是一个图度数序列? 如果是，试画出它的图。哪些是可简单图化的? a) (1, 2, 3, 4, 5) b) (2, 2, 2, 2, 2) c) (1, 2, 3, 2, 4) 2.已知无向简单图G中,有10条边，4个3度结点,其余结点的度均小于或等于2，问G中至少有多少个结点？
6、为什么？,14-1 图,图的同构 设G1=, G2=为两个无向图(两个有向 图)，若存在双射函数f:V1V2, 对于vi,vjV1, (vi,vj)E1 当且仅当 (f(vi),f(vj)E2 （E1 当且仅当 E2 ) 并且, (vi,vj)（）与 (f(vi),f(vj)（）的重数相 同，则称G1与G2是同构的，记作G1G2。,图之间的同构关系具有自反性、对称性和传递性 能找到同构的必要条件，但它们全不是充分条件： 边数相同，顶点数相同; 度数序列相同; 对应顶点的关联集及邻域的元素个数相同，等等 若破坏必要条件，则两图不同构 判断两个图同构是个难题,14-1 图,图同构实例,(1) (2
7、) (3) (4),图中，(1)与(2)不同构（度数列不同），(3)与(4)也不同构.,(1) (2),问：图中(1)与(2)的度数序列相同，它们同构吗？为什么？,14-1 图,完全图 无向完全图G是个简单图，如果每对不同顶点都相邻，则称G是个无向完全图。如果G有n个结点, 则记作Kn。 简单性质：边数 有向完全图G是个有向简单图，如果任意两个不同顶点之间都有方向相反的边,则称它是有向完全图。 简单性质：边数 竞赛图基图为Kn的有向简单图。,14-1 图,子图,定义：G=, G= (1) GG G为G的子图，G为G的母图 (2) 若GG且V=V，则称G为G的生成子图 (3) 若VV或EE，称G
8、为G的真子图 (4) V（VV且V）的导出子图，记作GV (5) E（EE且E）的导出子图，记作GE,14-1 图,例 画出K4的所有非同构的生成子图。,14-1 图,补图,定义：设G=为n阶无向简单图，以V为顶点集，以所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作 。 若G , 则称G是自补图。 相对于K4, 求上面图中所有图的补图，并指出哪些是自补图。 问：互为自补图的两个图的边数有何关系？,14-2 通路与回路,定义 给定图G=（无向或有向的），G中顶点与 边的交替序列 = v0e1v1e2elvl，vi1, vi 是 ei 的端点。 (1) 通路与回路： 为通路
9、；若 v0=vl， 为回路，l 为回路长 度。 (2) 简单通路与回路：所有边各异， 为简单通路，又若v0=vl， 为简单回路。 (3) 初级通路(路径)与初级回路(圈)： 中所有顶点各异，则称 为初级通路(路径)，又若除v0=vl，所有的顶点各不相同且所有的边各异，则称 为初级回路(圈)。 (4) 复杂通路与回路：有边重复出现。,14-2 通路与回路,表示法 定义表示法 只用边表示法 只用顶点表示法（在简单图中） 混合表示法 环（长为1的圈）的长度为1，两条平行边构成的圈长度为 2，无向简单图中，圈长3，有向简单图中圈的长度2. 不同的圈（以长度3的为例） 定义意义下 无向图：图中长度为l（
10、l3）的圈，定义意义下为2l个 有向图：图中长度为l（l3）的圈，定义意义下为l个 同构意义下：长度相同的圈均为1个,14-2 通路与回路,定理14-2.1 在n 阶图G中，若从顶点vi 到vj（vivj）存在通路，则从vi 到 vj 存在长度小于或等于n1 的通路. 推论 在 n 阶图G中，若从顶点vi 到 vj（vivj）存在通路，则 从vi 到vj 存在长度小于或等于n1的初级通路（路径）. 定理14-2.2 在一个n 阶图G中，若存在 vi 到自身的回路，则一定存在vi 到自身长度小于或等于 n 的回路. 推论 在一个n 阶图G中，若存在 vi 到自身的简单回路，则一定存在长度小于或等
11、于n 的初级回路.,14-3 图的连通性,1. 无向图的连通性 两个结点连通在无向图中，结点u和v之间如果存在一条通路，则称u与v是连通的。记作 uv 规定: 对任何结点u，uu。 结点之间的连通关系是个等价关系 令G=是无向图，R是V上连通关系，即 R=| u,v V且uv 显然R具有自反、对称和传递性。 于是可以求商集V/R。,例： 给定右图所示 V/R= a,b,g，c,d,e,f，h ,14-3 图的连通性,G的连通性与连通分支 若u, vV，uv，则称G是连通的 V/R=V1,V2,Vk，称等价类构成的子图GV1, GV2, ,GVk为G的连通分支，其个数 p(G)=k (k1)；
12、k=1，G是连通的。 下面实例中 p(G1)=3 p(G2)=2 p(G3)=1,14-3 图的连通性,距离 u与v之间的距离：d(u,v)u与v之间长度最短的通路。 d(u,v)的性质： d(u,v)0, uv时d(u,v)= d(u,v)=d(v,u) d(u,v)+d(v,w)d(u,w) 删除顶点及删除边 Gv 从G中将v及关联的边去掉 GV从G中删除V中所有的顶点 Ge 将e从G中去掉 GE删除E中所有边,14-3 图的连通性,点割集与边割集 定义： G=, VV V为点割集p(GV)p(G)且有极小性 v为割点v为点割集 定义： G=, EE E是边割集p(GE)p(G)且有极小性
13、 e是割边（桥）e为边割集,上例中v2,v5是点割集吗？e7,e9,e5,e6 是边割集吗？,例：v1,v4，v6是点割集，v6是割点。 e1,e2，e1,e3,e5,e6，e8等是边割集，e8是桥。,14-3 图的连通性,说明 Kn中无点割集，Nn中既无点割集，也无边割集，其中Nn为 n 阶零图. 若G 连通，E为边割集，则 p(GE)=2，V为点割集，则 p(GV)2 点连通度 G为连通非完全图，(G) = min |V |V 为点割集 规定 (Kn) = n1 若G非连通，(G) = 0; 若 (G)=k，则称G为 k-连通图 边连通度G为连通图，(G) = min|E|E为边割集 若G
14、非连通，则(G) = 0 若(G)=r，则称G是 r -边连通图 问题：求上例中的点连通度和边连通度。,14-3 图的连通性,说明 (Kn)=(Kn)=n1 G非连通，则 =0 若G中有割点，则=1，若有桥，则=1 若(G)=k, 则G是1-连通图，2-连通图，k-连通图，但不是(k+s)-连通图，s1 若(G)=r, 则G是1-边连通图，2-边连通图，r-边连通图，但不是(r+s)-边连通图，s1 , , 之间的关系. 定理14-3.1 (G)(G)(G) 问题：请画出一个的无向简单图。,14-3 图的连通性,2. 有向图的连通性 定义 D=为有向图 vi vj（vi 可达 vj）vi 到v
15、j 有通路 vi vj（vi 与vj 相互可达） 性质 具有自反性(vi vi)、传递性 具有自反性、对称性、传递性 vi 到vj 的距离 类似于无向图中，只需注意距离表示法的不同 (无向图中d(vi,vj)，有向图中d) 及 d无对称性,14-3 图的连通性,定义 D=为有向图 D弱连通(连通)基图为无向连通图 D单向连通vi,vjV，vivj 或 vjvi D强连通vi,vjV，vivj 易知，强连通单向连通弱连通 定理14-3.1 D强连通当且仅当D中存在经过每个顶点至少一次 的回路。 例 判断下面图的连通性。,14-4 图的矩阵表示,1. 邻接矩阵 以结点与结点之间的邻接关系确定的矩阵
16、。 定义设D=是个有向图，V=v1,v2,v3,vn , 一个nn阶矩阵A=(aij)称为D的邻接矩阵。 其中： aij为顶点vi邻接到顶点vj边的条数。,14-4 图的矩阵表示,例： 给定无向图G1和有向图G2如图所示，求邻接矩阵。,性质,邻接矩阵的乘积,14-4 图的矩阵表示,在(A(G1)2 中a342 =2 表示从v3到v4有长度为2的路有2条。 在(A(G1)3中a233 =6 表示从v2到v3有长度为3的路有6条。,邻接矩阵的乘积,14-4 图的矩阵表示,为D中长度为 l 的通路总数，,定理14-4.1 设 A为有向图 D 的邻接矩阵，V=v1, v2, , vn为顶点集，则 A 的 l 次幂 Al（l1）中元素,为D中vi 到vj长度为 l 的通路数，其中,为vi到自身长度为 l 的回路
