离散数学-图论基础

1、第七章 图论基础 Graphs24 九月 2022第一节 图的基本概念一个图G定义为一个三元组：G=V 非空有限集合，V中的元素称为结点 (node)或顶点(vertex)E 有限集合（可以为空），E中的元素称为边(edge) 从E到V的有序对或无序对的关联映射(associative mapping)v1v2v3(a)v1v2v3(b)v1v2v3(c)24 九月 2022图的基本概念图G=中的每条边都与图中的无序对或有序对联系若边e E 与无序对结点va, vb相联系，即(e)= va, vb（va, vb V）则称e是无向边（或边、棱）若边e E与有序对结点相联系，即(e)=（va, v

2、b V）则称e是有向边（或弧）va是e的起始结点， vb是e的终结点v1v2v3(a)v1v2v3(b)v1v2v3(c)24 九月 2022图的基本概念若va和vb与边（弧）e相联结，则称va和vb是e的端结点va和vb是邻接结点，记作：va adj vb (adjoin)也称e关联va和vb，或称va和vb关联e若va和vb不与任何边（弧）相联结，则称va和vb是非邻接结点，记作：va nadj vb关联同一个结点的两条边（弧），称为邻接边（弧）关联同一个结点及其自身的边，称为环(cycle)，环的方向没有意义v1v2v3(a)v1v2v3(b)v1v2v3(c)24 九月 2022图的基

3、本概念若将图G中的每条边（弧）都看作联结两个结点则G简记为：每条边都是弧的图，称为有向图(directed graph)（如图b）每条边都是无向边的图，称为无向图(undirected graph) （如图a） 有些边是弧，有些边是无向边的图，称为混合图（如图c）v1v2v3(a)v1v2v3(b)v1v2v3(c)24 九月 2022图的基本概念若图G中的任意两个结点之间不多于一条无向边（或不多于一条同向弧），且任何结点无环，则称G为简单图（如图c）若图G中某两个结点之间多于一条无向边（或多于一条同向弧），则称G为多重图（如图a, b） 两个结点间的多条边（同向弧）称为平行边（弧），平行边（

4、弧）的条数，称为重数v1v2v3(a)v1v2v3(b)v1v2v3(c)24 九月 2022图的基本概念在多重图的表示中，可在边（弧）上标注正整数，以表示平行边（弧）的重数把重数作为分配给边（弧）上的数，称为权(weight)将权的概念一般化，使其不一定是正整数，则得到加权图的概念：给每条边（弧）都赋予权的图，叫做加权图(weighted graph)记作G=，W是各边权之和v1v2v3(a)v1v2v3(b)v1v2v3(c)111111221124 九月 2022图的基本概念在无向图G=中，V中的每个结点都与其余的所有结点邻接，即(va)(vb)(va, vb V va, vb E)，如

5、图(a)则称该图为无向完全图(complete graph)，记作K|V|若|V|=n，则|E|= C = n(n-1)/2v1v2v3(a)v1v2v3(b)2n24 九月 2022图的基本概念在有向图G=中，V中的任意两个结点间都有方向相反的两条弧，即 (va)(vb)(va,vbV EE)，如图(a) 则称该图为有向完全图，记作K|V|若|V|=n，则|E|= P = n(n-1)v1v2v3(a)v1v2v3(b)2n24 九月 2022图的基本概念在图G=中，若有一个结点不与其他任何结点邻接则该结点称为孤立结点，如图(a)中的v4仅有孤立结点的图，称为零图，零图的 E = ，如图(b

6、)仅有一个孤立结点的图，称为平凡图(trivial graph)，如图(c) v1v2v3(a)v1v2v3(b)v1(c)v424 九月 2022问题问题1：是否存在这种情况：25个人中，由于意见不同，每个人恰好与其他5个人意见一致？问题2：是否存在这种情况：2个或以上的人群中，至少有2个人在此人群中的朋友数一样多？24 九月 2022结点的次数二、结点的次数定义：在有向图G=中，对任意结点v V以v为起始结点的弧的条数，称为出度(out-degree)（引出次数），记为d+(v)以v为终结点的弧的条数，称为入度(in-degree)（引入次数），记为d-(v)v的出度和入度的和，称为v的度

7、数(degree)（次数），记为d(v) = d+(v) + d-(v)v1v2v3(a)24 九月 2022结点的次数定义：在无向图G=中，对任意结点v V结点v的度数d(v) ，等于联结它的边数若结点v 上有环，则该结点因环而增加度数2记G的最大度数为： (G) = max d(v)| v V记G的最小度数为： (G) = min d(v)| v Vv1v2v3(a)v1v2v3(b)v424 九月 2022结点的次数在图G中的任意一条边e E，都对其联结的结点贡献度数2定理：在无向图G=中， d(v) = 2|E|通常，将度数为奇数的结点称为奇度结点 将度数为偶数的结点称为偶度结点定理：

8、在无向图G=中，奇度结点的个数为偶数个24 九月 2022结点的次数问题1：是否存在这种情况：25个人中，由于意见不同，每个人恰好与其他5个人意见一致？在建立一个图模型时，一个基本问题是决定这个图是什么 什么是结点？什么是边？在这个问题里，我们用结点表示对象人；边通常表示两个结点间的关系表示2个人意见一致。也就是说，意见一致的2个人（结点）间存在一条边。24 九月 2022结点的次数问题1：是否存在这种情况：25个人中，由于意见不同，每个人恰好与其他5个人意见一致？这样我们可以知道，如果存在题目所述情况，那么每个结点都与其他5个结点相关联。也就是说，每个结点的度为5。由定理可知：奇度结点的个数

9、为偶数个。现在是否能够得出结论了？24 九月 2022结点的次数类似问题：晚会上大家握手言欢，握过奇数次手的人数一定是偶数碳氢化合物中，氢原子个数是偶数是否有这样的多面体，它有奇数个面，每个面有奇数条棱？24 九月 2022结点的次数问题2：是否存在这种情况：两个人或以上的人群中，至少有两个人在此人群中的朋友数一样多？以人为结点，仅当二人为朋友时，在此二人之间连一边，得一“友谊图”G(V,E)， 设V=v1, v2, , vn，不妨设各结点的次数为d(v1)d(v2) d(vn)n-1。假设命题不成立，则所有人的朋友数都不一样多，则 0 d(v1)d(v2) d(vn)n-1。24 九月 20

10、22结点的次数问题2：是否存在这种情况：两个人或以上的人群中，至少有两个人在此人群中的朋友数一样多？若 0 d(v1)d(v2) d(vn) n-1，则有：由于d(v1)0 ，则有d(v2)1，d(v3)2，d(vn)n-1；又因为d(vn) n-1，所以： d(vn)=n-1因为d(vn)=n-1，则每个结点皆与vn相邻，则d(v1)1。于是有：d(v2)2，d(v3)3，d(vn)n，矛盾。故假设不成立，即d(v1)d(v2) d(vn)中至少有一个等号成立，命题成立。24 九月 2022结点的次数定义：在无向图G=中，若每个结点的度数都是k，即(v)( v V d(v) = k)，则称G

11、为k度正则图(regular graph)v1v2v6v33度正则图v4v5v7v8v9v103度正则图v1v5v6v2v3v424 九月 2022子图三、子图定义：给定无向图G1=， G2=若V2 V1，E2 E1，则称G2是G1的子图(subgraph)，记作G2 G1若V2 V1，E2 E1，且E2 E1，则称G2是G1的真子图，记作G2 G1若V2 = V1，E2 E1，则称G2是G1的生成子图(spanning subgraph)，记作G2 G1V2 = V124 九月 2022子图例如：v2v1(a)v3v4v5(a)的真子图v2v3v4v5(a)的生成子图v2v3v4v5v124

12、 九月 2022子图定义：对于图G=，G1=G，G2= G1和 G2都是G的生成子图，称为平凡生成子图定义：设G2=是G1=的子图对任意结点u, v V2，若有u, v E1，则有u, vE2，则G2由V2唯一地确定，则称G2是V2的诱导子图记作GV2，或G2=若G2中无孤立结点，且由E2唯一地确定，则称G2是E2的诱导子图，记作GE2，或G2=24 九月 2022子图例如：v2v1G=v3v4v5G=V或E的诱导子图v2v3v4v524 九月 2022补图定义：设G1=和G2=是G=的子图，若 E2 = E - E1，且G2是E2的诱导子图，即G2= 则称G2是相对于G的G1的补图24 九月

13、 2022补图图G1和G2互为相对于G补图G1v2v1v3v4v5G2v2v3v4v5Gv2v1v3v4v524 九月 2022补图定义：给定图G1= ，若存在图G2=且 E1 E2 = ，及图是完全图则称G2是相对于完全图的G1的补图，记作G2 = G124 九月 2022补图 G2 = G1v2v1G1v3v4v5v2v1K5v3v4v5G2v2v3v4v5v124 九月 2022图的同构四、图的同构定义：给定图G1=， G2=若存在双射函数f : V1 V2 ，使得对于任意u, v V1有u, v E1 f(u), f(v) E2 （或 E1 E2）则称G1与G2同构(isomorphi

14、c)，记作 G1 G224 九月 2022图的同构例7.1.1 证明下面两个图G1=， G2=同构证明：V1=v1, v2, v3, v4, V2=a, b, c, d构造双射函数f : V1 V2 ，f(v1)=a ，f(v2)=bf(v3)=c ，f(v4)=d可知，边v1, v2, v2, v3, v3, v4, v4, v1被分别映射成a, b, b, c, c, d, d, a，故G1 G2v2v1G1v3v4badcG224 九月 2022图的同构例7.1.2 证明下面两个有向图是同构的。G1eabcd证明：如图所示，G1=，G2=，结点编号如图所示。构造函数f: V1V2 ，使得

15、f(a)=1, f(b)=3, f(c)=4, f(d)=5, f(e)=2 则, , , , , , , 被分别映射成, , , , , ,故f是双射函数，所以G1与G2同构G13124524 九月 2022图的同构可以给出图的同构的必要条件：结点数相等边数相等度数相等的结点数相等要注意的是，这不是充分条件24 九月 2022图的同构例7.1.3 证明下面两个无向图是不同构的G1v1v2v3v4v5v6v7v8G2abcdefgh v1是3度结点，故f(v1)只能是c或d或g或h。 若f(v1)=c，由于v2、v4和v5与v1邻接，因此f(v2)、f(v4)和f(v5)应当分别为与c邻接的b

16、、d和g。 但是，v2、v4和v5中，只有一个3度结点，而b、d、g中却有2个3度结点，故f(v1)c。 同理可说明， f(v1)也不可能是d、g和h。 因此这样的f是不存在的。 因此G1和G2是不同构的。24 九月 2022第二节 路(链)与回路(圈)一、路(链)与回路(圈)定义：给定图G=，令v0,v1,vmV，e1,e2,emE称交替序列v0 e1 v1 e2 v2 em vm为连接v0到vm的链（路）称v0和vm为链（路）的始结点和终结点链的长度为边（弧）的数目m若v0=vm，该链（路）称为圈（回路, circuit ）24 九月 2022链和圈在链中：若任意ei只出现一次，则称该链（

17、路）为简单链（路）若任意vi只出现一次，则称该链（路）为基本链（路）基本链必定是简单链在圈中：若任意ei只出现一次，则称该圈（回路）为简单圈（回路）若任意vi只出现一次，则称该圈（回路）为基本圈（回路）24 九月 2022链和圈例7.2.1 下图中：v3v1v4v5v2e1e2e3e4e5e6e7e8P1=(v1 e1 v2 e7 v5)也可以表示为：P1=(e1 e7)是一个基本链，也是一个简单链P2=(v2 e2 v3 e3 v3 e4 v1 e1 v2)也可以表示为：P2=(e2 e3 e4 e1 )是一个简单圈，但不是基本圈P3=(v4 e6 v2 e7 v5 e8 v4 e6 v2

18、e2 v3) 是一个链P4=(v2 e7 v5 e8 v4 e6 v2) 是一个基本圈，也是一个简单圈24 九月 2022链和圈链和圈可以只用边的序列表示上例中： (v2e2v3e3v3e4v1e1v2)也可表示为 (e2e3e4e1)(v4e6v2e7v5e8v4e6v2e2v3)也可表示为 (e6e7e8e6e2)对于简单图来说，链和圈可以仅用结点序列表示v3v1v4v5v2e1e2e4e5e6e3e8图中：(v2e2v3e4v1e1v2e3v5e8v4)可表示为 (e2e4e1e3e8)也可表示为 (v2v3v1v2v5v4)24 九月 2022链和圈定理：在一个图中，若从结点vi到结点

19、vj存在一条链（路），则必有一条从vi到vj的基本链（路）证明：1) 若从vi到vj给定的链本身就是基本链，定理成立2) 若从vi到vj给定的链不是基本链，则至少含有一个结点vk，它在该链中至少出现两次以上。 也就是说，经过vk有一个圈 ，于是可以从原有链中去除中所有出现的边（弧）。对于原链中所含的所有圈都做此处理，最终将得到一条基本链（路）24 九月 2022链和圈问题：在一个图中，若从结点vi到结点vj存在一个圈， 则必有一个从vi到vj的基本圈吗？例7.2.2 若u和v是一个圈上的两个结点，u和v一定是某个基本圈上的结点吗？(习题7-16)答：不一定vaudcb本图中，u和v在一个圈上，

20、但是却不在一个基本圈上24 九月 2022链和圈定理：在一个具有n个结点的图中，任何基本链（路）的长度不大于n-1任何基本圈（回路）的长度不大于n证明：1) 根据基本链的定义可知，出现在基本链中的结点都是不同的。因此在长度为m的基本链中，不同的结点数为m+1又因为图中仅有n个结点，故 m+1 n，即 m n-12)根据基本圈的定义可知，长度为k的基本圈中，不同的结点数为k，图中共有n个结点，所以 k n24 九月 2022可达二、连通图定义：在一个图中，若从vi到vj存在任何一条链则称从vi到vj是可达的(accessible)，简称vi可达vj规定：每个结点vi到自身都是可达的24 九月 2

21、022连通无向图（一）连通无向图对于无向图G=而言，可证明“可达性”是一个_关系。它对V给出一个划分，每个块中的元素形成一个诱导子图。两个结点间是可达的，当且仅当它们属于同一个子图称这样的子图为G的连通分图，G的连通分图的个数记为(G)若G中只有一个连通分图，则称G是连通图(即任意两结点可达)否则称G为非连通图，或分离图等价24 九月 2022连通无向图定义：在无向图G=中若任意两个结点可达，则称G是连通的(connected) ，称G为连通无向图；否则称G是非连通的，称G为非连通图或分离图。若G的子图G是连通的，且不存在包含G的更大的G的子图G是连通的，则称G是G的连通分图(connecte

22、d components)，简称分图。G中连通分图的个数记为(G) 。24 九月 2022连通无向图例7.2.3v3v1v4v5v2v3v1v4v5v2G1G2G1是连通图， (G1)=1G2是非连通图， (G2)=224 九月 2022连通无向图定义：从图G=中删除结点集S，是指V-SE-与S中结点相连结的边而得到的子图，记做G-SG-v3v3v1v4v5v2Gv3v1v4v5v2v3v1v4v5v224 九月 2022连通无向图定义：从图G=中删除结点集S，是指V-SE-与S中结点相连结的边而得到的子图，记做G-SG-v3v1v4v5v2G24 九月 2022连通无向图定义：从图G=中删除

23、边集T，是指V不变E-T而得到的子图，记做G-TG-e1, e3 , e4v3v1v4v5v2Ge1e2e3e4e5e6e7v3v1v4v5v224 九月 2022连通无向图定义：从图G=中删除边集T，是指V不变E-T而得到的子图，记做G-TG-e1, e3 , e4v3v1v4v5v2Ge2e5e6e724 九月 2022连通无向图定义：给定连通无向图G=，S V若 (G-S) (G)=1且对任意 T S，(G-T) = (G)则称S是G的一个分离结点集(cut-set of nodes)若S中仅含有一个元素v，则称v是G的割点(cut-node)24 九月 2022连通无向图例7.2.4G

24、如下图所示，S=v1, v3v2v1v5v6v4Gv3v2v1v5v6v4G-Sv3v2v5v6v4G-S(G)=1， (G-S) =2(G-S) (G) 24 九月 2022连通无向图例7.2.4G如下图所示，S=v1, v3v2v1v5v6v4Gv3(G)=1， (G-S) =2(G-S) (G) (G-v1)=1v2v5v6v4G-v1v324 九月 2022连通无向图例7.2.4G如下图所示，S=v1, v3v2v1v5v6v4Gv3(G)=1， (G-S) =2(G-S) (G) (G-v1)=1v2v1v5v6v4G-v3(G-v3)=124 九月 2022连通无向图例7.2.4G

25、如下图所示，S=v1, v3v2v1v5v6v4Gv3v2v5v6v4G-S(G)=1， (G-S) =2(G-S) (G) (G-v1)=1(G-v3)=1S是G的分离结点集24 九月 2022连通无向图例7.2.5G如下图所示，S=v2v1v4v5v3Gv2(G)=1， (G-S) =2(G-S) (G) v1v4v5v3G-Sv2是G的割点不存在其他的G的割点24 九月 2022连通无向图定义：给定连通无向图G=，T E若 (G-T) (G) =1且对任意 F T，(G-F) = (G)则称T是G的一个分离边集(cut-set of edges)若T中仅含有一个元素e，则称e是G的割边(

26、cut-edge)，或桥24 九月 2022连通无向图例7.2.6G如下图所示，T=e1, e2(G)=1， (G-T) =2(G-T) (G) v1v3v4Gv2e1e4e2e3v1v3v4G-Tv2e4e324 九月 2022连通无向图例7.2.6G如下图所示，T=e1, e2(G)=1， (G-T) =2(G-T) (G) v1v3v4Gv2e1e4e2e3v1v3v4G-e1v2e4e2e3(G-e1)=124 九月 2022连通无向图例7.2.6G如下图所示，T=e1, e2(G)=1， (G-T) =2(G-T) (G) v1v3v4Gv2e1e4e2e3(G-e1)=1(G-e2

27、)=1v1v3v4G-e2v2e1e4e324 九月 2022连通无向图例7.2.6G如下图所示，T=e1, e2(G)=1， (G-T) =2(G-T) (G) v1v3v4Gv2e1e4e2e3v1v3v4G-Tv2e4e3(G-e1)=1(G-e2)=1T是G的分离边集24 九月 2022连通无向图例7.2.7G如下图所示，T=e1(G)=1， (G-T) =2(G-T) (G) v1v3v4Gv2e1e2e3v1v3v4G-Tv2e2e3e1是G的割边e2和e3都是G的割边24 九月 2022连通无向图定义：对连通的非平凡图G=，称 (G) = min |S| | S是G的分离结点集为

28、G的结点连通度(node-connectivity)它表明产生分离图需要删去结点的最少数目对分离图G而言， (G)=0对存在割点的连通图G而言， (G)=1S V24 九月 2022连通无向图例7.2.8求G1和G2的结点连通度v2v1v5v6v4G1v3 (G1)=2 (G2)=1v1v4v5v3G2v224 九月 2022连通无向图定义：对连通的非平凡图G=，称 (G) = min |T| | T是G的分离边集为G的边连通度(edge-connectivity)它表明产生分离图需要删去边的最少数目对分离图G而言， (G)=0对存在割边的连通图G而言， (G)=1对无向完全图Kn， (Kn)

29、 = ?T En-124 九月 2022连通无向图例7.2.9求G1和G2的边连通度 (G1)=2 (G2)=1v1v3v4G1v2e1e4e2e3v1v3v4G2v2e1e2e324 九月 2022连通无向图定理：对于任何一个无向图G，有 (G) (G) (G)证明：1) 若G是分离图，则 (G) = (G) = 0， 而 (G) 02) 若G是连通图，先证明 (G) (G)若G是平凡图，则 (G) = 0 = (G)若G不是平凡图，则当删去所有联结一个具有最小度的结点的边（除了环）后，便产生了一个分离图，因此 (G) (G)再证明 (G) (G) 若 (G)1，则G存在一个割边， 显然 (

30、G) = (G) = 1v3v1v4v5v2v1v1v3v4Gv2e1e2e3v1v3v4G e1v2e2e3v1v3v4Gv2e1e2e3v1v3v4G e1v2e2e3v3v4G v1v2e324 九月 2022连通无向图若 (G) 2，则删去某 (G)条边后，G就成为分离图若只删除 (G)-1条边，则仍得到连通图且存在一割边e=u, v对于 (G)-1条边中的每一条边，选取一个不同于u和v的结点，把这些结点删去，将必须至少删去 (G)-1条边若这样会产生分离图，则 (G) (G) -1 (G)若这样产生的仍是连通图且e是割边，再删除结点u或v必将产生分离图，因此 (G) (G)v1v3v

31、4Gv2e1e4e2e3v1v3v4G v2e2e3v1v4G v3综上所述，有 (G) (G) (G)24 九月 2022连通无向图定理：一个连通无向图G中的结点v是割点，充要条件是存在两个结点u和w，使得联结u和w的每条链都经过v证明：1) 充分性：若G中联结u和w的每条链都经过v，删去v，则在子图G-v中， u和w必定不可达，故v是G的割点2) 必要性：若v是G的割点，删去v，则子图G-v中至少有两个连通分图G1=和G2 = ，任取两个结点u V1，w V2 ，u和w不可达。故G中联结u和w的每条链必经过v24 九月 2022连通无向图同理可以证明：定理：一个连通无向图G中的边e是割边，

32、充要条件是存在两个结点u和w，使得联结u和w的每条链都经过e定理：一个连通无向图G中的边e是割边，充要条件是e不包含在G的任何基本圈中证明：教材P172 （定理7.8)24 九月 2022乌拉姆猜想（1929）左右两张相片，捂住左边相片的一部分，也捂住右边相片的相应部分，例如都捂住左眼，能看到的相片的大部分形象一致；再分别捂住左右相片的另一个对应部分，例如右耳，结果能看到的相片的大部分仍然一致。如此轮番地观察各次对应的暴露部分，都会看到相同的形象，那么谁都会相信这两张照片是同一个人或孪生兄弟的留影。数学描述：有图G1=V1, E1和G2=V2, E2 ，V1=v1, v2, , vn，V2=u

33、1, u2, , un（n3）。如果G1-vi G2-ui，i=1,2,n，则G1G224 九月 2022连通有向图（二）连通有向图对于有向图G=而言，结点间的可达性不再是等价关系，它仅仅是自反的和可传递的，一般不是对称的定义：对于给定的有向图G，要略去G中每条边的方向， 便得到一个无向图G，称G是G的基础图24 九月 2022连通有向图定义：在简单有向图G中，若任何两个结点间都是可达的，则称G是强连通的若任何两个结点间，至少是从一个结点可达另一个结点，则称G是单向连通的若G的基础图是连通的，则称G是弱连通的24 九月 2022连通有向图例7.2.10 判断G1、G2和G3是强连通？单向连通？

34、弱连通？G1是强连通的v1v3v4G1v2v1v3v4G2v2v1v3v4G3v2G2是单向连通的G3是弱连通的24 九月 2022连通有向图由定义可知：若G是强连通的，则它必定是单向连通的反之未必真若G是单向连通的，则它必是弱连通的反之未必真24 九月 2022连通有向图定理：有向图G是强连通的，当且仅当G中有一回路，它至少通过每个结点一次证明：1) 充分性：若G中存在一条回路，它至少通过每个结点一回，则G中任何两个结点都是互相可达的，所以G是强连通的。2) 必要性：若G是强连通的，则G中任何两个结点都是互相可达的，因此可以做出一条回路经过G中所有结点，否则，必有某结点v不在该回路上，v与回

35、路上的各结点不可能都互相可达。与G是强连通的矛盾24 九月 2022连通有向图定义：在简单有向图G中具有强连通性质的极大子图，称为强分图具有单向连通性质的极大子图，称为单向分图具有弱连通性质的极大子图，称为弱分图24 九月 2022连通有向图例7.2.11求G的强分图、单向分图和弱分图v3v2v1Gv4v5v6v3v2v1v4v5v6G的强分图有：定理：简单有向图G中的任意一个结点，恰位于一个强分图中24 九月 2022连通有向图定理：简单有向图G中的任意一个结点，恰位于一个强分图中证明：由强分图的定义可知，G中每个结点位于一个强分图中假设G中存在结点v位于两个强分图G1和G2中则由强分图的定

36、义可知， G1中的每个结点与v互相可达， G2中的每个结点也与v互相可达故G1中的每个结点与G2中的每个结点通过v，能够互相可达，这与G1和G2是两个强分图矛盾因此G中每个结点只能位于一个强分图中24 九月 2022连通有向图例7.2.11求G的强分图、单向分图和弱分图G的单向分图有：v3v2v1Gv4v5v6v3v2v1v4v5v5v6定理：简单有向图G中的每个结点和每条弧, 至少位于一个单向分图中24 九月 2022连通有向图例7.2.11求G的强分图、单向分图和弱分图G的弱分图有：v3v2v1Gv4v5v6v3v2v1v4v5v6定理：简单有向图G中的每个结点和每条弧 恰位于一个弱分图中

37、24 九月 2022结点间的距离三、结点间的距离定义：在图G中，若结点u可达结点v，它们之间可能存在不止一条链（路）。在所有链中，最短链的长度称为结点u和v之间的距离（或短程线、测地线）。记做：d24 九月 2022结点间的距离距离满足下面性质：d 0d=0d+d d若u不可达v，则 d = +即使u和v互相可达，d未必等于d 24 九月 2022有向图在计算机中的应用四、有向图在计算机中的应用这里给出一个简单有向图在计算机中的应用 利用资源分配图来纠正和发现死锁24 九月 2022有向图在计算机中的应用在多道程序的计算机系统中，同一时间内有多个程序需要同时执行。每个程序都共享计算机资源：如C

38、PU、内存、外存、输入设备、编译系统等，操作系统将对这些资源分配给各个程序。当一个程序需要使用某种资源的时候，要向操作系统发出请求，操作系统必须保证这个请求得到满足，才能运行该程序24 九月 2022有向图在计算机中的应用对资源的请求可能发生冲突，发生死锁。例如：程序P1占有资源r1，请求资源r2程序P2占有资源r2，请求资源r1有冲突的请求必须要解决，可以利用有向图来模拟对资源的请求，从而帮助发现和纠正“死锁”状态24 九月 2022有向图在计算机中的应用令Pt=P1, P2, P3, P4是t时刻运行的程序集合 Rt=r1, r2, r3, r4是t时刻所需要的的资源集合P1占有资源r4，

39、请求资源r1P2占有资源r1，请求资源r2和r3P3占有资源r2，请求资源r3P4占有资源r3，请求资源r1和r4可得到资源分配图G如图所示r4r3r2r1P1P3P2P2P4P4可证：t时刻系统处于死锁状态G中包含多于一个结点的强分图24 九月 2022有向图在计算机中的应用t时刻系统处于死锁状态G中包含多于一个结点的强分图解决办法： 使G中的每个强分图中都是单个结点r4r3r2r1P1P3P2P2P4P4r4r3r2r1P1P3P2P224 九月 20223x+1猜想（卡拉兹）20世纪30年代，汉堡大学的卡拉兹（Callatz）提出一个猜想：x0是一个自然数，若x0是偶数，则取x1= x0

40、/2，若x0是奇数，则取x1=(3x0+1)/2。将x1应用上述规则得到x2， 如此进行下去，则到达某一步，xk=1。东京大学的N.永内达（Nabuo Yoneda）用计算机检验了所有不超过2401.21012的自然数，结果都符合卡拉兹的猜想。24 九月 20223x+1猜想（卡拉兹）如果把一批自然数放在最高层，用3x+1问题的规则算出第二层的值，继而算出第三层的值。图中的结点是自然数，当数1算出数2时，则在图上画上有向边，得到的有向图称为卡拉兹有向图，如图所示。3x+1猜想中，卡拉兹图的最底层结点是1。24 九月 2022第三节 图的矩阵表示一、图的矩阵表示定义：给定简单图G=，V=v1,v

41、2,vnV中的结点按照下标由小到大编序（编序与矩阵形式有密切关系），则n阶方阵AG=(aij)称为图G的邻接矩阵(adjacency matrix)。其中：aij=i, j = 1, 2, , n1vi adj vj0vi nadj vj24 九月 2022邻接矩阵例7.3.1 图G=如图所示v4v5v3v2v10 1 1 1 11 0 1 0 01 1 0 1 01 0 1 0 11 0 0 1 0AG= G的邻接矩阵为：0 1 0 0 11 0 1 0 10 1 0 1 10 0 1 0 11 1 1 1 0AG= G的邻接矩阵变为：v3v4v2v1v5若G中结点编序如下图所示24 九月

42、2022邻接矩阵例7.3.2 图G=如图所示0 1 0 1 0 0 1 01 0 0 1 0 1 0 0AG= G的邻接矩阵为：v1v3v4v2若G中结点编序如下图所示v4v3v1v20 1 0 0 0 0 1 01 0 0 1 1 1 0 0AG= G的邻接矩阵变为：24 九月 2022邻接矩阵对于仅仅结点编序不同的图，是同构的它们的邻接矩阵也是相似的G1 G2 存在置换矩阵P，使得AG2 = P-1 AG1 P对于由结点编序不同引起的邻接矩阵的不同将被忽略任取图的任意一个邻接矩阵作为该图的矩阵表示24 九月 2022邻接矩阵图G的邻接矩阵AG可以展示图G的一些性质：若邻接矩阵AG的元素全是

43、零，则G是若邻接矩阵AG的元素主对角线上全是0，其他元素全是1，则G是无向图G的邻接矩阵AG是在简单有向图的邻接矩阵中，第i行元素是由结点vi出发的弧所确定的，故第i行元素为1的数目，等于vi的 ，即d+(vi)= aik第j列元素是由到达结点vj的弧所确定的，故第j列元素为1的数目，等于vj的 ，即d-(vj)= akjnk=1nk=1零图连通的简单完全图对称矩阵出度入度24 九月 2022邻接矩阵定理：设A为简单图G的邻接矩阵，则An中的i行j列的元素aijn等于G中联结vi和vj的长度为n的链（路）的数目证明：1) 当n=1时， An= A1=A，定理成立2) 设n=k时定理成立，即ai

44、jk为G中联结vi和vj的长度为k的链的数目3) 当n=k+1时， An= Ak+1= AkA，即aijk+1= airk arj 根据假设可知， airk为G中联结vi和vr的长度为k的链的数目， arj为G中联结vr和vj的长度为1的链的数目，因此aijk+1为G中联结vi和vj的长度为k+1的链的数目24 九月 2022邻接矩阵例7.3.3 图G=如图所示，求A, A2, A3, A40 1 0 1 0 0 1 01 0 0 1 0 1 0 0A= v1v3v4v20 1 1 0 1 0 0 10 2 0 1 0 0 1 0A2= 1 0 1 1 0 2 0 10 1 2 0 1 0 0

45、 1A3= 1 2 0 2 0 1 2 02 0 1 2 0 2 0 1A4= 24 九月 2022邻接矩阵由上面的定理可知：若要判断图G中结点vi到vj是否可达，可以利用G的邻接矩阵A，计算A, A2, A3, , An, 若发现某个Ar（r是正整数）中aijr 1，则表明vi到vj可达。由上一节的定理可知：对于含有n个结点的图G，任何基本链（路）的长度不大于 ，任何基本圈（回路）的长度不大于因此，仅考虑 aijr （1 r n）即可n-1n24 九月 2022邻接矩阵因此，只要计算Bn= (bij) =A+A2+A3+An Bn 中元素bij 表示vi到vj的长度小于等于n的不同路径的总数

46、bij 0时， vi可达vj；若i=j，则说明存在经过vi的回路bij 0时， vi不可达vj；若i=j，则说明不存在经过vi的回路24 九月 2022邻接矩阵例7.3.4 图G=如图所示，求Bnv1v3v4v2Bn= A + A2 + A3 + A40 1 1 0 1 0 0 10 2 0 1 0 0 1 0+ 1 0 1 1 0 2 0 10 1 2 0 1 0 0 1+ 1 2 0 2 0 1 2 02 0 1 2 0 2 0 1+ 0 1 0 1 0 0 1 01 0 0 1 0 1 0 0= 2 4 2 4 1 3 3 23 3 3 4 1 3 1 2= 24 九月 2022邻接矩阵

47、问题：如何判断某无向图G是否为连通图？求出Bn= (bij) =A+A2+A3+An若有某个bij 为0(ij) ，则说明结点vi和vj处于不同的连通分图中，图G为分离图；否则G为连通图（即非主对角线上元素都不为0）。思考： 主对角线上元素bii 表示什么？24 九月 2022可达矩阵若关心的只是结点间的可达性或结点间是否有链存在至于存在多少条链以及长度为多少无关紧要则可以使用可达矩阵P=(pij)来表示结点间的可达性：pij=1,vi 可达 vj0,vi 不可达 vj24 九月 2022可达矩阵可达矩阵P=(pij)的计算之一：通过Bn 可令Bn= (bij) =A+A2+A3+An再将Bn中非零元素改为1，零元素不变，即可得到P pij=1, bij 0 0, bij 0注意：可达矩阵中，主对角线元素aii只表现了是否存在经过结点vi的圈，并不描述结点到自身的可达性。24 九月 2022可达矩阵例7.3.5 图G=如图所示，求可达矩阵Pv1v3v4v2Bn= A + A2 + A3 + A42 4 2 4 1 3 3 23 3 3 4 1 3 1 2= 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1P = 由P可知：G中任意两个结点彼此可达任意结点处都有圈存在G是强连通图24 九月 2022可达矩阵如何判定有向图G是否为强连通图？强连通图G的可达