第1章 图和子图[教育研究].ppt

上传人:scccc 文档编号:11332232 上传时间:2021-07-26 格式:PPT 页数:65 大小:1.27MB
返回 下载 相关 举报
第1章 图和子图[教育研究].ppt_第1页
第1页 / 共65页
第1章 图和子图[教育研究].ppt_第2页
第2页 / 共65页
第1章 图和子图[教育研究].ppt_第3页
第3页 / 共65页
第1章 图和子图[教育研究].ppt_第4页
第4页 / 共65页
第1章 图和子图[教育研究].ppt_第5页
第5页 / 共65页
点击查看更多>>
资源描述

《第1章 图和子图[教育研究].ppt》由会员分享,可在线阅读,更多相关《第1章 图和子图[教育研究].ppt(65页珍藏版)》请在三一文库上搜索。

1、图论及其应用,1 图的基本概念 2 树 3 连通度 4 遍历问题 5 匹配,6 着色问题 7 平面图 8 有向图 9 网络 10 NP-完全问题,1,章节课堂,第一章 图的基本概念,2,章节课堂,1.1 图的概念 1.2 同构 1.3 图的矩阵和顶点的度 1.4 子图 1.5 路和连通性 1.6 圈 1.7 最短路问题,3,章节课堂,1.1 图的概念,4,章节课堂,Knigsberg七桥问题 电网络 四色猜想,5,章节课堂,图 G = (V(G), E(G), 其中 V(G) = V -顶点集, -顶点数 E(G) = E -边集,-边数 例如,下图中, V=a, b,f, E=k,p, q

2、, ae, af, ,ce, cf ,6,章节课堂,注意, 右图仅仅是图G的一个几何实现(geometric realization,代表representation), 它们有无穷多个,随顶点位置及边的形状而不同。真正的图G是上面所给出式子,它与顶点的位置、边的形状等无关。不过今后对图G及其几何实现将经常不加以区别。,7,章节课堂,称 边 ad 与顶点a (及d) 相关联(incident)。也称顶点 b(及 f) 与边 bf 相关联 。 称顶点a与e 相邻(adjacent)。也称有公共端点的一些边,例如 p与af彼此相邻。 称一条边的两个顶点为它的两个端点 环(loop,selfloop

3、):如边 k ,它的两个端点相同。 棱(link):如边ae,它的两个端点不相同。 重边:如边p及边q。 简单图:(simple graph)无环,无重边 平凡图:仅有一个顶点的图。 注意:任何一图都有 V 。 记号: ( ,),8,章节课堂,例题 1.1 若G为简单图,则 。 1.2 若一群人中,凡相识的两人都无公共朋友,凡不相识的两人都恰有两个公共朋友,则每人的朋友数相等。,9,章节课堂,1.2 同构,10,章节课堂,例如在下图中,称 图G恒等于图H (记为 G = H) VG)=V(H), E(G)=E(H)。,11,章节课堂,图G同构于图F (记为 G F ) V(G)与V(F), E

4、(G)与E(F)之间各存在一 一映射, 及 且这二映射保持关联关系,即:,12,章节课堂,注 两个图同构是指”它们有相同的结构”,仅在顶点及边的标号上或两个图的画法上有 所不同而已。往往将同构慨念引伸到非标号图中,以表达两个图在结构上是否相同。 注 判定两个图是否同构是个未解决的困难问题(open problem)。,13,章节课堂,完全图(complete graph) Kn 空图(empty g.) E = 。 V ( V) 为独立集 V中任二顶点都互不相邻。 二部图 (偶图,bipartite g.) G = (X, Y ; E) 存在 V(G) 的一个 2-划分 (X, Y) (即V(

5、G)=X Y,且XY=),使X与Y 都是独立集。,14,章节课堂,完全二部图 Km,n 二部图G = (X, Y; E),其中X和Y之间的每对顶点都相邻,且 X = m, Y = n 。 类似地可定义,完全三部图(例如, Km,n,p),完全 n-部 图等。,15,章节课堂,例。用标号法判定二部图。用红蓝两种颜色进行顶点标号如下:任取一顶点v 标以红色。再将v的所有相邻顶点都标以兰色。这时称v为已扫描顶点。若尚存在一已标号未扫描顶点u,将它的所有相邻顶点,(若不出现矛盾)都标以(其相异色)红色,并称u为已扫描顶点。如此继续下去,直到或者所有顶点都已标号,从而该图为一二部图;或者在标号过程中出现

6、矛盾,该图为非二部图。,16,章节课堂,习题,1.2.1 G H (G) = (H) , (G) = (H) 。 并证明其逆命题不成立。 1.2.2 证明下面两个图不同构:,17,章节课堂,1.2.3 证明下面图1与图2是同构的; 而图1与图3是不同构的: 1.2.4 证明两个简单图G和H 同构 存在一 一映射 f : V(G) V(H) ,使 得 uv E(G)当且仅当 f(u)f(v) E(H) 。,18,章节课堂,1.2.5 证明:(a). (Km,n ) = mn ; (b). 对简单二部图有 2/4 . 1.2.6 记Tm,n为这样的一个完全m-部图:其顶点数为n,每个部分的顶点数为

7、n/m 或n/m个。证明: (a). (Tm,n) = 其中 k =n/m . (b)*. 对任意的n顶点完全m-部图G,一定有 (G) (Tm,n),且仅当G Tm,n 时等式才成立。 1.2.7 所谓k-方体是这样的图:其顶点是由0与1组成的有序k-元组,其二顶点相 邻当且仅当它们恰有一个坐标不同。证明k-方体有2k个顶点,k*2 k-1条边,且是一偶图。,19,章节课堂,1.2.8 简单图G的补图G c 是指和G有相同顶点集V的一个简单图,在G c中两个 顶点相邻当且仅当它们在G中不相邻。 (a). 画出Kcn和 Kcm,n。 (b). 如果G G c则称简单图G为自补的。证明:若G是自

8、补的,则 0, 1 (mod 4) 。 1.2.9 设 ,且 , 则H一定是个完全二部图。 1.2.10若 的简单图 中如下性质成立 则G一定是个完全(某)m部图。,20,章节课堂,1.3 图的矩阵和顶点的度,21,章节课堂,M(G)=mi,j , (关联矩阵) mi,j = 顶点vi与边ej 的关联次数= 0, 1, 2.,22,章节课堂,A(G)=ai,j, ai,j = 连接顶点vi 与 vj 的边数 。 (邻接矩阵),23,章节课堂,顶点 v的 度 dG(v) = G中与顶点v 相关联边数。(每一环记为2) 记号: 最大、最小度 , 。((G) , (G) ) 奇点:度为奇数的顶点;

9、偶点:度为偶数的顶点; 孤立点:度为0的顶点; 悬挂点:度为1的顶点; 悬挂边:悬挂点的关联边。,24,章节课堂,定理1.3 .1 (hand shaking lemma) 任一图中, 推论1.1 任一 图中,度为奇数顶点的个数为偶数。,25,章节课堂,例:任一多面体中,边数为奇数的外表面的数目为偶数。 (提示:作一图,其顶点对应于多面体的面,且二顶点相邻当且仅当对应的两个面相邻(即有公共边界)。) k-正则图 (k-regular g.) ,26,章节课堂,习题,1.3.1 证明: 2/ 。 1.3.2 若 k-正则偶图(k 0)的2-划分为 (X, Y),则 X = Y。 1.3.3 在人

10、数 1的人群中,总有二人在该人群中有相同的朋友数,27,章节课堂,1.3.4 设V(G) = ,则称 ( d(v1), d(v2), , d(v) ) 为G的度序列。 证明:非负整数序列 ( d1 ,d 2, d n) 为某一图的度序列 是偶数。 1.3.5 证明:任一 无环图G都包含一偶生成子图H,使得 dH(v) dG(v)/2 对所有v V 成立。 (提示:考虑G的边数最多的偶生成子图) 1.3.6* 设平面上有n个点,其中任二点间的距离 1,证明:最多有 3n对点的距离 = 1 。,28,章节课堂,1.4 子图,29,章节课堂,子图 (subgraph) H G V(H) V(G) ,

11、 E(H) E(G) 。 真子图 H G H G 且HG 。母图(super graph)。 生成子图(spanning subg.) H H G 且V(H) = V(G)。 生成母图。 基础简单图 (underlying simple g.):从一图中去掉其所有重边及环后所得的剩余(简单图)图称之为其基础简单图。 导出子图(induced subgraph.)GV, ( 非空 V V ) 以V为顶点集,以G中两端都在V上的边全体为边集构成的G的子图 边导出子图 GE (非空E E) 以E为边集,以E中所有边的端点为顶点集的的子图。,30,章节课堂,GV, GE 两种子图对应于取子图的两种基本

12、运算。 下面是取子图的另两种基本运算: G - V 去掉V及与V相关联的一切边所得的剩余子图。 即 GV V G - E 从中去掉E 后所得的生成子图,31,章节课堂,例。G - b, d, g, ( = GE b, d, g ) G - b, c, d, g, ( GE b, c, d, g ) G - a, e, f, g. ( GE a, e, f, g ) 注意 GE E 与G - E 虽有相同的边集,但两者不一定相等 :后者一定是生成子图,而前者则不然。,32,章节课堂,上述四种运算是最基本的取子图运算,今后经常会遇到,一定要认真掌握好。关于子图的另一些定义还有: G + E 往G上

13、加新边集E 所得的(G的)母图。 为简单计,今后将 G e 简记为 G e ; G - v 简记为 G - v 。 设 G1, G2 G ,称G1与G2为 不相交的(disjiont) V(G1) V(G2) = ( E(G1) E(G2) = ) 边不相交 (edge-distjiont,边不重的) E(G1) E(G2 ) = 。 (但这时G1与G2仍可能为相交的)。 并图 G1G2 , 当不相交时可简记为 G1+G2. 交图 G1 G2 .,33,章节课堂,习题,1.4.1 证明:完全图的每个导出子图是完全图;偶图的每个导出子图是偶图。 1.4.2* 设G为一 简单 图,1 n -1。证

14、明:若 4,且G中每个n顶点的导出子图均有相同的边数,则 G K或 Kc 。,34,章节课堂,1.5 路和连通性,35,章节课堂,途径 (walk) 例如图G的(u,x)-途径 W = ueyfvgyhwbvgydxdydx (有限非空序列) = uyvywvyxyx (简写法-当不引起混淆时),36,章节课堂,起点(origin) u 。 终点(terminus) x。 内部顶点(internal vertex) y, v, w, x。 (注意,中间出现的x也叫内部顶点。) 长 边数(重复计算)。 节(段,section)。 例如W的(y, w)-节=yvw 。 W-1 (逆途径), WW(

15、两条途径W与W相衔接。要求:W的终点=W的起点)。 迹( trail) 边各不相同的途径(顶点可重复出现)。 例如,yvwyx 。 路 (path) 顶点各不相同的途径。(边也一定不重复出现。路可当作一个图或子图)。例如, yvwx 。 距离 dG(u, v) = 图G中顶点u与v之间最短路的长。,uyvywvyxyx,37,章节课堂,定理1.5.1 G中存在(u, v)-途径 G中存在(u, v)-路。 证明:是显然的; :设G中存在 -途径 其中 若W中的顶点互不相同,则W就是(u, v)-路;不然,设其中有 ( ),则 也是一条 -途径,长度比W短 。若其中仍有重复顶点出现,则继续上述过

16、程。由于W 长度的有限性,上述过程必停止于一(u, v)-路 。,38,章节课堂,图的连通性:称G中顶点u与v为连通的(connected) G中存在 (u, v)-路 ( G中存在(u, v)-途径。) 容易验证,V上的连通性 是V上的等价关系,它将 V划分为一些等价类: V1 ,V 使每个Vi中的任二顶点都连通 (即存在(u, v)-路); 而不同Vi与Vj之间的任二顶点都不连通。,39,章节课堂,称每个 GVi i=1,2,. 为G的一个分支(component); 称(G)为G的分支数。 称 G为连通图 (G) = 1 G中任两点间都有一 条路相连。 称 G为非连通图 (G) 1。,4

17、0,章节课堂,记号: 对任一非空 SV ,令 = VS, 记 S, = G中两端分别在S及 中的一切边的集合。 (后文中将称为边割),41,章节课堂,容易证明: 定理1.5.2 G连通 对任 S V 都有 S, 例1.5 简单图G中, k G中有长 k 的路。 (注意到,G中任一最长路P的起点(终点)的所有邻接点全在P上。),42,章节课堂,习题,1.5.1 证明:G中长为k的 途径的数目, 就是A k 中的(I, j)元素,其中A为G的 邻接矩阵。 1.5.2 证明:对简单图G有, G连通。 对于 1,试给出 的不连通简单图。 1.5.3 证明简单图G中, /2 - 1 G连通。 当是偶数时

18、,试 给 出 一个不连通的(/2-1)正则简单图。,43,章节课堂,1.5.4 G不连通 Gc 连通。 1.5.5 对任意图G的任一边e,有 (G) (G-e) (G) +1 。 1.5.6 G连通,且 d(v)=偶数, v V (G-v) d(v)/2, v V. 1.5.7 连通图中,任二最长路必有公共顶点。 1.5.8 对任一图的任三个顶点 u, v, w 都有 d(u, v)+d(v, w) d(u, w)。 1.5.9 任一的简单、连通、非完全图中,一定有三个顶点 u, v, w, 使得uv, vw E 而 uw E。 1.5.10若图G 中恰有两个奇点u与v,则G中一定有一(u,v

19、)路。,44,章节课堂,1.6 圈,45,章节课堂,闭途径(closed walk) 起点=终点 且长 0 的途径。 闭迹 (closed trail) 边各不相同的闭途径。 圈(cycle) 顶点各不相同的闭迹。 (可当作一图或子图。),46,章节课堂,例: 闭途径: uyvyu ; uywxywvu ; uyuyu。 闭迹:uyxwyvu。 圈: yfvgy ; uywvu。 k-圈(k-cycle) 长为k的圈。 奇圈 (odd cycle)。 偶圈 (even cycle)。,47,章节课堂,例: 1-圈(即一条环), 2-圈(由两条重边组成), 3-圈(又称三角形)。,48,章节课堂

20、,定理1.2 G 为二部图 G不含奇圈。,证明: :设G的2-划分为(X, Y),由G的定义,G的任一圈中,X和Y的顶点一定交错出现,从而其长必为偶数。 :不妨设G为 连通的。 任取一顶点u,令 X = xV d(u, x) = 偶数 , Y = yV d(u, y) = 奇数。 易见,(X, Y)为V的2-划分,,49,章节课堂,所以只要再证X(和Y)都是G的独立集( 即X(或 Y)中任二顶点v, w都不相邻 )即可。 令P与Q分别为最短(u, v)-路与最短(u, w)-路。设u为P与Q的最后一个公共顶点; 而 P与Q分别为P的(u, v)-节与Q的(u, w)-节。则P与Q只有一公共顶点

21、。 又,由于P与Q的(u, u)-节的长相等, P与Q的长有相同的奇偶性,因此v与w不能相邻, 不然,v( P)1 Qwv 将是一奇圈,矛盾。,50,章节课堂,容易证明: 命题1 图G中 2 G中含圈。 命题2 简单图G, 2 G含长 +1 的圈。 (提示:以上两例中可考虑其最长路) 命题3 任一图G中 G含圈。 证明:反证,假设结论不成立,而G为其最小反例。则首先G是连通的,且 。再由以上第一例知,G中存在一顶点u, 。 于是, ,且显然G-u中也不含圈,从而G-u也是个反例,但顶点数比G少,矛盾。,51,章节课堂,习题,1.6.1 若边e在G的一闭迹中,则e在G的一圈中。 1.6.2 证明

22、: (a). G含圈。 (b)*. + 4 G含两个边不重的圈。 1.6.3 证明:任一连通偶图G=(X, Y)的2-划分 (X, Y)是唯一的。 (提示:不然,必有二顶点u,v,原属同一部(例如,)X,而在另一种2-划 分 则不然。),52,章节课堂,1.6.4证明或反证: (1).G中有两个不同的(u,v)路,则G中含一圈。 (2).G中有一闭途径,在则G中含一圈。 (3).G中有一长为奇数的闭途径,在则G中含一奇圈。 1.6.5 设图G 的顶点可用两种颜色进行着色,使每个顶点都至少与两个异色顶点邻,则G中一定包含偶圈。 1.6.6座位的教室中,不可能让每个学生都作一上下左右移动,使每个人

23、都换了座位。(提示:“座位图”是 一二部图),53,章节课堂,1.7 最短路问题,54,章节课堂,赋权图(weighted graph)G (注:权 1 时即为上文中所提的图。) 权( weight ) w(e) 0. 记号: w(H) = , H G . 路P的长 = w(P) 顶点u与v的 距离 d(u, v) = 最短(u, v)-路的长。,55,章节课堂,问题 求最短( u0, v0)-路。 转 求最短(u0, v)-路, v V u0. 简化 只考虑简单图,且w(e) 0 e E. ( w(uv) = 0 时, 可合并u与v为一 顶点)。,56,章节课堂,原理 逐步求出顶点序列 u1

24、, u2, . 使 d(u 0, u1) d(u 0, u2) . 记 S0 = u0 , Sk = u 0, u1,u k , = V S 。 Pi 为最短( u0, ui)-路 i = 1, 2, (1).求u1 : u1是使 w(u0 u1) = min w(u0v) v u 0 者 . 得 S1 = S0 u1 , P1 = u 0u1 .,57,章节课堂,(2). 若已求得Sk-1 ; d(u0, u1),d(u0, uk-1) ; 及最短 (u0, ui)路 Pi ,i=1.2,.,k-1 。 求uk :显然, d(u0, uk) = min d( u0, v) v = d(u0,

25、 uj ) + w( u ju k ) 某 j 1,2,,k-1 = min d( u0, u ) + w( uu k ) u S k-1 = mind( u0 , u ) + w(uv ) u S k-1 ,v = min l( v ) v 其中, l( v ) = min d( uo, u ) + w( uv ) u S k-1 ( l( uk ) = d( u0 , uk ) ),58,章节课堂, Sk = Sk-1 uk , Pk = Pj ujuk 某 j 1,2,k-1 。 update 进行下一 步时,只要更新 l(v) 即可: l( v ) min l( v ) , l( uk

26、 ) + w( ukv ) 对 v ,59,章节课堂,Dijkstra算法,(1).作为开始:l( u0 ) 0; l( v ) ; v u0; S0 u0 ; k 0 . (2). (这时已有Sk = u0, u1,uk) l( v ) min l( v ) , l(uk ) + w(ukv ) v 再计算 min l( v ) ,设其最小值点为 uk+1 ,令 Sk+1 = Sk uk+1 。 (3).若 k=-1, 停止;不然,令kk+1,并回到(2)。,60,章节课堂,计算复杂性 加法: (- 1)/2 比较: (- 1)/2 2 v : (-1)2 +) _ 共 O (2 ),61,

27、章节课堂,凡是复杂性为 p( , ) 的算法 ( p( . , . ) 为一多项式 ) 称为“好算法”( “good algorithm”-J.Edmonds )。这是相对于指数型算法而言的:在10 - 6秒/步运算速度下:,由上表可见,两种算法有天壤之别。,62,章节课堂,注 1.若只关心求d(u0,v0), 则算法进行到v0Sk时停止。 2.计算过程中,每步所得子图都是一 棵树(?:每步都是往其上增加一条边及一 个顶点)。因此该过程称为 tree growing procedure 。在该树中的(u0,v0)-路, 是中最短(u0,v0)-路 。 3.若要计录u0到每个顶点u的最短路,只要记录该路中u的前一个顶点(即该树中u的父亲)即可。,63,章节课堂,例,64,章节课堂,习题,1.7.1 描述一个算法以确定 (a). 一图的各个分支; (b). 一图的围长(即最短圈的长); 并说明你的算法好到什么程度。,65,章节课堂,

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 社会民生


经营许可证编号:宁ICP备18001539号-1