离散数学基础第六章图论

第六章图《离散数学基础》——谢胜利1煤气管道的铺设问题。现为城市的各小区之间铺设煤气管道(如下图所示)，对n个小区只需铺设n-1条管线，由于地理环境不同等因素使各条管线所需投资不同，如何使投资成本最低？

图论问题2第1节图的基本概念36.1图的起源一、哥尼斯堡七桥问题

18世纪的东普鲁士有个哥尼斯堡城，在横贯全城的普雷格尔河两岸和两个岛之间架设了7座桥，它们把河的两岸和两个岛连接起来。从河岸或小岛出发，七座桥每座桥恰好通过一次，再回到原地，是否可能？6.1图的基本概念4

数学大师欧拉对七桥问题给出否定回答，并给出严格的证明(Euler图)。1736年，欧拉对七桥问题的抽象和论证思想，开创了图论的研究，这一年可以看成是图论的元年。5二、Hamilton环球旅行游戏1895年，Hamilton设计一个“环球旅行”游戏：

在一个正12面体的20个顶点上各标志一个城市，如果从一城市出发，沿正12面体的棱行走，每个城市恰好经过一次，再回到出发点，则算旅行成功。6

对于该游戏的抽象得到图论中一个很重要的概念：Hamilton图。7一、图的概念

定义5.1.1图G(graph)主要由2部分组成:(1)结点集合V,其中的元素称为结点或顶点(vertex或node).(2)边集合E,其中的元素称为边(edge).通常将图G记为G=(V,E).§1无向图和有向图81、图绘制的几点说明:(a)结点或顶点，常用一个实心点或空心点表示，但在实际应用中还可以用诸如方形、圆形、菱形等符号。(b)边的表示：无向边，例：e3=（v3,v4）=（v4,v3）有向边(弧)，例：e8=<v2,v3>起点终点e3v3v4e8v2v39有向图无向图2、图的基本术语有向图：图中各边都是有向边无向图：图中各边都是无向边混合图：图中既有有向边又有无向边10顶点与边的关联：若从结点u到结点v有边l，则称边l与结点u和v相关联(incident)

。顶点与顶点的邻接：若从结点u到结点v有边，则结点u和v互为邻接顶点。无向图边与边的邻接：有公共端点的边互为邻接边无向图有向图11有限图：图中仅有有限个顶点。（无限图：图中有无限个顶点。）N阶图：具有n个顶点的有限图。零图：只有顶点而没有边的图平行边：两顶点之间有多条边（若为有向图则方向也相同）。边的重数：两顶点间平行边的条数。多重图：含有平行边的多重图。自环（自回路）：两个端点重合的边简单图：不含平行边且不含自环的图。1213权重图（赋权图）：设G=(V,E)是任意图，若G的每一条边上都赋予一个非负实数，则称G是权重图（边赋权图）。每条边上所赋的非负实数称为这条边上的权，它可以理解为该边上的流量或通过该边的时间，还可以理解为该边的长度。14二、图中顶点的度数1、无向图中顶点的度数【定义】在图（无向图或有向图）中，若顶点a和b是边e的两个端点，则称顶点a和b是邻接的，并称边e关联于顶点a和b。【定义】设图G是无向图，v是图G中的顶点，与v关联的边的条数称为顶点v的度数，记作deg(v)。

与结点v关联的环对v的度数的贡献要计算两次15孤立点：度数为零的顶点悬挂点：度数为1的顶点悬挂边：与悬挂点关联的边K度点：度数为k的顶点16【定理】（握手定理）任一图中，顶点的度数的总和等于边数的二倍，即【推论】任一图中，奇度数顶点的个数必为偶数。17由定理及其推论容易知道：在任何一次聚会上，所有人握手次数之和必为偶数并且握了奇数次手的人数必为偶数。(平行边及环的解释?)18【例】下列各组数中，哪些可以构成无向图的度数列：（1）1，1，1，2，2（2）2，2，2，2，3（3）2，3，3，3，3（4）2，2，2，2，219【例】求解下列各题:(1)图G的度数列为2，2，3，5，6，则边数m为多少?解：由握手定理：2m=∑deg(v)=2+2+3+5+6=18，知m=9。20(2)图G有12条边，度数为3的顶点有6个，余者度数均小于3，问G至少有几个顶点？解：由握手定理∑deg(v)=2m=24，度数为3的顶点有6个占去18度，还有6度由其余顶点占有;而由题意，其余顶点的度数可为0，1，2;当均为2时所用顶点数最少，所以应有3个顶点占有此6度，即G中至少有9个顶点。21

【例】

证明:在n（n≥2）个人的团体中，必有两个人有相同个数的朋友。

解：以顶点代表人，二人如果是朋友，则在代表他们的顶点间连上一条边，这样可得简单无向图G，每个人的朋友数即图中代表它的顶点的度数，于是问题转化为：

n阶简单无向图G中必有两个顶点的度数相同。22（2）有向图中顶点的度数【定义】设图G是有向图，v是G的顶点，以v为始点的有向边的条数称为v的出度，称为deg+(v),以v为终点的有向边的条数称为v的入度，称为deg-(v)。例：deg+(a)=2deg-(a)=1deg+(b)=0deg-(b)=2deg+(c)=1deg-(c)=2deg+(d)=2deg-(d)=2deg+(e)=2deg-(e)=023【定理】设图G是有向图，G中含有n个顶点和m条边，则图中各顶点的的出度之和与各顶点的入度之和相等，且等于图的边数。24三、特殊图【定义】设图G为无向简单图，如果图G中各个顶点的度数都为k，则称G为k度正则图，记为k-正则图25三、特殊图【定义】在n阶无向简单图中，如果任意两个不同的顶点之间都有一条边关联，则称此无向简单图为无向完全图，记作Kn。无向完全图Kn的边数是多少？

【定理】在n阶无向完全图Kn中，共有n(n-1)/2条边。26【定义】在n阶有向图中，如果任意两个不同的顶点之间都有两条方向相反的有向边关联，且每一个顶点都有自回路，则称此有向图为有向完全图。有向完全图各顶点的入度与出度是多少？三、特殊图

27四、子图【定义】在图G中删去一些边或顶点后所得的图称为图G的子图。删边：删去图中某一条边，但仍保留这条边的两个端点。删点：删去图中某一点以及与这个点关联的所有边。28删边删点29【定义】由图G中删去一些边后所得到的子图称为图G的生成子图。【定义】在图G中仅删去一个顶点后所得的子图称为图G的主子图。30子图示例:31五、图的同构由于在画图的图形时，顶点的位置和边的几何形状是无关紧要的，因此表面上完全不同的图形可能表示的是同一个图。32定义为了判断不同的图形是否反映同一个图形的性质，我们给出图的同构的概念。设有两个图G1=(V1,E1)，G2=(V2,E2)，如果存在着双射：V1→V2，使得(u,v)∈E1当且仅当((u),(v))∈E2

且边的重数相同，则称图G1与G2同构，记作G1

G2。33直观理解:

G1

G2是指其中一个图仅经过下列两种变换可以变为另一个图:(a)挪动结点的位置；(b)伸缩边的长短。两个图同构的必要条件:（1）结点数目相同；（2）边数相同；（3）度数相同的结点数相同。34例：35例：36【示例】下图中，G1G2，其中

f：V1→V2，f（vi）=ui（i=1，2，…，6）。

G3

G4，其中

f：V1→V2，f（v1）=u3，f（v2）=u1，f（v3）=u237注意：顶点数相同、边数相同、度数列相同为二图同构的必要条件而非充分条件38【例】证明下图中，G与G’不同构。125634GabefcdG’分析

证明两个图不同构，通常用反证法。证明

假设G≌G’，双射函数为。由定义，v与(v)的度数一定相同，因此有(3)=d。G中3与一个度数为1的结点6邻接，而G’中d与两个度数为1的结点e、f邻接，矛盾。39

在图的集合上定义二元关系R：对于图G1、G2，G1RG2当且仅当G1和G2同构，称R为图的同构关系。容易证明，图的同构关系是等价关系。

40六、补图

【定义】

G为n阶简单图，由G的所有顶点和能使G成为完全图的添加边所构成的图称为G的相对于完全图的补图，简称G的补图，记作。

41【例】下图中是G相对于K5的补图。42对于补图,显然有以下结论(3)n阶完全图与n阶零图互为补图43第2节图的连通性44一、通路与回路

右图是中国铁路交通图的一部分，旅客乘火车旅行，相当于从一个结点出发，沿着一些边连续移动到另一个结点，这就引出了通路的概念。成都昆明重庆广州长沙武汉上海兰州西安沈阳北京天津郑州厦门高雄台北45一、通路定义在任意一个图G=(V,E)中，称G中结点与边交替出现的序列L：为从v0到vn的一条通路或路径。ei的起点ei的终点通路的起点通路的终点46通路的长度：一条路中所包含的边数。对于权重图，通路的长度为通路中各边的权重之和。47路的简记：1)结点序列2)边序列48

【例】一个人带着一只狼、一只羊和一捆草要渡河，由于船太小，人做摆渡者一次只能运送一个“乘客”，很显然，如果人不在，狼要吃羊，羊要吃草，问人怎样才能把它们安全地渡过河去？49解：这是通路问题的一个典型实例。用f表示人，w表示狼，s表示羊，h表示草。集合{f，w，s，h}中能安全在一起的子集有：{f，w，s，h}，{f，w，s}，{f，s，h}，{f，w，h}，{f，w}，{f，s}，{f，h}，{w，h}，{f}，{w}，{s}，{h}。50原岸对岸{f，w，s，h}{}{f，w，s}{h}{f，s，h}{w}{f，w，h}{s}{f，s}{w，h}原岸对岸{}{f，w，s，h}{h}{f，w，s}{w}{f，s，h}{s}{f，w，h}{w，h}{f，s}初始状态结束状态渡河过程中所有可能的安全状态：可以使用二元组表示安全状态：第一元素表示留在原岸的子集，第二元素表示留在对岸的子集。51用顶点表示渡河过程中的状态，将可以通过一次渡河进行转换的状态利用一条有向边链接。容易看出，一条路径就是一种渡河方案。52二、回路定义1）起点与终点相同的通路(长度1)称为回路(circuit)。2）边不重复的回路称为简单回路。3）除起点重复一次外,别的结点均不重复的简单回路称为基本回路或环(cycle)。53v0到v0的回路：简单回路，也是基本回路简单回路，非基本回路54定理在一个n阶图中，若从顶点u到顶点v（u≠v）存在通路，则从u到v存在长度小于等于n-1的基本通路。

在一个n阶图中，若从顶点u到自身存在回路，则从u到自身存在长度小于等于n的基本回路。55三、图的连通性由于结点v到v总存在一条长度为0的路,因此规定：任意结点v可达v自身。定义5.1.8若从图的结点u到v存在一条路,则称u到v是可达的

(accessible)

。56定义若无向图G中任意两点均可达，则称G是连通图，否则称G是非连通图或不连通图。特别地，单独一个结点是连通图。定义如果无向图是非连通图，则图能分解为k个不相交的连通子图，称连通子图为此非连通图的连通分支。57【例】下图所示：图G1是连通图；图G2是一个非连通图。58

【例】在一次国际会议中，由七人组成的小组{a,b,c,d,e,f,g}中：a会英语、阿拉伯语；b会英语、西班牙语；c会汉语、俄语；d会日语、西班牙语；e会德语、汉语和法语；f会日语、俄语；g会英语、法语和德语。问：他们中间任何二人是否均可对话（必要时可通过别人翻译）？5960

【定义】设图G是无向连通图，如果图G中存在一个顶点v，使得删去顶点v后，图G成为不连通图，则称v为割点。

【定义】设图G是无向连通图，如果图G中存在一条边u，使得删去边u后，图G成为不连通图，则称v为割边或桥。61

【定义】在简单有向图G中，若任二顶点间均相互可达，则称G为强连通图；若任二顶点间至少从一个顶点到另一个顶点是可达的，则称G是单向连通图；若在忽略G中各边的方向时G是无向连通图，则称G是弱连通图。

62【例】下图中，图(a)是强连通图，图(b)是单向连通图，图(c)是弱连通图。abcdabcdabcd63第3节图的表示64【定义】设无向图G的点集为V，边集为E，且V={v1，v2，…，vn}，E={e1,e2,…,em},令则称(mij)

n×m

为G的关联矩阵，记作M(G)§1图的关联矩阵65【例】求下图G的关联矩阵。66无向图的关联矩阵的特性：（1），即M(G)每列元素之和为2，因为每条边恰有两个端点（若是简单图则每列恰有两个1）。（2），因而全为0的行所对应的顶点是孤立顶点。67*4、有向无环图的关联矩阵

【定义】设G=〈V,E〉是有向无环图，

V={v1，v2，…，vn}，E={e1，e2，…，em}，令vi是ej的起点vi与ej不关联vi是ej的终点则称(mij)

n×n

为G的关联矩阵，记作M(G)。6869M(G)的特性：

（1）（一条边关联两个点：一个起点，一个终点），从而有。（2）每一行中1的数目是该点的出度，-1的数目是该点的入度。（3）二列相同，当且仅当对应的边是平行边（同向）。（4）全为0的行对应孤立顶点。70

注:无向图也有相应的邻接矩阵，一般只考虑简单图，无向图的邻接矩阵是对称的，其性质基本与有向图邻接矩阵的性质相同。71定义设图G=(V,E)，V={v1,v2,…,vn}，则称矩阵为图G的邻接矩阵，其中aij是vi邻接到vj的边数,i,j=1,2,…,n。§2图的邻接矩阵

72无向图中自环对应主对角线上元素是1还是2？73由邻接矩阵很容易地看出：一个矩阵元素全为0则其对应的图为零图。一矩阵的元素除对角线元素为0外，全为1则其对应的图为完全图。对于无向图，其邻接矩阵关于主对角线对称。一个图与其邻接矩阵是一一对应的。对权重图，aij可取该边的权重。74从一个图G的邻接矩阵A(G)容易得出每个结点的度数：1）有向图：752）无向图：76练习现有如下所示图：(1)写出该图的关联矩阵和邻接矩阵。(2)求各个顶点的度。(3)图中是否存在平行边？如果存在，请指出。77定理设A是图G的邻接矩阵,则Al中(i,j)位置元素aij(l)

为从结点vi到vj长度为l(l

1)的路的数目。78例：在图G中，求出：（1）从v2到v4长度为1,2,3,4的通路各有多少条？（2）长度为3的路共有多少条？其中有多少条是回路？解：邻接矩阵798081（1）从v2到v4长度为1,2,3,4的通路分别有1,0,0,4条。（2）由于A3中所有元素之和为20,所以长度为3的路共有20条。又由于对角线上元素之和为12，故其中有12条是回路。82定义设图G=(V,E)，V={v1,v2,…,vn}，则称矩阵为图G的可达矩阵，其中rij给出了从vi到vj的所有长度为1~n的通路数目之和。若rij＝0则表示vi到vj不可达。§3图的可达矩阵83例84说明:容易从图的可达矩阵得出图的连通性质：1）对无向图的可达矩阵若rij＝rji>0(i,j=1~n;i≠j),则该图为连通图。2）对有向图的可达矩阵若rij与rji中只有一个大于零(i,j=1~n;i≠j),则该图为单向连通图（弱连通图）。若rij与rji都大于零(i,j=1~n;i≠j),则该图为双向连通图（强连通图）。85判定算法为：isConnect(A，n)//A为图的邻接矩阵，n为图中点的个数{R=0；//初始矩阵Rfori=1ton{A=MatrixMulti(A,A)//完成矩阵相乘 R=R+A；//进行矩阵相加，计算可达性矩阵}fori=1tonforj=1ton{if(rij=0andi≠j)returnfalse;}returntrue;}86第4节一些特殊的图87§1二部图【定义】无向图G=〈V，E〉的顶点集V能分成两个子集V1和V2，满足（1）V=V1∪V2，V1∩V2=Φ；（2）任给e=（u，v）∈E，均有u∈V1，v∈V2。则称G为二部图。【定义】设G=(V,E)是二部图，如果V1中每个顶点都与V2中所有顶点邻接，则称G为完全二部图，并记为Km,n，其中m=|V1|，n=|V2|。Km,n的边数是多少？88上图中的三个图均是二部图，其中图（b）是完全二部图K3，3，图（c）是K2，4。Km,n的边数是多少？89定理一个无向图是二部图当且仅当图中无奇数长度的回路。90有些图虽然表面上不是上面的样式，但经过改画就能成为上面的样式，仍可判定它是一个二部图，如上图中（a）可改画成图（b），图（c）可改画成图（d）。91（补）二部图的应用某公司招聘了3名大学毕业生，公司有5个部门需要人。不考虑单向的意愿，毕业生意愿去这个部门，这个部门也同意接收这名毕业生如表所示。部门1部门2部门3部门4部门5毕业生A***毕业生B***毕业生C***有什么分配方案使得在每个部门最多可接收一个毕业生的前提下毕业生都满意！92定义设G=(V,E)是任意图,则G中经过所有边一次且仅一次的通路称为欧拉通路;G中经过所有边一次且仅一次的回路称为欧拉回路;存在欧拉回路的图称为欧拉图或简称为E图.

一、欧拉图的有关概念§2欧拉图93定理连通无向图G是欧拉图的充要条件是G的每个结点的度数都是偶数（这样的顶点称为偶度结点）。

二、欧拉定理定理有向图G是欧拉图的充要条件是G的每个结点的入度等于其出度。94由于在七桥问题的图中，有４个点是奇度顶点，故不存在欧拉回路，七桥问题无解。95图中存在欧拉回路:96定理设G是连通无向图,则G中存在欧拉通路的充要条件是G的度数为奇数的结点个数为0或为2。根据该定理知,“七桥问题”甚至不存在欧拉轨迹。97图中存在欧拉通路，但不存在欧拉回路。98“一笔画问题”：所谓一个图能一笔画出是指从图的某结点出发，线可以相交但不能重合，不起笔就可以将图画完。如果该图为欧拉图，则能够一笔画完该图，并且笔又回到出发点；如果该图只存在欧拉通路，则能够一笔画完该图，但笔回不到出发点；如果该图中不存在欧拉通路，则不能一笔画完该图。99【例】图中的三个图能否一笔画？为什么？v1v2v3v4v5(b)v1v2v3v4(c)v1v2v3v4v5(a)解

因为图(a)和(b)中分别有0个和2个奇度数结点，所以它们分别是欧拉图和存在欧拉通路，因此能够一笔画，并且在(a)中笔能回到出发点，而(b)中笔不能回到出发点。图c中有4个度数为3的结点，所以不存在欧拉通路，因此不能一笔画。100蚂蚁比赛问题：

【例】甲、乙两只蚂蚁分别位于图的结点A、B处，并设图中的边长度相等。甲、乙进行比赛：从它们所在的结点出发，走过图中所有边最后到达结点C处。如果它们的速度相同，问谁先到达目的地？A(甲)B(乙)C解

图中仅有两个度数为奇数的结点B、C，因而存在从B到C的欧拉通路，蚂蚁乙走到C只要走一条欧拉通路，边数为9条，而蚂蚁甲要想走完所有的边到达C，至少要先走一条边到达B，再走一条欧拉通路，因而它至少要走10条边才能到达C，所以乙必胜。101

例下图是一幢房子的平面图形，前门进入一个客厅，由客厅通向4个房间。如果要求每扇门只能进出一次，现在你由前门进去，能否通过所有的门走遍所有的房间和客厅，然后从后门走出。奇度顶点奇度顶点奇度顶点奇度顶点不存在欧拉通路，所以，此题无解。102定义5.5.1设G=(V,E)是任意图,则G中经过所有结点一次且仅一次的通路称为汉密尔顿通路;G中经过所有结点一次且仅一次(除起点重复一次外)的回路称为汉密尔顿回路;存在汉密尔顿回路的图称为汉密尔顿图。一、汉密尔顿图的有关概念§3汉密尔顿图103由汉密尔顿回路可得到汉密尔顿路径,但反过来一般不成立。如(a)存在汉密尔顿路径bcade,但不存在汉密尔顿回路。(b)存在汉密尔顿回路v1v5v4v3v2v1,它是汉密尔顿图。104例：汉密尔顿回路问题。它是1859年汉密尔顿首先提出的一个关于12面体的数学游戏：能否在下图中找到一个回路，使它含有图中所有顶点一次且仅一次？这个问题也被称作周游世界问题。105尽管汉密尔顿回路与欧拉回路问题在形式上极为相似，但是到目前为止还不知道一个图为汉密尔顿图的充要条件，寻找该充要条件仍是图论中尚未解决的主要问题之一。下面先给出一个简单而有用的必要条件。106定理设图G＝（V,E）是汉密尔顿无向图，则对于任意

W

V,均有w(G-W)|W|成立，其中w(G-W)是图G－W的连通分支数。

二、汉密尔顿图的必要条件107上述定理在应用中它本身用处不大，但它的逆否命题却非常有用。我们经常利用其逆否命题来判断某些图不是汉密尔顿图，即：若存在V的某个非空子集W使得w(G-W)＞|W|，则G不是汉密尔顿图。

108例如：考虑下图中的(a)删去的顶点删去的顶点3个连通分支所以(a)不是汉密尔顿图109判断图(a),(b)是不是汉密尔顿图:v3v1v2v4v5v6v7v2v4v1v5v3(a)(b)删去的顶点删去的顶点删去的顶点110定理设G=(V,E)是n(n

3)阶简单无向图,若对于任意的不相邻结点u,v

V,有deg(u)＋deg(v)≥n则G是汉密尔顿图。

三、汉密尔顿图的充分条件111注意，上述定理给出的是汉密尔顿图的充分条件，而不是必要条件。例如,在六边形中，任两个不相邻的结点的度数之和都是4＜6，但六边形是汉密顿图。112推论设G=(V,E)是n(n

3)阶简单无向图,若对于任意结点v

V,有deg(v)

n/2,则G是汉密尔顿图。113定理设G=(V,E)是n(n

3)阶简单无向图,若对于任意的不相邻结点u,v

V,有deg(u)＋deg(v)≥n-1则在G中存在汉密尔顿路径。

114【例】某地有5个风景点，若每个风景点均有2条道路与其他点相通。问游人可否经过每个风景点恰好一次而游完这5处？解

将5个风景点看成是有5个顶点的无向图(n=5)，两风景点间的道路看成是无向图的边。因为每处均有两条道路与其他顶点相通，故每个顶点的度数均为2，从而任意两个不同顶点的度数之和等于4，正好为总顶点数n减1。故此图中存在一条汉密顿路径，因此游人可以经过每个风景点恰好一次而游完这5处。115小结：欧拉通路与欧拉回路判别准则

对无向连通图，只需通过对图中各结点度数的计算，就可知它是否存在欧拉通路及欧拉回路，从而知道它是否为欧拉图；对有向连通图，只需通过对图中各结点出度与入度的计算，就可知它是否存在欧拉通路及欧拉回路，从而知道它是否为欧拉图。116第5节最短路径117在权重图中，从一个结点到另一个结点的通路上所有边上的权之和称为该通路的“权”。在实际应用中，经常需要得出从一个结点到别的结点权最小的一条路径（通路），称为最短路径。§1Dijkstra算法118例：（Dijkstra算法原理）结点v1到v6的最短路径？思路：依次求出距v1最近的结点（直至到达所求结点）及其最短路径。119步骤：到结点v1最近的结点是v4，最短路径是2。到结点v1第二近的结点是v2，最短路径是4（只需在与v1及v4邻接的结点中搜索）。到结点v1第三近的结点是v5，最短路径是5（只需在与v1、v4及v2邻接的结点中搜索）。到结点v1第四近的结点是v6，最短路径是6（只需在与v1、v4、v2及v5邻接的结点中搜索）。120Dijkstra算法：设G=(V,E)是n阶权重图，V={v1,v2,…,vn},用wij表示结点vi到vj的边上的权，若vi到vj无边，则令wij=+。

目标:求结点v1到其他任意结点的最短路径。121基本思想：设置一个集合S（也可以看作红点集）存放已经找到最短路径的顶点，S的初始状态只包含源点v，对vi∈V-S（也可以看作蓝点集）