离散数学图论

1、1 1问题问题1 1 最短路径问题最短路径问题 如下带权的有向图如下带权的有向图G=(VG=(V，E)E)中，求从结点中，求从结点0 0到其余各结点的到其余各结点的短路径和路径长度短路径和路径长度，其中结点，其中结点0 0称为源点。称为源点。 2 2 下表列出了有向图中从结点下表列出了有向图中从结点0到其余各结点的到其余各结点的最短路径和路径长度。最短路径和路径长度。源点源点终点终点最短路径最短路径路径路径长长度度01(0,2,3,1)452(0,2)103(0,2,3)254(0,2,3,1,4)5553 3问题问题2 2 旅行商问题旅行商问题 下图是连通无向图下图是连通无向图G=(VG=(

2、V，E)E)，求图的所有，求图的所有HamiltonHamilton回路。回路。 4 4第十四章第十四章 图的基本概念图的基本概念第十五章第十五章 欧拉图与哈密顿图欧拉图与哈密顿图 主要知识内容主要知识内容5 5本章知识点的本章知识点的关联图：关联图：6 6（1）多重集合）多重集合（2）无序积）无序积（3）无向图）无向图 顶点、边（无向边）顶点、边（无向边）例例1 如图，如图，V=v1, v2, ,v5, E=(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) （4）有向图）有向图 顶点、边（有向边）顶点、边（有向边）例例

3、2 如右图，如右图，试写出它的试写出它的V和和E。14.1 图图7 7 一般地，用小圆圈（或实心点）表示顶点，用一般地，用小圆圈（或实心点）表示顶点，用顶点间的连线表示无向边，用有方向的连线表示顶点间的连线表示无向边，用有方向的连线表示有向边。如有向边。如例例3 设设D=，V=a, b, c, d, e，E=, , , , , , ，画图。，画图。注意注意：图的数学定义与图形表示，在同构的意义：图的数学定义与图形表示，在同构的意义下是一一对应的。下是一一对应的。 8 8（5）几个特殊的图）几个特殊的图l通常用通常用G表示无向图表示无向图, D表示有向图表示有向图, 也常用也常用G泛指泛指无向图

4、和有向图无向图和有向图, 用用ek表示无向边或有向边表示无向边或有向边.l V(G), E(G) 表示图表示图G的顶点集的顶点集, 边集边集.l |V(G)|, |E(G)| 表示图表示图G的顶点数集（阶）和边数的顶点数集（阶）和边数. n 阶图、有限图、零图、平凡图、空图、基图阶图、有限图、零图、平凡图、空图、基图（6）顶点和边的关联）顶点和边的关联 关联、关联次数、环、孤立点关联、关联次数、环、孤立点（7）相邻）相邻 点相邻、边相邻点相邻、边相邻9 9（8）邻接）邻接 邻接到、邻接于邻接到、邻接于（9）邻域和关联集）邻域和关联集设无向图设无向图G, v V(G) v的邻域、的邻域、 v的闭

5、邻域、的闭邻域、 v的关联集的关联集设有向图设有向图D, v V(D) v的后继元集的后继元集 v的先驱元集的先驱元集 v的邻域的邻域 v的闭邻域的闭邻域1010（1010）多重图）多重图 平行边、重数平行边、重数（1111）简单图简单图例例4 判别下图是否是简单图？判别下图是否是简单图？1111（1212）顶点的度数顶点的度数 设设G=为无向图为无向图, v V, v的度数的度数(度度) d(v)：v作为边的端点次数之和作为边的端点次数之和 悬挂顶点悬挂顶点：度数为：度数为1的顶点的顶点 悬挂边悬挂边：与悬挂顶点关联的边：与悬挂顶点关联的边 G的最大度的最大度 (G)=maxd(v)| v

6、V G的最小度的最小度 (G)=mind(v)| v V例例5 如右图，如右图， d(v5)=3, d(v2)=4, d(v1)=4, (G)=4, (G)=1, v4是悬挂顶点是悬挂顶点, e7是悬挂边是悬挂边, e1是环。是环。1212设设D=为有向图为有向图, v V, v的出度的出度d+(v)：v作为边的始点次数之和作为边的始点次数之和 v的入度的入度d (v)：v作为边的终点次数之和作为边的终点次数之和 v的度数的度数(度度) d(v)：v作为边的端点次数之和作为边的端点次数之和 d(v)= d+(v)+ d-(v)D的最大出度的最大出度 +(D), 最小出度最小出度 +(D)最大入

7、度最大入度 (D), 最小入度最小入度 (D)最大度最大度 (D), 最小度最小度 (D) 例例6 如右图，如右图， d+(a)=4, d (a)=1, d(a)=5, d+(b)=0, d (b)=3, d(b)=3, +(D)=4, +(D)=0, (D)=3, (D)=1, (D)=5, (D)=3. 1313（13）握手定理）握手定理 定理定理 任意无向图和有向图的所有顶点度数之和都任意无向图和有向图的所有顶点度数之和都等于边数的等于边数的2倍倍, 并且有向图的所有顶点入度之并且有向图的所有顶点入度之和等于出度之和等于边数和等于出度之和等于边数.( )2( )( )d vmd vd v

8、m推论推论 在任何无向图和有向图中，奇度顶点的个数必在任何无向图和有向图中，奇度顶点的个数必为偶数为偶数.例例7 下列各图中各有多少个顶点？下列各图中各有多少个顶点？ (1) 16条边，每个顶点的度数均为条边，每个顶点的度数均为2。 (2) 21条边条边, 3个个4度的顶点度的顶点, 其余顶点的度数均为其余顶点的度数均为3。 (3) 24条边，每个顶点的度数均相同。条边，每个顶点的度数均相同。1414（1414）图的度数列图的度数列 设无向图设无向图G的顶点集的顶点集V=v1, , vn G的度数列的度数列: d(v1), d(v2), , d(vn)如右图度数列如右图度数列:4,4,2,1,

9、3设有向图设有向图D的顶点集的顶点集V=v1, v2, , vn D的度数列的度数列: d(v1), d(v2), , d(vn) D的出度列的出度列: d+(v1), , d+(vn) D的入度列的入度列: d (v1), , d (vn)如右图度数列如右图度数列:5,3,3,3 出度列：出度列：4,0,2,1 入度列：入度列：1,3,1,21515（15）可图化、可简单图化）可图化、可简单图化 定理定理：可图化：可图化 为偶数。为偶数。 定理定理：可简单图化，则：可简单图化，则(G) n-1。充分条件充分条件1niid例例8 (3,3,3,4), (2,3,4,6,8)能成为图的度数列吗能

10、成为图的度数列吗?例例9 已知图已知图G有有10条边，条边，4个个3度顶点，其余顶点度顶点，其余顶点的度数均小于的度数均小于2，问，问G至少有多少个顶点至少有多少个顶点? 例例10 根据度数列，画图根据度数列，画图. (1) d= (5,3,3,2,1) (2) d= (3,2,1) (3) d= (3,3,2,1)1616（16）图的同构图的同构 abc例例11 试画出试画出4阶阶3条边的所有非同构的无向简单图条边的所有非同构的无向简单图例例12 判断下述每一对图是否同构。判断下述每一对图是否同构。1717ed（17）完全图完全图 n阶无向完全图阶无向完全图Kn、n阶有向完全图阶有向完全图（

11、18）n阶阶k正则图正则图1818（19）子图）子图 子图子图、母图母图 、生成子图、真子图生成子图、真子图 V 的导出子图的导出子图、 E 的导出子图的导出子图 例例10 画出画出K4的所有非同构的生成子图。的所有非同构的生成子图。（20）补图、自补图）补图、自补图图的运算：图的运算：记记 G v：从：从G中删除中删除v及关联的边及关联的边 G V ：从：从G中删除中删除V 中所有的顶点及关联的边中所有的顶点及关联的边 G e：从：从G中删除中删除e G E ：从：从G中删除中删除E 中所有边中所有边1919（21）通路与回路）通路与回路 通路、起点通路、起点和和终点、长度、回路终点、长度、

12、回路 简单通路、简单回路简单通路、简单回路 初级通路初级通路(路径路径)、初级回路、初级回路(圈圈) 奇奇(偶偶)圈圈（22）通路与回路的性质）通路与回路的性质 P281-P22 定理定理14.5及推论、定理及推论、定理14.6及推论及推论14.2 通路与回路通路与回路2020说明说明:还可以用更简单的表示法表示通路和回路：还可以用更简单的表示法表示通路和回路： 只用边的序列，只用边的序列，如如 =e1e2el 简单图中，用顶点的序列，简单图中，用顶点的序列，如如 =v0v1vl 非简单图中非简单图中,可用混合表示法可用混合表示法, 如如 =v0v1e2v2e5v3v4v5环是长度为环是长度为

13、1的圈的圈, 两条平行边构成长度为两条平行边构成长度为2的圈。的圈。简单无向图中，圈的长度简单无向图中，圈的长度 3；在有向简单图中；在有向简单图中, 所所有圈的长度有圈的长度 2。复杂通路和复杂回路：复杂通路和复杂回路： 中的边重复出现。中的边重复出现。2121（23）无向图的连通性）无向图的连通性 设无向图设无向图G=， u, v V，u与与v连通连通：u与与v之间存在通路之间存在通路. 记作记作u v. 规定规定u u。连通关系连通关系： =| u,v V且且u v是等价关系。是等价关系。连通图连通图：平凡图：平凡图, 任意两点都连通的图。任意两点都连通的图。 否则称否则称G为非连通图。

14、为非连通图。如图如图G1是非连通图，是非连通图， G2是连通图。是连通图。14.3 图的连通性图的连通性2222连通分支连通分支：设无向图：设无向图G=，V关于顶点之间的关于顶点之间的连通关系连通关系 的商集的商集 V/ =V1,V2,Vk，Vi为等价为等价类，称导出子图类，称导出子图GVi (i=1,2,k) 为为G的连通分的连通分支支, 其个数记作其个数记作p(G)=k。如：如： p(G1)=2， p(G2)=1 G是连通图是连通图 p(G)=1 n阶零图的连通分支数最多，阶零图的连通分支数最多， p(Nn)=n2323（24）无向图的短程线与距离）无向图的短程线与距离短程线短程线：u与与

15、v之间长度最短的通路。之间长度最短的通路。 （路）（路）距离距离d(u,v)：u与与v之间短程线的长度。之间短程线的长度。 （数）（数） 规定，若规定，若u与与v不连通，不连通，d(u,v)=。性质：性质： d(u,v) 0, 且且d(u,v)=0 u=v d(u,v)=d(v,u) d(u,v)+d(v,w) d(u,w) 2424（25）点割集）点割集 定义：定义： 点割集点割集 割点割点例例11 如右图，写出所如右图，写出所有的点割集和割点。有的点割集和割点。 例例12 如下图，写如下图，写出所有的点割集出所有的点割集和割点。和割点。2525（26）边割集）边割集 定义：定义： 边割集边

16、割集 割边（桥）割边（桥） 例例13 写出例写出例11和例和例12的所有边割集和桥。的所有边割集和桥。几点说明：几点说明： Kn无点割集无点割集 n阶零图既无点割集，也无边割集阶零图既无点割集，也无边割集. 若若G连通，连通，E 为边割集，则为边割集，则p(G E )=2 若若G连通，连通，V 为点割集，则为点割集，则p(G V ) 2 2626G例例14 如右图如右图G，是，是1-连通图，连通图， k边边-连通图，连通图，k=1，2 (G)=1， (G)=2 定理定理 对于任何无向图对于任何无向图G，有，有 (G)(G)(G)（27）点）点(边边)连通度连通度 点连通度点连通度：(G)=mi

17、n|V | | V 为为G的点割集的点割集 边连通度边连通度：(G)=min|E | | E 为为G的边割集的边割集 如例如例11中，中， (G)=1， (G)=2。2727（28）有向图的连通性）有向图的连通性 设有向图设有向图D= ， vi, vj Vvi可达可达vj：若：若vi 到到vj 存在通路。记存在通路。记vi vj 。 规定规定 自身可达，即自身可达，即vi vi 。 vi与与vj相互可达相互可达，记记vi vj 。规定。规定 vi vi 说明：说明： 是是V上的等价关系。上的等价关系。D弱连通弱连通(连通连通)：D的基图为无向连通图的基图为无向连通图D单向连通单向连通： vi

18、vj或或vj vi 至少成立起一至少成立起一D强连通强连通： vi, vj V，均有，均有vi vj 强连通强连通单向连通单向连通弱连通弱连通 2828定理定理(强连通判别法强连通判别法) D强连通当且仅当强连通当且仅当D中存在经中存在经过每个顶点至少一次的回路。过每个顶点至少一次的回路。定理定理(单向连通判别法单向连通判别法) D单向连通当且仅当单向连通当且仅当D中存中存在经过每个顶点至少一次的通路。在经过每个顶点至少一次的通路。 例例15 判断以下有向图的连通性。判断以下有向图的连通性。2929练习练习1 如右图，分别求：如右图，分别求：(1) a, d之间所有不同的通路；之间所有不同的通

19、路；(2) a, d之间的短程线；之间的短程线；(3) d(a, d)。练习练习2 判断以下判断以下有向图的连通性。有向图的连通性。3030（29）有向图的短程线与距离）有向图的短程线与距离短程线短程线： vi到到vj长度最短的通路长度最短的通路 (vi可达可达vj)。距离距离d： vi到到vj 的短程线的长度。的短程线的长度。 若若u不可达不可达v, 规定规定d=.性质：性质： d 0, 且且d=0 u=v d+d d 注意：没有对称性注意：没有对称性3131（30）二部图）二部图定义：定义：二部图二部图：无向图无向图G, V1 V2=V, V1 V2=, V1， V2, G中每条边的两个端

20、点都一个属于中每条边的两个端点都一个属于V1, 另一另一个属于个属于V2，记为，记为。 称称V1和和V2为为互补顶点子集互补顶点子集。完全二部图完全二部图：若若G是简单图是简单图, 且且V1中每个顶点均与中每个顶点均与V2中每个顶点都相邻，中每个顶点都相邻， 记为记为Kr,s, 其中其中r=|V1|, s=|V2|. 例如：例如： K3,3 ， K2,3注意注意: n 阶零图为二部图。阶零图为二部图。3232二部图的判别法：二部图的判别法：定理定理 无向图无向图G=是二部图是二部图 G中无奇圈。中无奇圈。 例例16 16 下述各图都是二部图下述各图都是二部图 3333（31）无向图的关联矩阵）

21、无向图的关联矩阵 无向图无向图G的关联矩阵的关联矩阵，记为，记为M(G)，表示点与边的，表示点与边的关联次数。关联次数。 性质：性质：P288例例17 如右图：如右图：2 1 1 1 00 1 1 0 0( )0 0 0 1 10 0 0 0 1M Ge1 e2 e3 e4 e5v1v2v3v4 14.4 图的矩阵表示图的矩阵表示 3434定义定义 M(D)=(mij)n m性质：性质：P288（32）有向图的关联矩阵有向图的关联矩阵 的终点的终点为为，不关联不关联与与，的始点的始点为为jijijiijevevevm10,1例例18 如下图：如下图：1 1 0 0 01 0 1 1 1( )0

22、 0 0 0 10 1 1 1 0MD3535定义定义 设有向图设有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令令 为顶点为顶点vi邻接到顶点邻接到顶点vj边的条数，边的条数，称称( )n n为为D的邻接矩阵的邻接矩阵, 记作记作A(D), 简记为简记为A。性质：性质： P289)1(ija)1(ija（33）有向图的邻接矩阵）有向图的邻接矩阵例例19 如右图：如右图：0 1 0 00 0 1 10 0 0 01 1 0 0A3636（34）D中的通路及回路数中的通路及回路数)(lija)(liia ninjlija11)( niliia1)(定理定理 设设A

23、为为n阶有向图阶有向图D的邻接矩阵的邻接矩阵, 则则Al(l 1)中中元素，元素， 为为D中中vi到到vj长度为长度为 l 的通路数，的通路数， 为为vi到自身长度为到自身长度为 l 的回路数，的回路数， 为为D中长度为中长度为 l 的通路总数，的通路总数， 为为D中长度为中长度为 l 的回路总数。的回路总数。 3737例例20 有向图有向图D如图所示如图所示, 求求A, A2, A3, A4, 并回答诸问题：并回答诸问题：(1) D中长度为中长度为1, 2, 3, 4的通路各有的通路各有多少条？其中回路分别为多少条？多少条？其中回路分别为多少条？(2) D中长度小于或等于中长度小于或等于4的

24、通路为的通路为多少条？其中有多少条回路？多少条？其中有多少条回路？ ninjlijb11)( niliib1)(推论推论 设设Bl=A+A2+Al(l 1), 则则Bl中元素中元素 为为D中长度小于或等于中长度小于或等于l 的通路数，的通路数， 为为D中长度小于或等于中长度小于或等于l 的回路数的回路数.3838定义定义 有向图有向图D的的可达矩阵可达矩阵 P = (pij)n n ，其中，其中性质：性质： P(D)主对角线上的元素全为主对角线上的元素全为1. D强连通当且仅当强连通当且仅当P(D)的元素全为的元素全为1.（35）有向图的可达矩阵）有向图的可达矩阵1,可达0, 否则ijijvv

25、p39391 0 0 01 1 1 11 0 1 11 0 1 1P计算方法：计算方法： （1）写出邻接矩阵；）写出邻接矩阵；（2）计算）计算Bn-1 = A+A2+An-1；（3）将）将Bn-1 中对角线上的元素和非零元素改为中对角线上的元素和非零元素改为1，即得即得P。例例21 21 如下图如下图D D 的可达矩阵为的可达矩阵为4040练习：已知图练习：已知图G的邻接矩阵的邻接矩阵 (1) d+(v3)=_， d (v1)=_， d(v2)=_； (2) 从从v1到到v4长度为长度为 2 的通路数；的通路数； (3) 从从v3到到v1长度为长度为 3 的通路数；的通路数； (4) 过过v4

26、长度为长度为 3 的回路数。的回路数。231 0 1 13 1 1 27 2 3 41 0 0 01 0 1 13 1 1 21 0 0 12 1 1 15 1 2 31 1 0 02 0 1 14 1 2 3AAA4141（36）欧拉图）欧拉图 欧拉通路欧拉通路：行遍所有顶点、恰好过每条边一次：行遍所有顶点、恰好过每条边一次. 欧拉回路、欧拉图、半欧拉图欧拉回路、欧拉图、半欧拉图几点说明：几点说明： 上述定义对无向图和有向图都适用上述定义对无向图和有向图都适用. 规定平凡图为欧拉图规定平凡图为欧拉图. 欧拉通路是简单通路欧拉通路是简单通路, 欧拉回路是简单回路欧拉回路是简单回路. 环不影响图

27、的欧拉性环不影响图的欧拉性. 15.1 欧拉图欧拉图4242例例22 22 判断下图是否是欧拉图？若不是，则至少加几判断下图是否是欧拉图？若不是，则至少加几条边才能成为欧拉图条边才能成为欧拉图? ?4343（37）欧拉图的判别法）欧拉图的判别法 定理定理 无向图无向图G为为欧拉图欧拉图 G连通连通且无奇度顶点且无奇度顶点. 无向图无向图G是半是半欧拉图欧拉图 G连通且恰有两个奇度连通且恰有两个奇度顶点顶点. 定理定理 有向图有向图D是是欧拉图欧拉图 当当D连通且每个顶点的入连通且每个顶点的入度都等于出度度都等于出度. 有向图有向图D具有欧拉通路具有欧拉通路 D连通且恰有两个奇连通且恰有两个奇度

28、顶点度顶点, 其中一个入度比出度大其中一个入度比出度大1, 另一个出度比入另一个出度比入度大度大1, 其余顶点的入度等于出度其余顶点的入度等于出度.4444例例23 23 下面两个图都是欧拉图。从下面两个图都是欧拉图。从A A点出发点出发, , 如何一如何一次成功地走出一条欧拉回路来？次成功地走出一条欧拉回路来？ 4545（38）哈密顿图）哈密顿图 哈密顿通路哈密顿通路：经过图中所有顶点一次且仅一次。：经过图中所有顶点一次且仅一次。 哈密顿回路哈密顿回路、哈密顿图、半哈密顿图哈密顿图、半哈密顿图几点说明：几点说明：平凡图是哈密顿图平凡图是哈密顿图. .哈密顿通路是初级通路，哈密顿回路是初级回路

29、哈密顿通路是初级通路，哈密顿回路是初级回路. .环与平行边不影响图的哈密顿性环与平行边不影响图的哈密顿性. .4646例例24 24 判别下图是否是哈密顿图。判别下图是否是哈密顿图。（39）哈密顿图的判别方法）哈密顿图的判别方法定理定理(必要条件必要条件) 设无向图设无向图G=是哈密顿图是哈密顿图, 则则 V1 V且且V1, 均有均有 p(G V1) |V1|.推论推论 设无向图设无向图G=是半哈密顿图是半哈密顿图, 则则 V1 V且且V1, 均有均有 p(G V1) |V1|+1.4747例例25 25 如右图，若取如右图，若取V1 = =v1, v4，则，则G V1有有3个连通分个连通分支

30、，支， 不是哈密顿图。不是哈密顿图。几点说明几点说明： 定理中的条件是必要条件，可利用该定理判断定理中的条件是必要条件，可利用该定理判断某些图不是哈密顿图某些图不是哈密顿图. 由定理可知由定理可知, Kr,s当当s r+1时不是哈密顿图时不是哈密顿图. 当当r 2时时, Kr,r是哈密顿图是哈密顿图, 而而Kr,r+1是半哈密顿图是半哈密顿图. 例例26 设设G为为n阶无向连通简单图阶无向连通简单图, 若若G中有割点或桥中有割点或桥, 则则G不是哈密顿图不是哈密顿图.4848定理定理(充分条件充分条件) 设设G是是n阶无向简单图阶无向简单图, 若任意两个若任意两个不相邻的顶点的度数之和大于等于不相邻的顶点的度数之和大于等于n 1, 则则G中存中存在哈密顿通路在哈密顿通路. 推论推论：当：当n 3时，若任意两个不相邻的顶点的度数时，若任意两个不相邻的顶点的度数之和大于等于之和大于等于n，则，则G为哈密顿图为哈密顿图. 例例27 某次国际会议某次国际会议8人参加，已知每人至少