离散数学概论课件10

第五章图的基本概念和矩阵表示离散数学概论21.1

基本概念

1.6矩阵表示1.2握手定理1.7路径1.3图的同构和子图1.8图的着色1.4图的操作1.9匹配1.5连通性第五章图的基本概念和矩阵表示3§1基本概念

图(Graph)是由顶点集合和顶点间的一元关系集合(即边的集合或弧的集合)组成的数据结构，通常可以用G(V，E，φ)来表示。其中顶点集合(VertexSet)和边的集合(EdgeSet)分别用V(G)和E(G)表示，φ是从E到V中的有序对或无序对的映射。V(G)中的元素称为顶点(Vertex)，又称结点。用u、v等符号表示；顶点个数称为图的阶(Order)，通常用n表示。E(G)中的元素称为边(Edge)，用e等符号表示；边的个数称为图的边数(Size)，通常用m表示。从边（e）到其相连结的两顶点（u、v）的映射如果是无序的，则这条边可以用无序对（u，v）来表示，这时边e称为无向边，也可以简称为边。4§1基本概念

从边（e）到其相连结的两顶点（u、v）的映射如果是有序的，则这条边一般用有序对<u，v>来表示，这时边e称为有向边或弧，u称为弧e的始点，v称为弧e的终点，u和v统称为e的端点。同时称e关联于u和v，u和v是邻接点。同样的，关联于同一个顶点的两条边，称为邻接边。关联于同一个顶点的一条边，称为自回路，又可称为环，环的方向是不定的。无向边又可称为棱，没有始点和终点。不与任何结点邻接的结点称为弧立结点。每一条边都是有向边的图称为有向图，每一条边都是无向边的图称为无向图。如果在图中一些边是有向边，而另一些边是无向边，则称这个图是混合图。全由孤立结点构成的图称为零图或离散图。若一个图中只含一个孤立结点，则该图称为平凡图。顶点数为n的图称为n阶图，顶点集为空集的图称为空图。5§1基本概念

在有向图中，两结点间(包括结点自身间)若同始点和同终点的边多于一条，则这几条边称为平行边，又称多重边。类似的，在无向图中，两结点间(包括结点自身间)若多于一条边，则称这几条边为平行边或多重边。含有平行边的图称为多重图，不含平行边的称为线图，没有自回路的线图称为简单图。图既无多重边，又无环。[e]可以既表示有向边，又可以表示无向边。两结点u、v间互相平行的边的条数称为边[u,v]的重数。仅有一条边时重数为0，没有边时重数为0。6§1基本概念

7§1基本概念

定理：在任何图中,n个结点的无向完全图Kn的边数为n(n-1)/2，n个结点的有向完全图Kn的边数为n(n-1)。定理：在任何有向完全图中，所有结点入度的平方之和等于所有结点的出度平方之和。定义：给每条边或弧都赋予权的图G=<V,E>称为加权图(weightedgraph)，又称赋权图，记为G=<V,E,W>。对于边e来说，W(e)表示边e的权重(weight)，简称权。V={a,b,c},E={e1,e2,e3},f(a)=3,f(b)=4,f(c)=5,g(e1)=6,g(e2)=7,g(e3)=8。8§1基本概念

在无向图中，顶点v作为边的端点的次数之和为v的度数，简称度，记作d(v)。在有向图中，顶点v作为边的始点的次数之和为v的出度，记为d+(v)。相对的，顶点v作为边的终点的次数之和为v的入度，记为d-(v),度数则是入度和出度之和。图中度数的最大值称为最大度，度数的最小值称为最小度。同时，有向图中入度的最大值称为最大入度，出度的最大值称为最大出度。有向图中度数为1的顶点称为悬挂顶点，它所关联的边称为悬挂边。设图G的顶点集为V={v1,v2,…,vn}，则称(d(v1),d(v2)，…，d(vn))为G的度数序列。同理，有向图还有入度序列和出度序列，分别为(d-(v1),d-(v2)，…，d-(vn))和(d+(v1),d+(v2)，…，d+(vn))。各结点的度数均相同的图称为正则图，各结点的度数均为k时称为k度正则图。9§1基本概念

例：描述下图a)所示的图和图b)所示的多重图。解：对于图(a)：有6个顶点，从而V={P1,P2,P3,P4,P5,P6}有6条边，由此有6个顶点偶，因此E=[{P1,P4},{P1,P6},{P4,P6},{P3,P2},{P3,P5},{P2,P5}]。对于图(b)：有6个顶点，从而V={P1,P2,P3,P4,P5,P6}有8条边(其中有2条是多重边，两条是环)，且由此有8个顶点偶，因此E=[{P1,P4},{P1,P6},{P3,P4},{P3,P4},{P4,P4},{P3,P5},{P6,P6},{P4,P6}]。10§1基本概念

例：判定下列多重图G(V,E)是否是简单图，其中V=｛A,B,C,D｝,且(a)E=[{A,B},{A,C},{A,D},{B,C},{C,D}];(b)E=[{A,B},{B,B},{A,D}];(c)E=[{A,B},{C,D},{A,B},{B,D}];(d)E=[{A,B},{B,C},{C,B},{B,B}];解：简单图既无多重边，又无环。故是简单图。不是简单图。因为{B,B}是环。不是简单图。因为{A,B}和{A,B}是多重边。不是简单图。因为{B,C}和{C,B}是多重边，{B,B}是环。11§1基本概念

例：画出下列多重图G(V,E)的图形，其中V={P1,P2,P3,P4,P5}，且(a)E=[{P2,P4

},{P2,P3},{P3,P5

},{P5,P4

}]；(b)E=[{P1,P1

},{P2,P3},{P2,P4},{P3,P2

},{P4,P1},{P5,P4}]；解：先根据顶点集画出顶点，再连接顶点标明边。其中(a)是图，(b)是多重图，结果如下图所示：12§1基本概念

例：画出一个结点数最少的简单图。(a)使它是3-正则图；(b)使它是5-正则图。解：所求如下图(a)和(b)所示。13§1基本概念

例：画出下图中简单图的补图。解：补图如下图所示：141.1基本概念1.6矩阵表示1.2

握手定理

1.7路径1.3图的同构和子图1.8图的着色1.4图的操作1.9匹配1.5连通性第五章图的基本概念和矩阵表示15§2

握手定理

16§2

握手定理

握手定理及其推论解释了结点数和边数的关系，我们可以根据上面的定理和推论解决很多问题，比如帮助快速判定某序列能否成为图的度数序列，要灵活掌握。17§2

握手定理

例：考虑图G，其中V(G)=｛A,B,C,D｝,E(G)=[{A,B},{B,C},{B,D},{C,D}]。求G的每个顶点的次数和奇偶性。解：计算每个顶点属于的边的条数，得： deg(A)=1，deg(B)=3，deg(C)=2，deg(D)=2。

故C和D是偶度结点，A和B是奇度结点。18§2

握手定理

例：求下图中多重图的每个顶点的次数。解：计算每个顶点属于的边的条数，得： deg(P1)=4，deg(P2)=3，deg(P3)=2，deg(P4)=3，deg(P5)=4。

其中P5处有一个环，所以计算次数时要乘以2。191.1基本概念1.6矩阵表示1.2握手定理1.7路径1.3

图的同构和子图

1.8图的着色1.4图的操作1.9匹配1.5连通性第五章图的基本概念和矩阵表示20§3

图的同构和子图

设G=<V,E>和G’=<V’,E’>分别表示两个图，若存在从V到V’的双射函数φ，使得对任意的结点a、b∈V，[a,b]∈E，当且仅当[φ(a),φ(b)]∈E'，且[a,b]和[φ(a),φ(b)]有相同的重数，就称图G和G'是同构的，记为G≌G′。图的同构可以视作是同一个图的不同表现形式，即同构图除了顶点和边的名称不同外，实际上就是一个图形。21§3

图的同构和子图

目前尚没有一个有效的方法来直接判定两个图同构，在这里我们可以给出一些同构的必要条件：（1） 同构的图结点数相等；（2） 同构的图边数相等；（3） 同构的图度数相同的结点数相等；以上是必要条件但不是充分条件，有满足以上三种条件但不是同构图的情况存在，例如下图：22§3

图的同构和子图

例：证明下图中的两个有向图是同构的。证明：作映射g(a)=4,g(b)=1,g(c)=2,g(d)=3,g(e)=5。在该映射下，边<a,e>,<b,a>,<d,a>,<b,c>,<e,b>,<d,c>,<c,e>,<e,d>分别对应为<4,5>,<1,4>,<3,4>,<1,2>,<5,1>,<3,2>,<2,5>,<5,3>，因此两个有向图同构。23§3

图的同构和子图

例：证明下图中的两个无向图是不同构的。证明：左图中有且只有4个次数为2的，且有两对点相邻接。右图中也有且只有4个次数为2的点，但这4个点互不邻接。因此，两图之间不存在同构映射，因而不同构。24§3

图的同构和子图

设G=<V,E>和G’=<V’,E’>是两个图。

如果V’⊆V且E’⊆E,则称G’是G的子图，记作G’⊆G。

如果G’⊆G且G’⊂G,则称G’是G的真子图。

如果V’=V且G’⊆G,则称G’是G的生成子图。

若子图G'中没有孤立结点，G'由E’唯一确定，则称G'为由边集E'导出的子图。25§3

图的同构和子图

下图展示了图G及其子图：261.1基本概念1.6矩阵表示1.2握手定理1.7路径1.3图的同构和子图1.8图的着色1.4

图的操作

1.9匹配1.5连通性第五章图的基本概念和矩阵表示27§4

图的操作

设图G1=<V1,E1>和图G2=<V2,E2>(1)G1与G2的并,定义为图G3＝<V3,E3>,其中V3=V1∪V2,E3=E1∪E2,记为G3=G1∪G2。(2)G1与G2的交，定义为图G3＝<V3,E3>,其中V3=V1∩V2,E3=E1∩E2,记为G3=G1∩G2。(3)G1与G2的差，定义为图G3＝<V3,E3>,其中E3=E1-E2,V3=(V1-V2)∪{E3中边所关联的顶点},记为G3=G1-G2。(4)G1与G2的环和，定义为图G3＝<V3,E3>,G3=(G1∪G2)-(G1∩G2),记为G3=G1⊕G2。28§4

图的操作

设图G<V,E>，（1）设e∈E，用G-e表示从G中去掉边e得到的图，称为删除e。又设E'E，用G-E'表示从G中删除E'中所有边得到的图，称为删除E'。（2）设v∈V，用G-v表示从G中去掉结点v及v关联的所有边得到的图，称为删除结点v。又设V'⊆V，用G-V'表示从G中删除V'中所有结点及关联的所有边得到的图，称为删除V'。（3）设e＝(u,v)∈E，用G\e表示从G中删除e，将e的两个端点u,v用一个新的结点w代替，使w关联除e外的u和v关联的一切边，称为边e的收缩。一个图G可以收缩为图H，是指H可以从G经过若干次边的收缩而得到。（4）设u,v∈V（u,v可能相邻，也可能不相邻），用G∪(u,v)表示在u,v之间加一条边(u,v)，称为加新边。29§4

图的操作

下图展示了图的一系列操作：30§4

图的操作

例：G图如下所示。求(a)G-A;(b)G-B;(c)G-C;解：图(a)(b)(c)求解如下图所示。31§4

图的操作

例：图G如下图所示，求:G-{A,B};(b)G-{B,C};(c)G-{B,D};(d)G-{C,D};解：只要从图G中删除对应的边即可，结果如下图所示：321.1基本概念1.6矩阵表示1.2握手定理1.7路径1.3图的同构和子图1.8图的着色1.4图的操作1.9匹配1.5连通性第五章图的基本概念和矩阵表示33§5

连通性

给定无向图（或有向图）G=<V,E>，令v0，v1……vm∈V,边(或弧)e0，e1…em∈E，其中vi-1，vi是ei的结点，交替序列v0e1v1e2v2……emvm称为连接v0到vm的链（或路）。v0和vm分别是链的始结点和终结点，而边（或弧）的数目称为链的长度。在图G＝<V，E>中，对∀vi,vj∈V，如果从vi到vj存在道路，则称长度最短的通路为从vi到vj的短程线，从vi到vj的短程线的长度称为vi到vj的距离，记为d(vi,vj)。

34§5

连通性

若通路中的所有边e0，e1……em互不相同，则称此通路为简单通路或一条迹。若回路中的所有边e0，e1……em互不相同，则称此回路为简单回路或一条闭迹；若通路中的所有结点v0，v1……vm互不相同（从而所有边互不相同），则称此通路为基本通路或者初级通路、路径；若回路中除v0=vm外的所有结点v0，v1……vm-1互不相同（从而所有边互不相同），则称此回路为基本回路或者初级回路、圈。基本通路(或基本回路)一定是简单通路(或简单回路)，反之则不一定。

35§5

连通性

在右图中，v1v2v3v4v5是一条4-路径；v1v2v3v4v3是一条4-通道；v1v2v3v4v5v6v3v7是一条7-迹；v1v2v3v4v5v6v3v7v1是一个圈（闭迹）。

36§5

连通性

例：图G如右图所示，判定下列的边序列是否形成通路：（{A,X}，{X,B}，{C,Y}，{X,X}

）；（{A,X}，{X,Y}，{Y,Z}，{Z,A}）；（{X,B}，{B,Y}，{Y,C}）；（{B,Y}，{X,Y}，{A,X}）；解：：若一个边序列的边是这样连接起来的：它的一条的终结点是下一条边的起始点，则这个边序列是通路。(a) 否。边{C,Y}不接在{X,B}后面。(b) 否。图上Y和Z之间没有相连，{Y,Z}不是一条边。(c) 是。(d) 是。因为这个序列可以重新写成（{B,Y}，{Y,X}，{X,A}）。37§5

连通性

例：图G如右图所示，求:(a)从A到Z的所有简单通路；从A到Z的所有迹。解：(a)若从A到Z的一条通路没有顶点是重复的(所以也没有边是重复的)，则它是一条简单通路。有6条简单通路：(A,C,Z),(A,B,C,Z),(A,X,Y,Z),(A,B,X,Y,Z),(A,X,B,C,Z),(A,C，B,X,Y,Z)。(b)若从A到Z的一条通路没有重复的边,则它是一条迹。由(a)的6条简单通路与(A,X,B,A,C,Z),(A,C,B,A,X,Y,Z),(A,B,C,A,X,Y,Z)，(A,B,X,A,C,Z)合在一起共有10条迹。38§5

连通性

设u,v为无向图G＝<V,E>中的两个结点，若u,v之间存在通路，则称结点u,v是连通的，记为u~v。对任意结点u，规定u~u。若无向图G＝<V，E>中任意两个结点都是连通的，则称G是连通图，否则称G是非连通图(或分离图)。无向图G中的每个连通的划分块称为G的一个连通分支，用p(G)表示G中的连通分支个数。设无向图G＝<V,E>（1）若存在结点子集V'V，使得删除V'后，所得子图G-V'的连通分支数与G的连通分支数满足p(G-V')＞p(G)，而删除V'的任何真子集V"后，p(G-V")＝p(G)，则称V'为G的一个点割集。特别地，若点割集中只有一个结点v，则称v为割点。39§5

连通性

（2）若存在边集子集E’E，使得删除E’后，所得子图G-E’的连通分支数与G的连通分支数满足p(G-E’)＞p(G)，而删除E’的任何真子集E”后，p(G-E”)＝p(G)，则称E’为G的一个边割集或简称为割集。特别地，若割集中只有一条边e，则称e为割边或桥，如下图中边cd和边hi。割集有以下特点：1)把该集合的所有边删去将增加连通分图的个数；2)把该集合的任何真子集从G中删去则无此效果。40§5

连通性{e2,e3,e4}是一个割集，{e4,e5}也是一个割集，但{e4,e5,e6}不是割集。41§5

连通性例：图G如下图所示，G有割点么？解：先求解G-A,G-B,G-C,G-X,G-Y,G-Z分别如下图(a)-(f)所示。由上图可知，只有G-B和G-Y是不连通的，所以B和Y是G的割点。42§5

连通性设无向图连通图G＝<V,E>，称(G)＝min{|V||V为G的点割集}为G的点连通度，简称连通度。又若(G)≥k，则称G为k-连通图。规定：完全图Kn的点连通度为n-1，n≥1；非连通图的点连通度为0。设无向图连通图G＝<V,E>，称(G)＝min{|E||E为G的边割集}为G的边连通度。又若(G)≥k，则称G为k边-连通图。规定非连通图的边连通度为0。对任意无向图G＝<V,E>，均有下面不等式成立： (G)≤(G)≤(G)

其中，(G)、(G)和(G)分别为G的点连通度、边连通度和结点的最小度数。43§5

连通性设G＝<V,E>是一个有向图，略去G中所有有向边的方向得无向图G'，如果无向图G'是连通图，则称有向图G是连通图或称为弱连通图，否则称G是非连通图。设图G=<V,E>，其中vi,vj∈V，如果从vi到vj存在一条路径，则称vj从vi可达。我们定义每个结点到其自身是可达的。设有向图G＝<V,E>是连通图，若G中任何一对结点之间至少有一个结点到另一个结点是可达的，则称G是单向连通图；若G中任何一对结点之间都是相互可达的，则称G是强连通图。在有向图G＝<V,E>中，设G’是G的子图，如果G’是强连通的（单向连通的、弱连通的），同时对任意G”G，若G’G”，则G”不是强连通的（单向连通的、弱连通的）。那么称G'为G的强连通分支（单向连通分支、弱连通分支），或称为强分图（单向分图、弱分图）。44§5

连通性例：求G的连通分图，此处V(G)={A,B,C,X,Y,Z}且E(G)=[{A,X},{C,X}];E(G)=[{A,Y},{B,C},{Z,Y},{X,Z}];解：(a)A与C和X连接,B，Y和Z是孤立顶点。

因此{A,C,X},{B},{Y}和{Z}是G的连通分图。(b)A,Y,Z

和X

是连接的，B

和C

是连接的。

因此{A,X,Y,Z}和{B,C}是G的连通分图。45§5

连通性例：求G的连通分图，此处V(G)={A,B,C,P,Q}且E(G)=[{A,C},{B,Q},{P,C},{Q,A}];E(G)=Ø,即空集;解：(a)这里G是连通的，即每一顶点与其余顶点连接。因此G有一个

分图V(G)={A,B,C,P,Q}。(b)由于E(G)是空集，所有的顶点是孤立点，因此{A},{B},{C},{P},{Q}

都是G的连通分图。461.1基本概念1.6矩阵表示1.2握手定理1.7路径1.3图的同构和子图1.8图的着色1.4图的操作1.9匹配1.5连通性第五章图的基本概念和矩阵表示47一、

邻接矩阵二、

可达矩阵三、

关联矩阵四、连通性与矩阵关系§6

矩阵表示48一.邻接矩阵

有向图G=<V,E>，顶点集V=｛v1,v2,……,vn｝，V中的结点按下标由小到大编序，构造n阶矩阵A=(aij)n×n，其中：

m，若存在m条vi到vj直接相连的有向边aij=i,j=1,2,……,n0，若不存在vi到vj直接相连的有向边

则称A为有向图G的邻接矩阵，记为A(G)。

邻接矩阵与结点编序有关，同一个图形结点编序不同得到的邻接矩阵不同，但是表示的都是同一张图。也就是说这些结点不同编序得到的图都是同构的，同时它们的邻接矩阵也是相似的。49一.邻接矩阵

50一.邻接矩阵

51一.邻接矩阵

52一.邻接矩阵

53二.可达矩阵

给定图G=<V,E>,顶点集V=｛v1,v2,……,vn｝，V中的结点按下标由小到

大编序，构造n阶矩阵P=(pij)n×n，其中：

1，若vi到vj可达pij

=i,j=1,2,……,n

0，若vi到vj不可达

则称矩阵P是图G的可达矩阵，记为P(G)。

可达矩阵表明了图中任意两结点间是否至少存在一条链（或路）以及在结点处是否有圈（或回路）。

54二.可达矩阵

55二.可达矩阵

56三.关联矩阵

设G＝<V,E>是一个无环的、至少有一条有向边的有向图，V＝{v1，v2，…，vn}，E＝{e1，e2，…，em}，矩阵M＝(mij)n×m，其中1当ej是vi的出边，mij=-1当ej是vi的入边，0其他，称M为有向图G的关联矩阵。有向图关联矩阵有如下性质：第i行（1≤i≤n）中，1的个数是vi的出度，-1的个数是vi的入度，都等于边数；每列都恰有一个1和一个-1；若第i行全为0，则vi为孤立结点。57三.可达矩阵

58三.可达矩阵

59四.连通性与矩阵关系

连通性与矩阵关系：无向线图G是连通图当且仅当它的可达性矩阵P的所有元素都均为1；有向线图G是强连通图当且仅当它的可达性矩阵P的所有元素都均为1；有向线图G是单向连通图当且仅当它的可达性矩阵P及其转置矩阵PT经布尔运算加后所得矩阵P’＝P∨PT中除对主角元外的其余元素均为1；

有向线图G是弱连通图当且仅当它的邻接矩阵A及其转置矩阵AT经布尔加运算后所得矩阵B＝A∨AT作为邻接矩阵而求出的可达性矩阵P’中所有元素均为1。601.1基本概念1.6矩阵表示1.2握手定理1.7路径1.3图的同构和子图1.8图的着色1.4图的操作1.9匹配1.5连通性第五章图的基本概念和矩阵表示61一、

最短路径二、Dijkstra算法三、Bellman-Ford算法四、SPFA算法五、Floyd算法六、拓扑排序和关键路径§7

路径62一.最短路径

p:v1→v2→…vk

表示v1到vk的一条路径，它的权值为该路径经过的所有边的权值总和，记为w(p)。从u到v的一条路径，使w(p)最小，此时的p就是最短路径。最短路径的权值为δ(u,v)=min{w(p)}，p为从u到v的路径。最短路径可能不存在：

（1）存在负权回路：

存在v1到v6的负权回路，它的权值为-3，如果我们想找从u到v的最短路

径，那么无限循环地走这个负权回路可以使最短路径越来越小，最后达

到负无穷，那么就说明找不到从u到v的最短路径。

（2）不存在从u到v的路径，肯定也不存在最短路径。63二.Dijkstra算法

算法思想：（1）需要指定起点s(即从顶点s开始计算)；（2）引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)；（3）初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。重复该操作，直到遍历完所有顶点。64二.Dijkstra算法

操作步骤：1）初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为”起点s到该顶点的距离”[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]；2）从U中选出”距离最短的顶点k”，并将顶点k加入到S中；同时，从U中移除顶点k；3）更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。

重复步骤2)和3)，直到遍历完所有顶点。65二.Dijkstra算法

例：以下图中a)图G为例，以D点为起点用Dijkstra算法寻找最短路径。S是已计算出最短路径的定点的集合，U是未计算出最短路径的定点的集合，C(3)表示顶点C到起点D的最短距离是3。过程如下：1）选取顶点D。S={D(0)}，U={A(∞),B(∞),C(3),E(4),F(∞),G(∞)}。2）选取顶点C。S={D(0),C(3)}，U={A(∞),B(13),E(4),F(9),G(∞)}。66二.Dijkstra算法

3）选取顶点E。S={D(0),C(3),E(4)}，U={A(∞),B(13),F(6),G(12)}。4）选取顶点F。S={D(0),C(3),E(4),F(6)}，U={A(22),B(13),G(12)}。5）选取顶点G。S={D(0),C(3),E(4),F(6),G(12)}，U={A(22),B(13)}。6）选取顶点B。S={D(0),C(3),E(4),F(6),G(12),B(13)}，U={A(22)}。7）选取顶点A。S={D(0),C(3),E(4),F(6),G(12),B(13),A(22)}。67二.Dijkstra算法

详细过程讲解如下：初始状态：S是已计算出最短路径的顶点集合，U是未计算除最短路径的顶点的集合。1）将顶点D加入到S中。

此时，S={D(0)},U={A(∞),B(∞),C(3),E(4),F(∞),G(∞)}。C(3)表示C到起

点D的距离是3。2）将顶点C加入到S中。

上一步操作之后，U中顶点C到起点D的距离最短；因此，将C加入到S中，同时更

新U中顶点的距离。以顶点F为例，之前F到D的距离为∞；但是将C加入到S之后，

F到D的距离为9=(F,C)+(C,D);

此时，S={D(0),C(3)},U={A(∞),B(13),E(4),F(9),G(∞)}。3）将顶点E加入到S中。

上一步操作之后，U中顶点E到起点D的距离最短；因此，将E加入到S中，同时更

新U中顶点的距离。还是以顶点F为例，之前F到D的距离为9；但是将E加入到S之后，68二.Dijkstra算法

F到D的距离为6=(F,E)+(E,D);

此时，S={D(0),C(3),E(4)},U={A(∞),B(13),F(6),G(12)}。4）将顶点F加入到S中。

此时，S={D(0),C(3),E(4),F(6)},U={A(22),B(13),G(12)}。5）将顶点G加入到S中。

此时，S={D(0),C(3),E(4),F(6),G(12)},U={A(22),B(13)}。6）将顶点B加入到S中。

此时，S={D(0),C(3),E(4),F(6),G(12),B(13)},U={A(22)}。7）将顶点A加入到S中。

此时，S={D(0),C(3),E(4),F(6),G(12),B(13),A(22)}。

起点D到各个顶点的最短距离就计算出来了：A(22)B(13)C(3)D(0)E(4)F(6)G(12)。69二.Dijkstra算法

例：用Dijkstra算法求下图(a)(b)从a到z的最短路径及其长度。解：(a)图中a到z的最短路径长为8，路径为（a,d,i,l,z）。

(b)图中a到z的最短路径长为4，路径为（a,b,g,z）。(a)(b)70三.Bellman-Ford算法

Dijkstra算法是处理单源最短路径的有效算法，但它局限于边的权值非负的情况，若图中出现权值为负的边，Dijkstra算法就会失效，求出的最短路径就可能是错的。这时候，就需要使用其他的算法来求解最短路径，Bellman-Ford算法就是其中最常用的一个。Bellman-Ford算法基本思想为：首先假设源点到所有点的距离为无穷大，然后从任一顶点u出发，遍历其它所有顶点vi，计算从源点到其它顶点vi的距离与从vi到u的距离的和，如果比原来距离小，则更新，遍历完所有的顶点为止，即可求得源点到所有顶点的最短距离。71三.Bellman-Ford算法

Bellman-Ford算法流程如下：1）初始化：给定图G(V,E)（其中V、E分别为图G的顶点集与边集），源点s，数组d[n]记录从源点到结点n的距离。将除起点s外所有顶点的距离数组置无穷大，d[n]=∞,d[s]=0；2）迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离。具体为以下操作循环执行至多n-1次，n为顶点数：对于每一条边e(u,v)，如果d[u]+w(u,v)<d[v]，则另d[v]=d[u]+w(u,v)。w(u,v)为边e(u,v)的权值；若上述操作没有对d[]进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；3）检验负权回路：即检验是否存在权值之和小于0的环路。判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在d[n]中。具体操作为对于每一条边e(u,v)，如果存在d[u]+w(u,v)<d[v]的边，则说明图中存在负环路，即是说该图无法求出单源最短路径。否则数组d[n]中记录的就是源点s到各顶点的最短路径长度。72三.Bellman-Ford算法

先从下面的例子来理解什么是松弛操作：对于下图，假如选择边<3,4>来进行松弛操作，那么就是进行如下两个操作：1）对于点3：d[3]=min(d[3],d[4]+w)。（w代表边的权值，上图省略）2）对于点4：d[4]=min(d[4],d[3]+w)。

这样做的目的是让距离数组d尽量的小，而每一次让d[i]减小的松弛操作，我们便称其松弛成功。我们使用的松弛操作可以是选取一条边，也可以是从一个点a到另一个点b。后者对应的松弛操作为：d[a]=min(d[b],d[a]+w)；从最短路的角度来讲，如果对点3的松弛操作成功，意味着从s到4再从4到3这条路比其他从s到3的路都短，距离数组中的d[3]就是目前起点到点3的最短距离。也就是说每一次成功的松弛操作，都意味着我们发现了一条新的最短路。73三.Bellman-Ford算法

接下来我们以下图为例展示Bellman-Ford算法的执行过程：图中有5个结点，所以要进行四次松弛操作。结点s为源点，距离d值被标记在顶点内。阴影覆盖的边指示了前趋值：如果边(u,v)被阴影覆盖，表示路径里的u结点在v结点前一个。在这个例子中，每一趟按照如下的顺序对边进行松弛：(t,x)，(t.y)，(t,z)，(x,t)，(y,x)，(y,z)，(z,x)，(z,s)，(s,t)，(s,y)。图a展示的是对边进行第一遍操作前的情况，图b到e展示的是每一趟连续对边操作后的情况，e图是最终结果。因为本例子中没有负权回路，所以Bellman-Ford算法在这个例子中返回的是true。74四.SPFA算法

SPFA算法可以看成是Bellman-Ford算法的队列优化版本。正如在前面讲到的，Bellman-Ford算法每一轮用所有边来进行松弛操作可以多确定一个点的最短路径，但是每次都把所有边拿来松弛太浪费了。不难发现，只有那些已经确定了最短路径的点所连出去的边才是有效的，因为新确定的点一定要先通过已知(最短路径的)节点。所以我们只需要把已知节点连出去的边用来松弛就行了，但是问题是我们并不知道哪些点是已知节点，不过我们可以放宽一下条件，找哪些可能是已知节点的点，也就是之前松弛后更新的点，已知节点必然在这些点中，所以SPFA算法的做法就是把每次更新了的点放到队列中记录下来。75四.SPFA算法

我们以右图为例展示SPFA算法的执行过程：初始化：我们先初始化数组dis如下图所示：（除了起点赋值为0外，其他顶点的对应的dis的值都赋予无穷大）此时，我们还要把v1入队列：{v1}现在进入循环，直到队列为空才退出循环。第一次循环：

首先，队首元素出队列，即是v1出队列，然后，对以v1为弧尾的边对应的弧头顶点进行松弛操作，可以发现v1到v3，v5，v6三个顶点的最短路径变短了，更新dis数组的值，得到如下结果：

我们发现v3，v4，v6都被松弛了，而且不在队列中，所以要他们都加入到队列中：{v3，v5，v6}；v1v2v3v4v5v60∞∞∞∞∞dis数组v1v2v3v4v5v60∞10∞30100dis数组76四.SPFA算法

第二次循环：此时，队首元素为v3，v3出队列，然后，对以v3为弧尾的边对应的弧头顶点进行松弛操作，可以发现v1到v4的边，经过v3松弛变短了，所以更新dis数组，得到如下结果：

此时只有v4对应的值被更新了，而且v4不在队列中，则把它加入到队列中：{v5,v6,v4}；第三次循环

此时，队首元素为v5，v5出队列，然后，对以v5为弧尾的边对应的弧头顶点进行松弛操作，发现v1到v4和v6的最短路径，经过v5的松弛都变短了，更新dis的数组，得到如下结果：

我们发现v4、v6对应的值都被更新了，但是他们都在队列中了，所以不用对队列做任何操作。队列值为：{v6，v4}；第四次循环此时，队首元素为v6，v6出队列，然后，对以v6为弧尾的边对应的弧头顶点进行松弛操作，发现v6出度为0，所以我们不用对dis数组做任何操作，其结果和上图一样，队列同样不用做任何操作，它的值为：{v4}；v1v2v3v4v5v60∞106030100dis数组v1v2v3v4v5v60∞10503090dis数组77四.SPFA算法

第五次循环此时，队首元素为v4，v4出队列，然后，对以v4为弧尾的边对应的弧头顶点进行松弛操作，可以发现v1到v6的最短路径，经过v4松弛变短了，所以更新dis数组，得到如下结果：因为v6对应的值被修改了，而且v6也不在队列中，所以我们把v6加入队列，{v6}第六次循环此时，队首元素为v6，v6出队列，然后，对以v6为弧尾的边对应的弧头顶点进行松弛操作，发现v6出度为0，所以我们不用对dis数组做任何操作，其结果和上图一样，队列同样不用做任何操作。所以此时队列为空。队列循环结束，此时我们也得到了v1到各个顶点的最短路径的值了，它就是dis数组各个顶点对应的值，如下图：dis数组v1v2v3v4v5v60∞10503060v1v2v3v4v5v60∞10503060dis数组78五.Floyd算法

算法思路：通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引入两个矩阵：距离矩阵D和路径矩阵P。距离矩阵D中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。路径矩阵P中的元素b[i][j]，表示顶点i到顶点j经过了b[i][j]记录的值所表示的顶点。假设图G中顶点个数为N，则需要对矩阵D和矩阵P进行N次更新。初始时，矩阵D中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞，矩阵P的值为顶点b[i][j]的j的值。接下来开始，对矩阵D进行N次更新。对于每一个顶点k，检查a[i][k]+a[k][j]<a[i][j]是否成立，如果成立，则证明从i到k再到j的路径比i直接到j的路径短，我们便设置a[i][j]=a[i][k]+a[k][j]，b[i][j]=k。这样一来，当我们遍历完所有顶点k，所得的a[i][j]矩阵便是i到j的最短路径的距离。79五.Floyd算法

接下来我们通过下图例子来展示Floyd算法的运算过程：1）我们先初始化两个矩阵，得到下图两个矩阵。D矩阵P矩阵

v1v2v3v4v5v6v7v1∞12∞∞∞1614v212∞10∞∞7∞v3∞10∞356∞v4∞∞3∞4∞∞v5∞∞54∞28v61676∞2∞9v714∞∞∞89∞

v1v2v3v4v5v6v7v11234567v21234567v31234567v41234567v51234567v61234567v7123456780五.Floyd算法

2）以v1为中介，更新两个矩阵：可发现，a[2][1]+a[1][7]<a[2][7]和a[7][1]+a[1][2]<a[7][2]，所以我们只需要矩阵D和矩阵P，结果如下：D矩阵P矩阵通过矩阵P，我发现v2–v7的最短路径是：v2–v1–v7。

v1v2v3v4v5v6v7v1∞12∞∞∞1614v212∞10∞∞726v3∞10∞356∞v4∞∞3∞4∞∞v5∞∞54∞28v61676∞2∞9v71426∞∞89∞

v1v2v3v4v5v6v7v11234567v21234561v31234567v41234567v51234567v61234567v7113456781五.Floyd算法

3）以v2作为中介，来更新我们的两个矩阵，使用同样的原理，扫描整个矩阵，得到下面的结果：D矩阵P矩阵由此可见，Floyd算法每次都会选择一个中介点，然后遍历整个矩阵，查找需要更新的值。相信已经可以看出该算法是如何工作的了，下面还剩下五步，这里就不继续演示下去了。

v1v2v3v4v5v6v7v1∞1222∞∞1614v212∞10∞∞726v32210∞35636v4∞∞3∞4∞∞v5∞∞54∞28v61676∞2∞9v7142636∞89∞

v1v2v3v4v5v6v7v11224567v21234561v32234562v41234567v51234567v61234567v7112456782六.拓扑排序和关键路径

对一个工程或者系统，人们最关心的往往是两个方面的问题：

（1）工程能否顺利进行

对AOV网进行拓扑排序

（2）估算整个工程完成所必须的最短时间

对AOE网求关键路径83六.拓扑排序和关键路径

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网（activityonvertexnetwork）。AOV网中不能出现回路，否则意味着某项活动的开始要以自己的完成作为先决条件，这显然是不成立的。因此判断AOV网能否正常进行即判断它是否存在回路。测试AOV网是否存在回路的方法就是对AOV网进行拓扑排序。设G=(V,E)是一个有向图，V的顶点序列v0,v1,…vn-1当且仅当满足以下条件：若从顶点vi到vj有一条路径，在顶点序列中vi必须存在于vj之前，则称此顶点序列为一个拓扑序列。对一个有向图构造拓扑序列的过程称为拓扑排序。拓扑排序的排序结果很可能是不唯一的。拓扑排序的过程如下：每次输出一个入度为0（即没有前驱）的结点，并删除该点与该点指出的有向边。重复此过程直至全部入度为0的结点被输出，得到的结点输出序列就是拓扑序列。如果所有入度为0的结点都被输出，但图还不为空，说明该有向图中必存在环。84六.拓扑排序和关键路径

接下来我们用右图的例子来展示拓扑排序的过程：由右图可得拓扑排序过程如下：1）入度为0的结点只有V1，所以输出V1，并删除边a1、a2、a3，{V1}。2）入度为0的结点有V2,V3,V4，可以任选一个结点输出，比如先输出V2，并删除边a4，{V1,V2}。3）入度为0的结点有V3,V4，可以任选一个结点输出，比如先输出V3，并删除边a5，{V1,V2,V3}。4）入度为0的结点有V4,V5，可以任选一个结点输出，比如先输出V4，并删除边a6，{V1,V2,V3,V4}。5）入度为0的结点有V5,V6，可以任选一个结点输出，比如先输出V5，并删除边a7、a8，{V1,V2,V3,V4,V5}。6）入度为0的结点有V6,V7，可以任选一个结点输出，比如先输出V6，并删除边a9，{V1,V2,V3,V4,V5,V6}。7）入度为0的结点有V7,V8，可以任选一个结点输出，比如先输出V7，并删除边a10，{V1,V2,V3,V4,V5,V6,V7}。8）入度为0的结点只有V8，输出V8，并删除边a11，{V1,V2,V3,V4,V5,V6,V7,V8}。9）入度为0的结点只有V9，输出V9，全部结点被输出，图为空，拓扑排序完成，最后排序结果为{V1,V2,V3,V4,V5,V6,V7,V8,V9}。本例题答案不唯一，满足拓扑排序的条件即可。85六.拓扑排序和关键路径

AOE网（ActivityOnEdgeNetwork）是指用边表示活动的网，是一个带权的有向无环图。其中顶点表示事件（Event），弧表示活动（Activity），权值表示活动持续的时间。由于整个工程只有一个开始点和一个完成点，在正常的情况（无环）下，网中只有一个入度为零的点（称作源点）和一个出度为零的点（称作汇点）。完成工程的最短时间指的是从源点到汇点的最长路径的长度，而这个长度最长的路径就叫做关键路径。假设开始点是v1，从v1到vi的最长路径长度叫做事件vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。活动ai的最早开始时间通常用e(i)表示。而活动的最迟开始时间l(i)，是指在不推迟整个工程完成的前提下，活动ai最迟必须开始进行的时间。我们把l(i)＝e(i)的活动叫做关键活动。86六.拓扑排序和关键路径

若活动ai由弧<i,j>表示，持续时间记为dut(<i,j>)，则关系如下图所示：活动i的最早开始时间等于事件j的最早发生时间e(i)＝ve(i)活动i的最迟开始时间等于事件k的最迟时间减去活动i的持续时间l(i)＝vl(j)-dut(<i，j>)ve[j]和vl[j]可以采用下面的递推公式计算，需分两步进行：（1）向汇点递推ve(源点)=0；ve(j)=Max{ve(i)+dut(<i,j>)}

公式意义：从指向顶点Vj的弧的活动中取最晚完成的一个活动的完成时

间作为Vj的最早发生时间ve[j]，如右图所示。87六.拓扑排序和关键路径

（2）向源点递推

由上一步的递推，最后总可求出汇点的最早发生时间ve[n]。因汇点就是结束点，最迟发生时间与最早发生时间相同，即vl[n]=ve[n]。从汇点最迟发生现时间vl[n]开始，利用下面公式：vl(汇点)=ve(汇点);vl(i)=Min{vl(j)–dut(<i,j>)}公式意义：由从Vi顶点指出的弧所代表的活动中取需最早开始的一个开始时间作为Vi的最迟发生时间，如下图所示。88六.拓扑排序和关键路径

例：求右图中AOE网的拓扑排序和关键路径。解：由图可得，拓扑排序为V1-V2-V3-V4-V5-V6。

关键路径求解如下：

由上表可知，活动a2、a5、a7的最早开始时间和最迟开始时间相等（e=l），

所以a2、a5、a7为关键活动。故得出关键路径为：V1-V3-V4-V6。顶点vevl活动ell-ev100a1011v234a2000v322a3341v466a4341v567a5220v688a6253

a7660

a867189六.拓扑排序和关键路径

例：求右图中AOE网的关键路径。解：由图可得，关键路径求解如下：由上表可知，活动a1、a4、a7、a8、a10、a11为关键活动，所以关键路径为V1-V2-V5-V7-V9或者V1-V2-V5-V8-V9。901.1基本概念1.6矩阵表示1.2握手定理1.7路径1.3图的同构和子图1.8图的着色1.4图的操作1.9匹配1.5连通性第五章图的基本概念和矩阵表示91一、

对偶图二、

四色猜想三、

平面图面着色四、平面图点着色§8

图的着色92一.对偶图

将平面图G嵌入平面后,通过以下手续(简称D过程):(1)对图G的每个面Di的内部作一顶点且仅作一顶点v*i;(