《离散数学图论》PPT课件.ppt

1、第八章 图论(Graph Theory),8.1 图的基本概念(Graph) 8.2 路与图的连通性(Walks 特别地, (n,0)称为零图, (1,0) 图称为平凡图 。在零图中边集为空集。 (2) 按G中关联于同一对结点的边数分为多重图和简单图; 多重图:含有平行边的图（如图 8 .1. 3） ； 线 图: 非多重图称为线图； 简单图:不含平行边和自环的图。,8.1 图的基本概念,G1、G2是多重图,G3是线图,G4是简单图,(3)按G的边有序、无序分为有向图、无向图和混合图; 有向图：每条边都是有向边的图称为有向图 （图 8 .1.4 (b)； 无向图：每条边都是无向边的图称为无向图；

2、 混合图：既有无向边, 又有有向边的图称为混合图。 如果将有向图中的每条边都变成无向边，称为底图 (4)按G的边旁有无数量特征分为加权图、无权图(如图 8.1.4);,8.1 图的基本概念,图 8 .1. 4,(5)按G的任意两个结点间是否有边分为完全图Kn (如图 8.1.5)和不完全图(如图 8.1.6)。,8.1 图的基本概念,完全图：任意两个不同的结点都邻接的简单图称为完全图。n 个结点的无向完全图记为Kn。 图8.1.5给出了K3和K4。从图中可以看出K3有条边，K4有条边。 容易证明Kn有 条边。,8.1 图的基本概念,图 8.1. 6,图 8.1.5 K3与K4示意图,例,有向完

3、全图,无向完全图,8.1.2 图的结点的度数及其计算 我们常常需要关心图中有多少条边与某一结点 关联，这就引出了图的一个重要概念结点的度数。,8.1 图的基本概念,定义: 在有向图中, 以v为终点的边数称为结点v 的入度， 记为 ;以v为始点的边数称为结点v 的出度， 记为 。结点v的入度与出度之和称为结点v的度数，记为 d(v)或deg(v)。,定义: 在无向图中，图中结点v所关联的边数(有环时计算两次)称为结点v 的度数，记为d(v)或deg(v) 。,顶点2入度：1 出度：3 顶点4入度：1 出度：0,顶点5的度：3 顶点2的度：4,定理 8.1.1 无向图GV ,E中结点度数的总和等于

4、边数的两倍， 即 证明: 因为每条边都与两个结点关联， 所以加上一条边就使得各结点度数的和增加 2， 由此结论成立。 定义：无向图中，如果每个结点的度都是k,则称为k-度正则图。,8.1 图的基本概念,推论: 无向图G中度数为奇数的结点必为偶数个。 证明: 设V1和V2分别是G中奇数度数和偶数度数的结点集。 由定理8.1.1知 由于 是偶数之和， 必为偶数， 而2|E|也为偶数， 故 是偶数。 由此|V1|必为偶数。,8.1 图的基本概念,定理 8.1.2 在任何有向图GV ,E中， 有,图8.1.4,8.1.3 子图和图的同构 1.子图 在研究和描述图的性质时，子图的概念占有重要地位。 定义

5、8.1.5 设有图G=V , E和图 G= V, E 。 1) 若V V， E E， 则称G是G的子图。 2) 若G是G的子图，且EE，则称G是G 的真子图。,图与子图,3) 若V=V， E E，则称G是G的生成子图。 图8.1.7给出了图G以及它的真子图G1和生成子图G2。,图8.1.7 图G以及其真子图G 1和生成子图G2,8.1 图的基本概念,给定任意一个含有n个结点的图G,总可以把它补成一个 具有同样结点的完全图,方法是把那些缺少的边添上。 定义8.1.2 设GV, E是一个具有n个结点的简单 图。以V为结点集，以从完全图Kn中删去G的所有边后 得到的图（或由G中所有结点和所有能使G成

6、为完全图 的添加边组成的图）称为G的补图，记为 。 例如，零图和完全图互为补图。,8.1 图的基本概念,G相对于Kn的补图是下图中的,关于补图： 1、G与 互为补图,1. 图的同构,8.1 图的基本概念,试观察下面各图有何异同？,图 8.1.8 同构的图,图 8.1.9,8.1 图的基本概念,定义8.1.6 设有图 G=V , E和图G= V, E。 如果存在双射：VV，使得 e=(u, v) E e=(u),(v)E， 且 (u， v)与(u),(v)有相同的重数，则称G与G 同构。记作GG。 注：由同构的定义可知，不仅结点之间要具有一一对应关系，而且要求这种对应关系保持结点间的邻接关系。对

7、于有向图的同构还要求保持边的方向。,8.1 图的基本概念,【例8.1.5】考察图8.1.9中的两个图GV , E和 G= V, E 。 显然，定义：VV, (vi)v i , 可以验证是满足定义8.1.6的双射，所以GG。,8.1 图的基本概念,图 8.1.9,一般说来，证明两个图是同构的并非是轻而易举的事情，往往需要花些气力。请证明下图中两个图是同构的。,根据图的同构定义，可以给出图同构的必要条件如下： (1) 结点数目相等； (2) 边数相等； (3) 度数相同的结点数目相等。 (4)有相同重数的边数相同，等等。 但这仅仅是必要条件而不是充分条件。,下图中的(a)和(b)满足上述三个条件，

8、然而并不同构。 因为在(a)中度数为3的结点x与两个度数为1的结点邻接，而(b)中度数为3的结点y仅与一个度数为1的结点邻接。 寻找一种简单有效的方法来判定图的同构，至今仍是图论中悬而未决的重要课题。,高等学校21世纪教材,对于同构，形象地说，若图的结点可以任意挪动位置，而边是完全弹性的，只要在不拉断的条件下，这个图可以变形为另一个图，那么这两个图是同构的。故同构的两个图从外形上看可能不一样，但它们的拓扑结构是一样的。,8.2 路与图的连通性(Walks (2) d(vi,vi)=0; (3) d(vi,vj)+d(vj,vk)d(vi,vk)。,图 8.2.1,8.2.1 路与回路(Wlak

9、s and Circuits),定理 8.2.1 设G是具有n个结点的图， 如果从结点v1到另一结点v2存在一条路，则从结点v1到v2必存在一条长度不大于n1的基本路（通路）。,8.2.1 路与回路(Wlaks and Circuits),证明:假定从v1到v2存在一条路径,(v1,vi,v2)是所经的结点,如果其中有相同的结点vk,例 (v1,vi,vk,vk,v2),则删去从vk到vk的这些边,它仍是从v1到v2的路径,如此反复地进行直至(v1,vi,v2)中没有重复结点为止。此时,所得的就是通路。通路的长度比所经结点数少1,图中共n个结点,故通路长度不超过n-1。 推论 设图GV ,E

10、， |V|n， 则G中任一基本圈长度不大于n。,8.2.1 路与回路(Wlaks and Circuits),1. 无向图的连通性 定义 8.2.4 在无向图如果一个图的任何两个结点之间都有一条路，那么我们称这个图是连通的，否则是不连通的。 定义 8.2.5 图G的一个连通的子图G（称为 连通子图）若不包含在G的任何更大的连通子图中， 它就被称作G的连通分支。我们把图G的连通分支个数记作（G）。,8.2.2 图的连通性(The Connectivity of Graphs),图 8.2.3 图G与G,在图8.2.3中， G是不连通的， （G）， 而G是连通的， （G）。 任何一个图都可划分为若

11、干个连通分支。 显然， 仅当图G的连通分支数（G）时， 图G是连通的。,8.2.2 图的连通性,在图的研究中，常常需要考虑删去与增加结点、结点集、边和边集（或弧集）的问题。所谓从图G=中删去结点集S，是指作V-S以及从E中删去与S中的全部结点相联结的边而得到的子图，记作G-S；特别当S=v时，简记为G-v；所谓从图G=中删去边集（或弧集）T，是指作E-T，且T中的全部边所关联的结点仍在V中而得到的子图，记为G-T；特别当T=e时，简记作G-e。,所谓图G=增加结点集S，是指作VS以及向E中并入S中、S与V中所成的边而得到的图，记作G+S；特别当S=v 时，简记为G+v；图G=增加边集（或弧集）

12、T是指作ET所得到的图，记作G+T，这里T中全部边（或弧）的关联结点属于V。,定义: 给定连通无向图G=，SV。若(G-S)(G)，但TS有(G-T)=(G)，则称S是G的一个分离结点集。若图G的分离结点集S=v ，则称v是G的割点。 类似地可定义图G的分离边集T；若图G的分离边集T=e ，则称e是G的割边或桥。P122,对于连通的非平凡图G，称(G)=|S|S是G的分离结点集为图G的结点连通度，它表明产生不连通图而需要删去结点的最少数目。于是，对于分离图G，(G)=0；对于存在割点的连通图G，(G)=1。,类似地定义边连通度(G)= |T|T是G的分离边集，它表明产生不连通图而需要删去边的最

13、少数目。可见，对于分离图G，(G)=0；对于平凡图G，(G)=0；对于存在割边的连通图G，(G)=1；对于完全图Kn，(Kn)=n-1。,定理: 一个连通无向图G中的边e是割边 存在两个结点u和w，使得联结u与w的每条链都经过e。 下面再给出一个判定一条边是割边的充要条件。 定理: 连通无向图G中的一条边e是割边e不包含在图的任何基本圈中。,2. 有向图的连通性 定义8.2.6 在有向图中,若从结点u到v有一条路，则称u可达v。 定义8.2.7 设有有向图G， 1)若G的任意两个结点中,至少从一个结点可达另一个结点,则称图G是单向连通的;,8.2.2 图的连通性,2)如果G的任意两个结点都是相

14、互可达的,则称图G是强连通的; 3)如果略去边的方向后， G成为连通的无向图，则称图G是弱连通的。,从定义可知： 若图G是单向连通的， 则必是弱连通的；若图G是强连通的， 则必是单向连通的， 且也是弱连通的。 但反之不真。,定义 8.2.8 在有向图G=V,E中,G是G的子图,若G是强连通的(单向连通的,弱连通的),但在G中任意增加原图的一些边或一些点，所有子图便不再是强连通的(单向连通的,弱连通的),则称G是G的强分图(单向分图,弱分图)。,8.2.2 图的连通性,连通图,强连通图,非连通图 连通分图,图 8.2.5,8.2.2 图的连通性(The Connectivity of Graph

15、s),在图8.2.5中,强分图集合是: 1,2,3,e1,e2,e3,4,5,6,7,8,e7,e8 单向分图集合是: 1,2,3,4,5,e1,e2,e3,e4,e5,6,5,e6, 7,8,e7,e8 弱分图集合是: 1,2,3,4,5,6,e1,e2,e3,e4,e5,e6, 7,8,e7,e8,8.2.2 图的连通性,下面给出简单有向图的一个应用资源分配图。 在多道程序的计算机系统中，可以同时执行多个程序。实际上，程序共享计算机系统中的资源，如磁带机、磁盘设备、CPU、主存贮器和编译程序等。操作系统对这些资源负责分配给各个程序。当一个程序要求使用某种资源，它要发出请求，操作系统必须保证

16、这一请求得到满足。,对资源的请求可能发生冲突。如程序A控制着资源r1，请求资源r2；但程序B控制着资源r2，请求资源r1。这种情况称为处于死锁状态。然而冲突的请求必须解决，资源分配图有助发现和纠正死锁。 假设某一程序对一些资源的请求，在该程序运行完之前必须都得到满足。在请求的时间里，被请求的资源是不能利用的，程序控制着可利用的资源，但对不可利用的资源则必须等待。,令Pt=p1，p2，pm表示计算机系统在时刻t的程序集合，QtPt是运行的程序集合，或者说在时刻t至少分配一部分所请求的资源的程序集合。Rt=r1，r2，rn是系统在时刻t的资源集合。资源分配图Gt=是有向图，它表示了时刻t系统中资源

17、分配状态。把每个资源ri看作图中一个结点，其中i=1，2，n。表示有向边，E当且仅当程序pkQt已分配到资源ri且等待资源rj。,例如，令Rt=r1,r2,r3,r4，Qt=p1,p2,p3,p4。资源分配状态是： p1占用资源r4且请求资源r1； p2占用资源r1且请求资源r2和r3； p3占用资源r2且请求资源r3； p4占用资源r3且请求资源r1和r4。,于是，可得到资源分配图Gt=，如图8.2.7所示。 能够证明，在时刻t计算机系统处于死锁状态资源分配图Gt中包含强分图。于是，对于图8.2.7，Gt是强连通的，即处于死锁状态。,图 8.2.7,8.3 图的矩阵表示(Matrix Not

18、ation of Graph),8.3.1 邻接矩阵 (Adjacency Matrices) 8.3.2 可达性矩阵 (Reachability Matrices ),8.3.1邻接矩阵 (Adjacency Matrices),上面我们介绍了图的一种表示方法， 即用图形表示图。 它的优点是形象直观， 但是这种表示在结点与边的数目很多时是不方便的。 下面我们提供另一种用矩阵表示图的方法。 利用这种方法， 我们能把图用矩阵存储在计算机中， 利用矩阵的运算还可以了解到它的一些有关性质。,定义 8.3.1 设GV ,E是有n个结点的简单图， 则n阶方阵（aij）称为G的邻接矩阵。 其中,否则,如图

19、8.3.1所示的图G， 其邻接矩阵A为,8.3 图的矩阵表示(Matrix Notation of Graph),显然无向图的邻接矩阵必是对称的。 下面的定理说明， 在邻接矩阵A的幂A2， A3， 等矩阵中， 每个元素有特定的含义。,图8.3.1 G,8.3 图的矩阵表示(Matrix Notation of Graph),图8.3.1 图G,8.3 图的矩阵表示(Matrix Notation of Graph),定理 8.3.1 设G是具有n个结点v1, v2, ,vn 的图， 其邻接矩阵为A， 则Ak（k1， 2， ）的（i， j）项元素a(k)ij是从vi到vj的长度等于k的路的总数。

20、 证明: 施归纳于k。 当k1时， A1A， 由A的定义， 定理显然成立。 若kl时定理成立， 则当kl1时， A l+1Al A，,所以,8.3 图的矩阵表示(Matrix Notation of Graph),根据邻接矩阵定义arj是联结vr和vj的长度为1的路数目,a(l)ir是联结vi和vr的长度为l的路数目,故上式右边的每一项表示由vi经过l条边到vr,再由vr 经过1条边到vj的总长度为l+1的路的数目 。对所有r求和,即得a(l+1)ij是所有从vi到vj的长度等于l+1的路的总数,故命题对l+1成立。,8.3 图的矩阵表示(Matrix Notation of Graph),由

21、定理8.3.1可得出以下结论： 1) 如果对l1， 2， ， n-1， Al的 （i， j）项元素（ij）都为零， 那么vi和vj之间无任何路相连接， 即vi和vj不连通。 因此， vi和vj必属于G的不同的连通分支。,8.3 图的矩阵表示(Matrix Notation of Graph),2) 结点vi 到vj （ij）间的距离d（vi， vj） 是使Al（l1， 2， ， n-1 ）的（i， j）项元素不为零的最小整数l。,3) Al的（i， i）项元素a(l)ii表示开始并结束于vi长度为l的回路的数目。,8.3 图的矩阵表示(Matrix Notation of Graph),【例8

22、.3.1】图GV ,E的图形如图8.3.2， 求邻接矩阵A和A2， A3， A4， 并分析其元素的图论意义。,8.3 图的矩阵表示(Matrix Notation of Graph),图 8.3.2,解:,8.3 图的矩阵表示(Matrix Notation of Graph),1) 由A中a(1)121知， v1和v2是邻接的； 由A3中a(3)122知， v1到v2长度为3的路有两条， 从图中可看出是v1v2v1v2和v1v2v3v2。 2) 由A2的主对角线上元素知， 每个结点都有长度为的回路， 其中结点v2有两条： v2v1v2和v2v3v2， 其余结点只有一条。 3) 由于A3的主对

23、角线上元素全为零， 所以G中没有长度为的回路。,8.3 图的矩阵表示(Matrix Notation of Graph),4) 由于 所以结点v3和v4间无路， 它们属于不同的连通分支。 5) d（v1， v3）。,8.3 图的矩阵表示(Matrix Notation of Graph),8.6 树与生成树(Trees and Spanning Trees),8.6.1 无向树(Undirected Trees) 8.6.2无向图中的生成树与最小生成树(Spanning Trees and Minimal Spanning Trees ),8.6.1 无向树(Undirected Trees)

24、,树是图论中的一个重要概念。早在1847年克希霍夫就用树的理论来研究电网络， 1857年凯莱在计算有机化学中2H2n+2的同分异构物数目时也用到了树的理论。 而树在计算机科学中应用更为广泛。本节介绍树的基本知识， 其中谈到的图都假定是简单图。,定8.6.1 一个连通无圈无向图称为无向树(简称为树)。记作T。树中度数为1的结点称为树叶（或终端结点）， 度数大于的结点称为分枝点（或内点，或非终端结点）。一个无圈图称为森林。 显然若图G是森林，则G的每个连通分支是树。如图8.6.1(a)所示的是一棵树；(b)所示的是森林。,8.6 树与生成树(Trees and Spanning Trees),图

25、8.6.1 树和森林示意图,8.6 树与生成树(Trees and Spanning Trees),【例8.6.1】判断图 8.6.2中各图是否为树.,图 8.6.2,8.6 树与生成树(Trees and Spanning Trees),证：因为T是一棵n2的（n， m）树， 所以由定理8.4.1， 有,若T中的无树叶， 则T中每个顶点的度数2,则 deg(vi)2n, （2）,(1),定理8.6.1 任一树T中,至少有两片树叶(n2时)。,8.6 树与生成树(Trees and Spanning Trees),若T中只有一片树叶，则T中只有一个结点度数为1,其它结点度数2, 所以,(3),

26、(2),(3)都与(1)矛盾。所以T中至少有两片树叶。,8.6 树与生成树(Trees and Spanning Trees),定理8.6.2一个无向图（n, m）图T是树,当且仅当下列5条之一成立。(或者说,这5条的任一条都可作为树的定义。) (1)无圈且m=n-1。 (2) 连通且m=n-1。 (3)无圈,但增加任一新边,得到且仅得到一个圈。 (4)连通但删去任一边,图便不连通(n2)。 (5)每一对结点间有唯一的一条通路。(n2)。,8.6 树与生成树(Trees and Spanning Trees),【例8.6.2】T是一棵树,有两个2度结点，一个3度结点，三个 4度结点，T有几片树

27、叶？ 解： 设树T有x片树叶，则T的结点数 n=2+1+3+x T的边数 m=n-1=5+x 又由 得 2 （5+x）=22+31+43+x 所以x=9，即树T有9片树叶。,8.6 树与生成树(Trees and Spanning Trees),8.6.2无向图中的生成树与最小生成树(Spanning Trees and Minimal Spanning Trees ) 定义8.6.2 若无向(连通图)G的生成子图是一棵树，则称该树是G的生成树，记为TG。生成树TG中的边称为树枝。图G中其它边称为TG的弦。 所有这些弦的集合称为TG的补。 如图8.6.3中(b)、(c)所示的树T1、T2是(a

28、)图的生成树，而(d)所示的树T3不是(a)图的生成树。一般的，图的生成树不唯一。,图 8.6.3,考虑生成树T1，可知e1，e2，e3，e4是T1的树枝，e5，e6，e7是T1的弦，集合e5，e6，e7是T1的补。生成树有其一定的实际意义。,8.6 树与生成树(Trees and Spanning Trees),【例8.6.3】某地要兴建5个工厂，拟修筑道路连接这5处。经勘测其道路可依如图8.6.3(a)图的无向边铺设。为使这5处都有道路相通，问至少要铺几条路？ 解 这实际上是求G的生成树的边数问题。 一般情况下，设连通图G有n个结点，m条边。由树的性质知，T有n个结点，n1条树枝， mn1

29、条弦。 在图8.6.3(a)中，n5，则n1514， 所以至少要修条路才行。,8.6 树与生成树(Trees and Spanning Trees),定义8.6.3 设G=V , E是一连通的有权图，则G的生成树TG为带权生成树, TG的树枝所带权之和称为。生成树TG的权,记为C(TG ) 。G中具有最小权的生成树TG称为G的最小生成树。 求最小生成树问题是有实际意义的。 如要建造一个连接若干城市的铁路网络，已知城市vi和vj之间直达铁路的造价，设计一个总造价为最小的铁路网络，就是求最小生成树TG。 下面介绍求TG的克鲁斯克尔（Kruskal)算法。,8.6 树与生成树(Trees and S

30、panning Trees),此方法又称为“避圈法”。 其要点是， 在与已选取的边不成圈的边中选取最小者。 具体步骤如下： 1) 在G中选取最小权边， 置边数i1。 2) 当in1时， 结束。 否则， 转3)。 3) 设已选择边为 e1, e2, , ei，在G中选取不同于e1, e2, , ei 的边 ei+1, 使 e1, e2, , ei ,ei+1无圈且ei+1是满足此条件的最小权边。 4) 置i为i1， 转2)。,8.6 树与生成树(Trees and Spanning Trees),【例8.6.4】求图8.6.4(0)中有权图的最小生成树。 解: 因为 图中n8， 所以按算法要执行

31、n17次， 其过程见图8.6.4中(1)(7)。,8.6 树与生成树(Trees and Spanning Trees),图 8.6.4,8.6 树与生成树(Trees and Spanning Trees),【例8.6.5】求图8.6.5中有权图G的最小生成树。 解: 因为 图中n8，所以按算法要执行n17次。,图 8.6.5,8.6 树与生成树(Trees and Spanning Trees),【例8.6.6】图8.6.6所示的赋权图G表示七个城市a,b,c,d,e,f,g及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小,并计算出最小造价。,图8.6

32、.6,8.6 树与生成树(Trees and Spanning Trees),解:该问题相当于求图的最小生成树问题，此图的最小生成树为图8.6.6中的TG ,因此如图TG架线使各城市间能够通讯，且总造价最小，最小造价为： (),8.6 树与生成树(Trees and Spanning Trees),10.7 根树及其应用(Rooted Trees and Its Applications),10.7.1 有向树(directed tree ) 10.7.2 m叉树(m-ary tree ) 10.7.3 最优二叉树(optimal binary tree ),10.7.1 有向树(direct

33、ed tree ),图 10.7.1,10.7.1 有向树(directed tree ),定义 10.7.1 一个有向图， 若不考虑边的方向， 它是一棵树， 则这个有向图称为有向树。 一棵有向树， 如果恰有一个结点的入度为， 其余所有结点的入度都为， 则称为根树， 其中入度为的结点称为树根， 出度为的结点称为树叶， 出度不为的结点称为分枝点或内点。,如图10.7.2(a)表示一棵根树， 其中v1为树根， v1， v2， v3为分枝点， 其余结点为树叶。 习惯上我们把根树的根画在上方， 叶画在下方。 这样就可以省去根树的箭头， 如图10.7.2(b)。 在根树中， 称从树根到结点v的距离为该点

34、的层次。 这样对图10.7.2中的根树， v1的层次为， v2、 v3的层次为， 其余结点的层次均为。 我们用家族关系表示根树中各结点的关系。,10.7 根树及其应用,图 10.7.2 根树示例,10.7 根树及其应用,定义10.7.2 在根树中， 若从vi到vj可达， 则称vi是vj的祖先， vj是vi的后代； 又若vi， vj是根树中的有向边， 则称vi是vj的父亲， vj是vi的儿子； 如果两个结点是同一结点的儿子， 则称这两个结点是兄弟。 定义10.7.3 在根树中， 任一结点v及其v的所有后代和从v 出发的所有有向路中的边构成的子图称为以v为根的子树。 根树中的结点u的子树是以u的儿

35、子为根的子树。,10.7 根树及其应用,在现实的家族关系中， 兄弟之间是有大小顺序的， 为此我们又引入有序树的概念。 定义10.7.4 如果在根树中规定了每一层次上结点的次序， 这样的根树称为有序树。 我们在有序树中规定同一层次结点的次序是从左至右。,10.7 根树及其应用,10.7.2 m叉树(m-ary tree ) 在树的实际应用中， 我们经常研究完全m叉树。 定义10.7.5 在根树中， 若结点的最大出度等于m， 则称这棵树为m叉树。 如果每个结点的出度恰好等于或m， 则称这棵树为完全m叉树。 二叉树(binary tree )的每个结点v 至多有两棵子树， 分别称为v的左子树和右子树。,图 10.7.3,定理10.7.1 在完全m叉树中， 若树叶数为 t， 分枝点数为 i， 则 (m-1)it- 证明: 由假设知， 该树有 i+t 个结点， 由定理8.6.2知， 该树边数为 i+t -。 因为所有结点出度之和等于边数所以根据完全m叉树的定义知， mi i+t - 即 (m-1)it-,1