第八章图论原理

第八章图论原理第一页，共七十三页，编辑于2023年，星期五图论图论是用图的方法研究客观世界的一门科学.用“结点”表示事物,用“边”表示事物之间联系,而由结点与边所构成的图表示所研究的客观对象.图论研究图的逻辑结构与性质，是研究图的抽象性质的一种数学.第二页，共七十三页，编辑于2023年，星期五图论图论在语言学、逻辑学、物理学、化学、电气工程、计算机网络、计算机科学及数学的其他分支中有广泛应用.在计算机科学中，图论在形式语言、数据结构、分布式系统、操作系统及数据库研究中均有很重要的应用.本篇结构第八章介绍图论一般原理第九章介绍一些常用的图如平面图、两步图以及树等第三页，共七十三页，编辑于2023年，星期五第八章图论原理本章主要介绍图论的基本原理，包括图论中的基本概念、基本方法以及图论的矩阵计算等内容.第四页，共七十三页，编辑于2023年，星期五8.1.1图起源：历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论着中，他所考虑的原始问题有很强的实际背景。

LeonhardEuler，(1707—1783)，瑞士数学家、力学家、天文学家、物理学家，图论的创始人，变分法的奠基人，复变函数论的先驱者，理论流体力学的创始人。第五页，共七十三页，编辑于2023年，星期五8.1.1图著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来，如下图所示，A、B、C，D表示陆地。问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，再回到起点。第六页，共七十三页，编辑于2023年，星期五8.1.1图欧拉在1736年解决了这个问题，他用抽象分析法将这个问题化为第一个图论问题：即把每一块陆地用一个点来代替，将每一座桥用联接相应的两个点的一条线来代替，从而相当于得到一个「图」。欧拉证明了这个问题没有解，并且推广了这个问题，给出了对於一个给定的图可以某种方式走遍的判定法则。这项工作使欧拉成为图论〔及拓扑学〕的创始人。第七页，共七十三页，编辑于2023年，星期五8.1.2图的基本概念定义8.1

图G是由非空结点集合V={v1,v2,…,vn}以及边集合E={l1,l2,…,lm}所组成,其中每条边可用一个节点对表示,亦即li=(vi1,vi2),i=1,2,…,m 这样一个图G可用G=<V,E>表示第八页，共七十三页，编辑于2023年，星期五8.1.2图的基本概念例8.1有4个城市:v1,v2,v3,v4,其中v1与v2间;v1与v4间;v2与v3间有直达长话线路相连,将此试试用图的方式表示解: 图中的结点集为:V={v1,v2,v3,v4} 边集为E={l1,l2,l3} l1={v1,v2},l2={v1,v4},l3={v2,v3},-------无序结点对 这个图可以用G=<V,E>表示

第九页，共七十三页，编辑于2023年，星期五8.1.2图的基本概念例8.2有4个程序p1,p2,p3,p4,它们间有一些调用关系：p1调用p2；p2能调用p3；p1能调用p4,试将此事实用图的方式表示.解： 图中的结点集为:V={p1,p2,p3,p4} 边集为E={c1,c2,c3} c1={p1,p2},c2={p2,p3},c3={p1,p4},-----有序结点对 这个图可以用G=<V,E>表示第十页，共七十三页，编辑于2023年，星期五8.1.2图的基本概念一般，用带有箭头的边表示有序结点对，而用不带箭头的边表示无序结点对.第十一页，共七十三页，编辑于2023年，星期五8.1.2图的基本概念有序结点对所对应的边称为有向边，无序结点对所对应的边称为无向边有向图：图中的所有边均为有向边无向图：图中的所有边均为无向边第十二页，共七十三页，编辑于2023年，星期五8.1.2图的基本概念有向边lk={vi,vj}中,vi称为lk的起点,vj称为lk的终点不管lk是有向还是无向,均称lk与vi和vj相关联,而vi和vj称为邻接的.若干条边关联于同一个结点,则这些边称为邻接的.第十三页，共七十三页，编辑于2023年，星期五8.1.2图的基本概念一条边若与两个相同的结点相关联,则称为环,即lk={vi,vi}不与任何结点相邻的结点称为孤立点第十四页，共七十三页，编辑于2023年，星期五8.1.2图的基本概念图G=<V,E>与G’=<V’,E’>间如果有V’⊆V,E⊆E’,则称G’是G的子图.如果有V’⊂V,E⊂E’,则称G’是G的真子图.如果有V’=V,E⊆E’,则称G’是G的生成子图.第十五页，共七十三页，编辑于2023年，星期五8.1.2图的基本概念(n,m)图:一个具有n个结点、m条边所组成的图零图:由一些孤立点组成的图,即(n,0)图平凡图:由一个孤立结点组成的图,即(1,0)图完全图:一个(n,m)图G如果其n个结点(n≥2)中的每一个均与其中n-1个结点邻接,可记为Kn.m=n(n-1)/2第十六页，共七十三页，编辑于2023年，星期五8.1.2图的基本概念第十七页，共七十三页，编辑于2023年，星期五8.1.2图的基本概念补图： 设有一图G=(V,E),对图G’=(V,E’),如果有 是完全图且E∩E’=Ø 则称G’是G的补图.一个图与其补图是互补的一个图的补图的补图还是自己第十八页，共七十三页，编辑于2023年，星期五8.1.3图的同构定义8.2 设有图G=<V,E>与G’=<V’,E’>,如果它们的结点间存在一一对应关系,而且这种对应关系也反映在表示边的结点对中(如果是有向边,则对应的结点对还保持相同的顺序),则称此两图是同构的.第十九页，共七十三页，编辑于2023年，星期五8.1.3图的同构(a)(b)同构，(c)(d)同构第二十页，共七十三页，编辑于2023年，星期五8.1.4图中结点的次数定义8.3在有向图中,以结点v为起点的边的条数称为v的引出次数,记以deg(v);以v为终点的边的条数叫v的引入次数,记以deg(v);v的引入次数与引出次数之和称为v的次数或全次数,记为deg(v).在无向图中,结点v的次数或全次数是与v相关联的边的条数,也用deg(v)表示.任一图的所有结点的次数之和必为偶数,且必为图中边数的两倍,因为每条边必与两个结点相关联.第二十一页，共七十三页，编辑于2023年，星期五8.1.4图中结点的次数题(8.1)设V={u,v,w,x,y},画出图G=<V,E>： 1)E={(u,v),(u,x),(v,w),(v,y)(x,y)} 2)E={(u,v),(v,w),(w,x),(w,y)(x,y)} 再求每个结点的次数.解： 1) 2)

1)中结点：deg(u)=2,deg(v)=3,deg(w)=1,deg(x)=2,deg(y)=2. 2)中结点：deg(u)=1,deg(v)=2,deg(w)=3,deg(x)=2,deg(y)=2.uwvxyuwvxy第二十二页，共七十三页，编辑于2023年，星期五8.1.4图中结点的次数定理8.1图G=<V,E>是一个(n,m)图,其中V={v1,v2,…,vn},此时有d次正则图：所有结点均有相同次数d的图.第二十三页，共七十三页，编辑于2023年，星期五8.1.4图中结点的次数例：任何图G中必有偶数个() A.引入次数为奇数的结点 B.引出次数为奇数的结点 C.次数为偶数的结点 D.次数为奇数的结点解： 引入次数与引出次数均指有向图,这里是所有图 因为图中结点次数的总和为偶数,因此次数为奇数的结点数目为偶数.所以选D.第二十四页，共七十三页，编辑于2023年，星期五8.1.5多重图与带权图多重图：一个结点对可对应若干条边,这种边称为多重边方向相反的两条边可看成是由不同的结点对对应的.简单图：不包含多重边的图第二十五页，共七十三页，编辑于2023年，星期五8.1.5多重图与带权图例：三个点可构成多少个不同构的简单无向图？解： 1)有点无边 2)有一条边 3)有两条边 4)有三条边 所以一共有4个.第二十六页，共七十三页，编辑于2023年，星期五8.1.4图中结点的次数有权图：在一个图中的旁侧可以附加一些数字来刻画此边的某些数量特征(如两地距离,车流量限制),称为边的权,此边叫有权边,具有有权边的图称为有权图.无权图：不具有有权边的图.第二十七页，共七十三页，编辑于2023年，星期五8.2.1通路与回路设有向图G=<V,E>,考虑G中边的序列(vi1,vi2),(vi2,vi3),…,(vik-1,vik),可简写为(vi1,vi2,vi3,…,vik)此序列中可以允许多次出现相同的结点与边,在此序列中除vi1和vik外,中间每个结点均与其前、后结点相连接,这种边的序列称为图的通路,而vi1和vik分别叫通路的起始结点与终止结点,通路中边的数目称为通路的长度.有向图中各边全不同的通路称为简单通路,各点全不同的称为基本通路.一条基本通路一定是简单通路,但一条简单通路则不一定是基本通路.第二十八页，共七十三页，编辑于2023年，星期五8.2.1通路与回路例：图中开始于结点1结束于结点3的通路有： P1:(1,2,3) P2:(1,4,3) P3:(1,2,4,3) P4:(1,2,4,1,2,3) P5:(1,2,4,1,4,3) P6:(1,1,1,2,3)P1,P2,P3均是基本通路P5是简单回路但不是基本通路第二十九页，共七十三页，编辑于2023年，星期五8.2.1通路与回路图中的一条通路如果其起始结点与终止结点相同,则称此通路为回路.回路是一种特殊的通路.图中各边全不同的回路称为简单回路,各点全不同的称为基本回路.任一通路如果删去所有回路，则必得基本回路;任一回路中删去其中间的所有其余回路,必得基本回路. C1:(1,1) C2:(1,2,1) C2:(1,2,1) C4:(1,2,3,1) 均是基本回路. C5:(1,2,3,2,1) 是简单回路但不是基本回路.第三十页，共七十三页，编辑于2023年，星期五8.2.1通路与回路定理8.2 一个有向(n,m)图中任何基本通路长度均小于或等于n-1,而任何基本回路长度均小于或等于n.资源分配图：是一个有向图，表示时刻t时系统中资源分配状态.当进程Pk占有资源Ri而又深情资源Rj时，则从结点Ri到Ri用一条有向边相连.第三十一页，共七十三页，编辑于2023年，星期五8.2.1通路与回路例8.3R={R1,R2,R3,R4}P={P1,P2,P3,P4} 其资源分配状况是： P1占有资源R4且申请资源R1; P2占有资源R1且申请资源R2及R3; P3占有资源R2且申请资源R3; P4占有资源R3且申请资源R1及R4.解： 其资源分配图：第三十二页，共七十三页，编辑于2023年，星期五8.2.1通路与回路例8.4用有向图刻画过程间的调用关系，来判断某过程是否是递归的. 一个过程集合P={P1,P2,P3,P4,P5} 调用关系： P1调用P2； P2调用P4； P3调用P1； P4调用P5； P5调用P2；某过程是递归的充分必要条件是包括此过程在内的结点构成一个回路.(P2,P4,P5,

P2)构成一条回路,故过程P2,P4和P5是递归的第三十三页，共七十三页，编辑于2023年，星期五8.2.1通路与回路定义8.4从一有向图的结点vi到另一vj如果存在一条通路,则称从vi到vj是可达的.vi到vj是可达的不一定表示它们间只有一条通路,也可能有若干条通路,它们间最短的通路,这种通路称为短程线,而短程线的长度则称从vi到vj间的距离,可用d(vi,vj)表示.第三十四页，共七十三页，编辑于2023年，星期五8.2.1通路与回路在无向图中一条边lk对应于无序结点对(vi,vj),而此无序结点对(vi,vj)可以看成两个有序结点对(vi,vj)和(vj,vi).即可用方向相反的两条有向边取代一条无向边,这样,一个无向图就转换为有向图了.第三十五页，共七十三页，编辑于2023年，星期五8.2.2连通性定义8.5 一个无向图G,如果它的任何两结点间均是可达的,则称图G为连通图;否则,称为非连通图.定义8.6 一个有向图,如果忽略其边的方向后得到的无向图是连通的,则称此有向图为连通图;否则,称为非连通图.第三十六页，共七十三页，编辑于2023年，星期五8.2.2连通性定义8.7 一个有向连通图G如果其任何两结点间均是互相可达的,则称图G是强连通的; 如果其任何两结点间至少存在一向是可达的,则称图G是单向连通的; 如果忽略边的方向后其无向图是连通的,则称图G是弱连通的.第三十七页，共七十三页，编辑于2023年，星期五8.2.2连通性无向图中的连通性是一种等价关系其等价类是V的一个划分第三十八页，共七十三页，编辑于2023年，星期五8.2.2连通性例：简单图G有n个结点,e条边,设e>(n-1)(n-2)/2,证明G是连通的证明:(反证法) 假设G=<V,E>不连通,设G可分成两个不相连通的连通分支(子图)G1和G2,并设G1和G2分别有n1,n2个结点,显然n1+n2=n.因为ni≥1,所以ni≤n-1(i=1,2). 与已知相矛盾,因此G是连通的.第三十九页，共七十三页，编辑于2023年，星期五例： (1)图的次数序列为2,2,3,3,4,则边数是多少？ 解:2m=2+2+3+3+4=14,m=7. (2)3,3,2,3;5,2,3,14能成为图的次数序列吗？为什么？ 解:不能.因为这两个序列中有奇数个结点是次数奇数. (3)图G有12条边,次数为3的结点有6个,其余结点次数均小于3,问图中至少有几个结点？ 解:次数为3的结点有6个占去18次数，还有6个次数由其余结点占有，其余结点的度数可为，当均为2时所用结点数最少，所以应由3个结点占有这6度，即图中至少有9个结点。第四十页，共七十三页，编辑于2023年，星期五8.3欧拉图定义8.8 图G的一个回路,若它通过G中的每条边一次,这样的回路称为欧拉回路,具有这种回路的图叫欧拉图.定理8.3 无向连通图G是欧拉图的充分必要条件是G的每个结点均具有偶次数,即无奇数次数的结点.第四十一页，共七十三页，编辑于2023年，星期五8.3欧拉图定义8.9

通过图G中每条边一次的通路(非回路)称为欧拉通路.具有这种通路的图叫欧拉半图.定理8.4无向连通图G中结点vi与vj间存在欧拉通路的充分必要条件是vi与vj的次数均为奇数而其他结点的次数为偶数.第四十二页，共七十三页，编辑于2023年，星期五8.3欧拉图例8.5图中deg(v1)=deg(v3)=3,deg(v2)=deg(v4)=2,故v1和v3间存在一条欧拉通路,从图中可以知道这条通路是 C:(v1,v2,v3,v1,v4,v3) 但是这个图中不存在欧拉回路.第四十三页，共七十三页，编辑于2023年，星期五8.3欧拉图例8.6邮递员从邮局v1出发沿邮路投递信件，其邮路图如图所示,试问是否存在一条投递路线使邮递员从邮局出发通过所有路线而不重复且最后回到邮局.第四十四页，共七十三页，编辑于2023年，星期五8.3欧拉图解：此问题就是验证该图是否为欧拉图. 经检验图中每个结点均为偶次数,由定理8.3可知这样的一条投递线路是存在的. 我们可以找出这样一条线路： C:(v1,v5,v11,v7,v12,v8,v10,v6,v9,v11,v12,v10,v9,v5,v2,v6,v4,v8,v3,v7,v1) 该线路不是唯一的.例8.7洒水车从A点出发执行洒水任务,城市街道图形如图所示,试问是否存在一条洒水路线使洒水车从A点出发通过所有街道且不重复而最后回到车库B.第四十五页，共七十三页，编辑于2023年，星期五8.3欧拉图例8.8判断图中4个图形是否可以一笔连续画成而使图中没有一部分被重复.图(a)(c)(d)是欧拉通路,图(b)是欧拉回路.第四十六页，共七十三页，编辑于2023年，星期五8.3欧拉图例：构造一个欧拉图,其结点数v和边数e分别满足下述条件: 1)v,e的奇偶性一样 2)v,e的奇偶性相反 如果不可能,说明原因. 解：构造欧拉图与v,e的奇偶性没什么必然关系.第四十七页，共七十三页，编辑于2023年，星期五8.3欧拉图例：设图G是一个具有k个奇次结点的图,问最少加几条边到G中,而使所得的图有一条欧拉回路？解： 添加一条边能使两个结点的次数改变奇偶性 欧拉回路要使图中所有的结点次数均是偶数 所以对于k个奇次结点,要将它们变为偶次结点,至少添加k/2条边才能使它们都变成偶数.第四十八页，共七十三页，编辑于2023年，星期五8.3欧拉图例:

下图表示的是一个展览馆的平面图。馆里各相邻房间之间都有门（共16扇）。一个参观者来到展览馆门外，他想在参观过程中，把馆里所有的门都不重复地穿行一遍后出来，这个想法能否实现？解:首先建立该问题的图论模型。将展览馆的5个房间和馆外场地用6个结点表示，两个端点之间的边表示它们所在位置之间有一扇门(a)ABCDEF(b)BACDEF图中有4个奇点图中有4个奇点A,B,D,F,图(b)不是欧拉图,即参观者的想法不能实现。

第四十九页，共七十三页，编辑于2023年，星期五8.4汉密尔顿图爱尔兰数学家汉密尔顿（WilliamHamilton）爵士1859年提出了一个“周游世界”的游戏。这个游戏把一个正十二面体的二十个顶点看成地球上的二十个城市。棱线看成是连接城市的航路（航空、航海线或陆路交通线），要求游戏者沿棱线走，寻找一条经过所有结点（即城市）一次且仅一次的回路.第五十页，共七十三页，编辑于2023年，星期五8.4汉密尔顿图定义8.10

若图G的一个回路通过G中的每个点一次,这样的回路称为汉密尔顿图.定义8.11

通过图G中每结点一次的通路(非回路)称为汉密尔顿通路.定理8.5(必要条件)

设无向图G=<V,E>是汉密尔顿图,Ø⊆V1⊆V,则P(G-V1)≤|V1|,其中P(G-V1)是从G中删去V1(包括V1中相应结点及其关联的边)后所得到的图的连通分支数.第五十一页，共七十三页，编辑于2023年，星期五8.4汉密尔顿图汉密尔顿图的必要条件可用来判定某些图不是汉密尔顿图。例:解：图中共有9个结点,如果取结点集V1={3个白点}，即|V1|=3.而这时P(G-V1)=4.这说明该图不是汉密尔顿图。 但要注意若一个图满足该必要条件也不能保证这个图一定是汉密尔顿图,如图c。o。o。o。(a)(b)(c)第五十二页，共七十三页，编辑于2023年，星期五8.4汉密尔顿图定理8.6(充分条件) 设G=<V,E>为无向简单图,|V|≥3,如果G中每对结点次数之和≥|V|,则G必为汉密尔顿图.满足这个条件的图一定是汉密尔顿图。但不是所有的汉密尔顿图都满足这些条件.定理

(充分条件) 设G=<V,E>为无向简单图,|V|≥3,如果G中每对结点次数之和大于等于|V|-1,则G存在一条汉密尔顿通路.第五十三页，共七十三页，编辑于2023年，星期五8.4汉密尔顿图例：考虑在七天内安排七门课程的考试,使得同一位教师所任的两门课程考试不排在连接的两天中,试证明如果没有教师担任多于四门课程,则符合上述要求的考试安排总是可能的.解： 设G为具有七个结点的图,每个结点对应于一门课程考试,如果这两个结点对应的课程考试是由不同的老师担任的,那么这两个结点之间有一条边. 因为每个教师所任课程数不超过四,故每个节点的次数至少是3,任两个结点的次数之和至少是6,故G总是包含一条汉密尔顿通路,它对应于一个七门考试课目的一个适当的安排.第五十四页，共七十三页，编辑于2023年，星期五8.4汉密尔顿图例：某次会议有20人参加,其中每人都至少有10个朋友,这20人围一圆桌入席,要想使每个人相邻的两位都是朋友是否可能？根据是什么？解： 可用结点代表人,根据题意,两人是朋友对,相应结点间连一条边,则得到一个无向图G=<V,E>,可转化为求汉密尔顿回路问题. 由于每人至少10个朋友,故对任意结点u,v∈V,有deg(u)≥10,deg(v)≥10 所以deg(u)+deg(v)≥20.根据汉密尔顿回路的充分条件定理,可知G为汉密尔顿图,G中存在汉密尔顿回路,按此回路各点位置入席即为所求.第五十五页，共七十三页，编辑于2023年，星期五8.4汉密尔顿图推销员问题：设有某推销员为推销商品需要跑遍各大城市且不重复,而最后返回原地,需要找到一条总距离为最短的路线.可以用结点表示城市,城市间的交通路线用边表示,而城市间的交通线路距离可用附加于边的权表示.而该问题的目的即找一条权的总和为最短的汉密尔顿回路.第五十六页，共七十三页，编辑于2023年，星期五8.5图的矩阵表示法图的矩阵表示法的优点表示简单,可以表示较为复杂的图将图的问题变成计算问题，方便借助计算机进行计算.第五十七页，共七十三页，编辑于2023年，星期五8.5.1有向图的邻接矩阵设有一有向图G=<V,E>,其中 V={v1,v2,…,vn} E={e1,e2,…,em} 假设各结点按一定顺序排列 这时构成一矩阵: A=(aij)n×n

其中: 此矩阵称为图G的邻接矩阵.第五十八页，共七十三页，编辑于2023年，星期五8.5.1有向图的邻接矩阵例：有图如下，请写出它的邻接矩阵解：v1v2v3v4第五十九页，共七十三页，编辑于2023年，星期五8.5.1有向图的邻接矩阵设有图G=<V,E>,其邻接矩阵为可由邻接矩阵很容易地辨认其对应的图的一些特性来.环：矩阵对角线元素有1零图：矩阵元素全为0完全图：除对角线元素为0外,其余全为1第六十页，共七十三页，编辑于2023年，星期五8.5.1有向图的邻接矩阵图G中结点vi的引出次数结点vi的引入次数其全次数C=Al,此时cij表示从vi到vj长度为l的通路数目,如cij=0,则表示长度为l的通路没有,而cii给出了从vi出发的长度为l的回路数目.第六十一页，共七十三页，编辑于2023年，星期五8.5.2可达性矩阵Rn=(rij)n×n Rn=A+A2+A3+…+An 若rij=0,表示从vi到vj是不可达的 若rij≠0,表示从vi到vj是可达的可达性矩阵(通路矩阵) P

=(pij)n×n rij=0时,令pij=0 rij≠0时,令pij=1一个图G的可达性矩阵给出了图中各结点间是否可达以及图中是否有回路.第六十二页，共七十三页，编辑于2023年，星期五8.5.2可达性矩阵可达性矩阵的简单算法P=A(+)A(2)(+)A(3)(+)…(+)A(n)

A(i)表示在布尔矩阵运算意义下A的i次幂 (+)表示在布尔矩阵运算意义下加法运算第六十三页，共七十三页，编辑于2023年，星期五8.5.3无向图的矩阵表示法将无向图中的无向边用两条方向相反的有向边替代,使无向图转换为有向图. 这样,有向图中的邻接矩阵、可达性矩阵等均适用于无向图.如：无向图的邻接矩阵都是对称矩阵.第六十四页，共七十三页，编辑于