图论基本概念学习教案

1、图论图论(t ln)基本概念基本概念第一页，共52页。有多少辆汽车从城市P开到城市Q？最优支撑树问题：某一地区有若干个主要城市，拟修建高速公路把这些城市连接起来，使得从其中任何(rnh)一个城市都可以经高速公路直接或间接到达另一个城市。假设已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？第1页/共52页第二页，共52页。无序集AB=(x,y) | xAyB第2页/共52页第三页，共52页。V = v1, v2, ,v5, E = (v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v

2、4,v5) 则 G = 为一无向图第3页/共52页第四页，共52页。注意：图的数学定义(dngy)与图形表示，在同构（待叙）的意义下是一一对应的第4页/共52页第五页，共52页。第5页/共52页第六页，共52页。第6页/共52页第七页，共52页。8. 邻域邻域(ln y)与关联集与关联集 vV(G) (G为无向图为无向图) v 的关联的关联(gunlin)集集 v V(D) (D为有向图为有向图)9. 标定图与非标定图标定图与非标定图(顶点和边指定顶点和边指定(zhdng)编号的）编号的）10. 基图（有向图的有向边改为无向边）基图（有向图的有向边改为无向边）相关概念相关概念第7页/共52页第

3、八页，共52页。简单图是极其重要的概念第8页/共52页第九页，共52页。 (3) (G)（最大度）, (G)（最小度） 无向图中 (4) +(D), +(D), (D), (D), (D), (D) (5) 度数(d shu)为1的点称为悬挂点，关联的边为悬挂边；奇顶点度与偶度顶点第9页/共52页第十页，共52页。定理定理(dngl)14.1 (dngl)14.1 设设G=G=为任意无向图，为任意无向图，V=v1,v2,vn, |E|=m, V=v1,v2,vn, |E|=m, 则则证 G中每条边 (包括环) 均有两个端点(dun din)，所以在计算G中各顶点度数之和时，每条边均提供2度，m

4、 条边共提供 2m 度.此二定理(dngl)是欧拉1736年给出，是图论的基本定理(dngl)握手定理握手定理定理定理14.2 设设D=为任意有向图，为任意有向图，V=v1,v2,vn, |E|=m, 则则第10页/共52页第十一页，共52页。由于2m, 均为偶数，所以为偶数，但因为V1中顶点度数为奇数(j sh)，所以|V1|必为偶数. 第11页/共52页第十二页，共52页。d+(v2), , d+(vn) D的入度列：d(v1), d(v2), , d(vn) 3. 非负整数列d=(d1, d2, , dn)是可图化的，是可简单图化的.易知：(2, 4, 6, 8, 10)，(1, 3,

5、3, 3, 4) 是可图化的，后者又是可简单图化的，而(2, 2, 3, 4, 5)，(3, 3, 3, 4) 都不是(b shi)可简单图化的，特别是后者也不是(b shi)可图化的第12页/共52页第十三页，共52页。(f(vi),f(vj)（）的重数相同，则称G1与G2是同构的，记作G1G2. l图之间的同构关系具有自反性、对称性和传递性图之间的同构关系具有自反性、对称性和传递性.l能找到多条同构的必要条件，但它们全不是充分条件：能找到多条同构的必要条件，但它们全不是充分条件：l 边数相同，顶点数相同边数相同，顶点数相同; 度数列相同度数列相同; l 对应顶点的关联集及邻域的元素对应顶点

6、的关联集及邻域的元素(yun s)个数相同，等等个数相同，等等l 若破坏必要条件，则两图不同构若破坏必要条件，则两图不同构l判断两个图同构是个难题判断两个图同构是个难题第13页/共52页第十四页，共52页。 (1) (2) (3) (4) 图中，图中，(1)与与(2)不同不同(b tn)构（度数列不同构（度数列不同(b tn)），），(3)与与(4)也不同也不同(b tn)构构. (1) (2) 第14页/共52页第十五页，共52页。(3) n (n1) 阶竞赛(jngsi)图基图为Kn的有向简单图.简单性质：边数 1,2)1( nnnm 第15页/共52页第十六页，共52页。 (1) (2)

7、 (3)定义定义(dngy)14.7 n 阶阶k正则图正则图=k 的无向简单图的无向简单图简单性质：边数（由握手定理得）简单性质：边数（由握手定理得）Kn是是 n1正则图，正则图，彼得松图（见书上图彼得松图（见书上图14.3(1) 所示，记住它）所示，记住它）第16页/共52页第十七页，共52页。(5) E（EE且E）的导出子图，记作GE第17页/共52页第十八页，共52页。例例2 画出画出K4的所有的所有(suyu)非同构的生成子图非同构的生成子图实例实例(shl)第18页/共52页第十九页，共52页。. 问：互为自补图的两个图的边数有何关系？第19页/共52页第二十页，共52页。(2) 简

8、单(jindn)通路与回路：所有边各异，为简单(jindn)通路，又若v0=vl，为简单(jindn)回路(3) 初级通路(路径)与初级回路(圈)：中所有顶点各异，则称为初级通路(路径)，又若除v0=vl，所有的顶点各不相同且所有的边各异，则称为初级回路(圈)(4) 复杂通路与回路：有边重复出现第20页/共52页第二十一页，共52页。的为例） 定义意义下无向图：图中长度为l（l3）的圈，定义意义下为2l个有向图：图中长度为l（l3）的圈，定义意义下为l个 同构意义下：长度相同的圈均为1个试讨论l=3和l=4的情况第21页/共52页第二十二页，共52页。存在 vi 到自身的回路，则一定存在vi

9、到自身长度(chngd)小于或等于 n 的回路.推论 在一个n 阶图G中，若存在 vi 到自身的简单回路，则一定存在长度(chngd)小于或等于n 的初级回路.第22页/共52页第二十三页，共52页。，称G连通 V/R=V1,V2,Vk，称GV1, GV2, ,GVk为连通分支，其个数 p(G)=k (k1)； k=1，G连通第23页/共52页第二十四页，共52页。 d(u,v)=d(v,u) d(u,v)+d(v,w)d(u,w)第24页/共52页第二十五页，共52页。定义14.16 G=, VV V为点割集p(GV)p(G)且有极小性 v为割点v为点割集定义14.17 G=, EE E是边

10、割集p(GE)p(G)且有极小性 e是割边（桥）e为边割集第25页/共52页第二十六页，共52页。割集，e8是桥，e7,e9,e5,e6 是边割集吗？几点说明：几点说明：Kn中无点割集，中无点割集，Nn中既无点割集，也无边中既无点割集，也无边(wbin)割集，其中割集，其中Nn为为 n 阶零图阶零图. 若若G 连通，连通，E为边割集，则为边割集，则 p(GE)=2，V为点割集，则为点割集，则 p(GV)2 第26页/共52页第二十七页，共52页。min|E|E为边割集若G非连通，则(G) = 0若(G)r，则称G是 r 边-连通图图中，=1，它是 1-连通图 和 1边-连通图第27页/共52页

11、第二十八页，共52页。不是(r+s)-边连通图，s1l, , 之间的关系.l定理(dngl)7.5 (G)(G)(G)l请画出一个的无向简单图第28页/共52页第二十九页，共52页。类似(li s)于无向图中，只需注意距离表示法的不同(无向图中d(vi,vj)，有向图中d) 及 d无对称性第29页/共52页第三十页，共52页。定理14.8 D强连通当且仅当D中存在经过每个顶点至少一次的回路定理14.9 D单向(dn xin)连通当且仅当D中存在经过每个顶点至少一次的通路第30页/共52页第三十一页，共52页。为 l 的路径扩大成了长度为 l+k 的路径），称l+k为“极大路径”，称使用此种方法

12、证明问题的方法为“扩大路径法”.有向图中类似讨论，只需注意，在每步扩大中保证有向边方向的一致性.第31页/共52页第三十二页，共52页。(2),(3),(4)中实线边所示的都是它扩展成的极大路径. 还能找到另外的极大路径吗？ (1) (2) (4) (3)第32页/共52页第三十三页，共52页。证证 设设 = v0v1vl 是由初始路径是由初始路径 0 用扩大路径法的得到的极用扩大路径法的得到的极大路径，则大路径，则 l （为什么？）（为什么？）. 因为因为(yn wi)v0 不与不与 外顶点相邻，又外顶点相邻，又 d(v0) ，因而在，因而在 上除上除 v1外，至少还存在外，至少还存在 1个

13、顶点与个顶点与 v0 相邻相邻. 设设 vx 是离是离 v0 最远的顶最远的顶点，于是点，于是 v0v1vxv0 为为 G 中长度中长度 +1 的圈的圈. 第33页/共52页第三十四页，共52页。补顶点子集，常将二部图G记为. 又若G是简单二部图，V1中每个顶点均与V2中所有的顶点相邻，则称G为完全二部图，记为 Kr,s，其中r=|V1|，s=|V2|. 注意，n 阶零图为二部图. 第34页/共52页第三十五页，共52页。第35页/共52页第三十六页，共52页。第36页/共52页第三十七页，共52页。有向图的关联矩阵（无环有向图） 定义(dngy)14.25 有向图D=，令则称 (mij)nm

14、为D的关联矩阵，记为M(D). (4) 平行平行(pngxng)边对应的列相同边对应的列相同性质性质(xngzh)有向图的关联矩阵第37页/共52页第三十八页，共52页。第38页/共52页第三十九页，共52页。推论推论(tuln) 设设Bl=A+A2+Al（l1），则），则 Bl中元素中元素为D中长度为 l 的通路(tngl)总数，定理定理14.11 设设 A为有向图为有向图 D 的邻接矩阵，的邻接矩阵，V=v1, v2, , vn为顶点为顶点(dngdin)集，则集，则 A 的的 l 次幂次幂 Al（l1）中元素）中元素为D中vi 到vj长度为 l 的通路数，其中为vi到自身长度为 l 的回

15、路数，而为为D中长度小于或等于中长度小于或等于 l 的回路数的回路数为为D中长度小于或等于中长度小于或等于 l 的通路数的通路数. 邻接矩阵的应用邻接矩阵的应用为为D 中长度为中长度为 l 的回路总数的回路总数. 第39页/共52页第四十页，共52页。例例5 有向图有向图D如图所示，求如图所示，求 A, A2, A3, A4，并回答诸问题：，并回答诸问题：(1) D 中长度为中长度为1, 2, 3, 4的通路各有多少条？其中回路分别的通路各有多少条？其中回路分别(fnbi)为多少条？为多少条？(2) D 中长度小于或等于中长度小于或等于4的通路为多少条？其中有多少条回路？的通路为多少条？其中有

16、多少条回路？实例实例(shl)第40页/共52页第四十一页，共52页。(1) D中长度为中长度为1的通路的通路(tngl)为为8条，其中有条，其中有1条是回路条是回路. D中长度为中长度为2的通路的通路(tngl)为为11条，其中有条，其中有3条是回路条是回路. D中长度为中长度为3和和4的通路的通路(tngl)分别为分别为14和和17条，回路分别条，回路分别 为为1与与3条条.(2) D中长度小于等于中长度小于等于4的通路的通路(tngl)为为50条，其中有条，其中有8条是回路条是回路.实例实例(shl)求解求解第41页/共52页第四十二页，共52页。定义定义(dngy)14.27 设设D=

17、为有向图为有向图. V=v1, v2, , vn, 令令 有向图的可达矩阵有向图的可达矩阵(j zhn)（无限（无限制）制）称称 (pij)nn 为为D的可达矩阵，记作的可达矩阵，记作P(D)，简记为，简记为P. 由于由于(yuy)viV，vivi，所以，所以P(D)主对角线上的元素全为主对角线上的元素全为1. 由定义不难看出由定义不难看出, D 强连通当且仅当强连通当且仅当 P(D)为全为全1矩阵矩阵. 下图所示有向图下图所示有向图 D 的可达矩阵为的可达矩阵为第42页/共52页第四十三页，共52页。第43页/共52页第四十四页，共52页。l会判别有向图连通性的类型l熟练掌握用邻接矩阵及其幂

18、求有向图中通路与回路数的方法，会求可达矩阵第44页/共52页第四十五页，共52页。19阶无向图阶无向图G中，每个顶点中，每个顶点(dngdin)的度数不是的度数不是5就是就是6. 证明证明G中至少有中至少有5个个6度顶点度顶点(dngdin)或至少有或至少有6个个5度顶点度顶点(dngdin). 练习练习(linx)1证证 关键是利用握手定理的推论关键是利用握手定理的推论. 方法一：穷举法方法一：穷举法设设G中有中有x个个5度顶点，则必有度顶点，则必有(9x)个个6度顶点，由握手定理推论可知，度顶点，由握手定理推论可知，(x,9x)只有只有5种可能种可能(knng)：(0,9), (2,7),

19、 (4,5), (6,3), (8,1）它们都满足要求）它们都满足要求. 方法二：反证法方法二：反证法否则，由握手定理推论可知，否则，由握手定理推论可知，“G至多有至多有4个个5度顶点并且至多有度顶点并且至多有4个个6度顶点度顶点”，这与，这与G是是 9 阶图矛盾阶图矛盾. 第45页/共52页第四十六页，共52页。2数组数组2, 2, 2, 2, 3, 3能简单能简单(jindn)图化吗？若能，画出尽可能多的非同构的图来图化吗？若能，画出尽可能多的非同构的图来. 练习练习(linx)2只要能画出只要能画出6 阶无向简单阶无向简单(jindn)图，就说明它可简单图，就说明它可简单(jindn)图化图化. 下图的下图的4个图都以此数列为度数列，请证明它们彼此不同构，都是个图都以此数列为度数列，请证明它们彼此不同构，都是K6的子图的子图.第46页/共52页第四十七页，共52页。用扩大路径法证明用扩大路径法证明.情况一：情况一： +. 证明证明D中存在长度中存在长度(chngd) +1的圈的圈. 设设 = v0v1vl为极大路径，则为极大路径，则l (为什么为什么?)