离散数学第七章图.doc

第七章 图

在自然界和人类社会的实际生活中，用图形来描述和表示某些事物之间的关系既方便又直观。例如用工艺流程图来描述某项工程中各工序之间的先后关系，用网络图来描述某通讯系统中各通讯站之间信息传递关系，用开关电路图来描述IC中各元件电路导线连接关系等等。图论起源于18世纪，它是研究由线连成的点集的理论。一个图中的结点表示对象，两点之间的连线表示两对象之间具有某种特定关系(先后关系、胜负关系、传递关系和连接关系等)。事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟。由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点之间连接与否最重要，而连接线的曲直长短则无关紧要。由此经数学抽象产生了图的概念。研究图的基本概念和性质、图的理论及其应用构成了图论的主要内容。

7.1　图的基本概念
7.1.1图的定义
7.1.1.1无向图
定义7.1.1　设A，B是任意集合。集合{(a,b)|aA且bB}称为A和B的无序积，记为A＆B。
　　在无序积中，两个元素间的顺序是无关紧要的，即(a,b)＝(b,a)。
定义7.1.2　无向图G是一个二元组<V，E>，记作G＝<V，E>，其中V是一个非空有限集合，其元素称为结点(顶点)。E是一个V＆V的多重子集，其元素称为边(无向边)。
　　我们可用平面上的点来表示顶点，两点间的连线表示边，从而将任一个无向图用图形表示出来。
［例7.1.1］　无向图G＝<V，E>，其中V={a，b，c，d，e，f}，E={(a,b)，(a,c)，(a,d)，(b,b)，(b,c)，(b,c)，(b,d)，(c,d)}。
7.1.1.2有向图
定义7.1.3　有向图G是一个二元组<V，E>，记作G＝<V，E>，其中V是一个非空有限集合，其元素称为顶点，E是一个VV的多重子集，其元素称为有向边或弧，简称为边。
注：1)在有向图G＝<V，E>中，若e=〈u，v〉，则称u和v为e的起点和终点；
2)自回路既可看成是有向边又可看成是无向边；
3)去掉有向图中边的方向得到的图称为该有向图的基图。
［例7.1.2］　有向图G＝<V，E>，其中V={a，b，c}，E={<a,a>，<a,a>，<a,b>，<b,c>，<b,c>，<c,b>}。
7.1.1.3相关概念
在无向图或有向图中，
1）有限图与无限图；
2）n阶图；|V|=n;
3) 零图 E=Φ；
4）平凡图（|V|=n ，E=Φ）；
5)对于无向图， 若边e=(u,v)，则称u和v是边 e的端点，称边 e关联于u和v，若u=v，则称此为环，边与顶点的关联次数是0，1，2；至少有一条边相连的两个顶点相邻；至少一个公共顶点的两条边相邻
6)对于有向图， 若边e=<u,v>，则称u和v是边 e的端点，称u是边 e的始点，v是边 e的终点，称u邻接到v。
7)关联于同一个顶点的边称为环（自回路）；若关联于同一对顶点的边多于一条时，称这些边为平行边，平行边的条数称为边的重数；
8)不与任何顶点邻接的顶点称为孤立点；含有平行边的图称为多重图，不含有平行边，也不含环的图称为简单图；

7.1.2顶点的度数，握手定理
定义7.1.4　(1)在无向图G=〈V，E〉中，v∈V。与v关联的边数称为v的度数，记为deg(v)；
(2) 在有向图G=〈V，E〉中，v∈V。以v为始点的边数称为v的出度，记为deg＋(v)；以v为终点的边数称为v的入度，记为deg－(v)；称deg(v)= deg＋(v)+ deg－(v)称为v的度(数)。
［例7.1.3］　求例7.1.1中无向图每个顶点的度数；求例7.1.3中有向图每个顶点的出度、入度和度。
注：若结点有自回路，则结点的度数因此而增加2；若有向图的结点v有自回路，则它的出度和入度分别因此而增加1。孤立结点的度数为0。
定理7.1.1 (Euler握手定理) 在图G=<V，E>中, deg(v)=2|E|。
推论7.1.1 　任何图中度数为奇数的结点为偶数个。
定理7.1.2　在有向图G=<V，E>中有
deg＋(v)= deg－(v)=|E|。
度序列，出度序列，入度序列：
定理7.1.3：度序列可图化的充要条件是度序列之和是偶数。
［例7.1.4］（1）3，2，3，3 5，2，3，1，4，7可图化吗？
（2）一知一个图有10条边，4个3度顶点，其余顶点的度数均小于等于2，问该图至少有几个顶点？

7.1.3子图
定义7.1.5　设图G=<V，E>和G´=<V´，E´>，
（1） 若V´Ｖ，Ｅ´Ｅ，则称Ｇ´是Ｇ的子图，记为G´G；
（2） 若G´G且V´Ｖ或Ｅ´Ｅ，则称Ｇ´是Ｇ的真子图，记为G´G；
（3） 若G´G且V´=V，则称Ｇ´是Ｇ的生成子图；
（4） V´V，V´，以V´为顶点集，以所有端点均在V´中的G的边为边集的图称为由V´诱导出的Ｇ的子图；
（5） E´E，E´，以E´为边集，以E´中的边的端点点为顶点集的图称为由E´诱导出的Ｇ的子图；
［例7.1.5］　求例7.1.1中无向图的子图、生成子图、由边集诱导的子图和由顶点集诱导的子图。

7.1.4完全图、补图和图的同构
定义7.1.6　在无向简单图G=〈V，E〉中，|V|=n。若每对结点都邻接(即每对结点之间都有边)，则称之为无向完全图，记为Kn。
　　类似地，可以定义有向完全图。
［例7.1.6］　K2，K3，K4，K5及2、3、4、5个顶点的有向完全图。
定义7.1.7　 设G=<V，E>是简单图，|V|=n，H=<V，>。若E=且E=E(Kn)，则称图H是G的补图，记为。
G和互为补图。
［例7.1.7］ 求补图。

定义7.1.8　设图G1=<V1，E1>，G2=<V2，E2>。若存在双射f：V1—>V2，满足：u，v∈V1，[u,v]∈E1[f(u),f(v) ]∈E2且[u,v]的重数和[f(u),f(v)]的重数相等 ([u,v]指(u,v)或[u,v])，则称G1和G2同构，记为G1≌G2。
由于一个图是由其顶点集和边集所决定的，而同构的两个图中顶点集之间存在一一对应关系，且这种对应关系保持顶点间的邻接关系及边的重数，故抽象地看，两个同构的图本质上是一样的。
两个图同构的必要条件：
顶点数相等; 边数相等; 所有顶点度数之和相等；度数相同的顶点数相等。
自补图

7.2　通路、回路、图的连通性

7.2.1通路和回路
定义7.2.1　给定图G=〈V，E〉，设v0,v1,…,vn∈V，e1,e2,…,en∈E，顶点和边交替出现的序列v0e1v1e2…en vn称为从顶点v0到vn的通路，v0和vn 分别称为该通路的起点和终点；称通路上的边数为该通路的长度。
当v0和vn相等时，称该通路为回路或圈。
若通路(回路)的所有边都各不相同，则称该通路(回路)为简单通路(回路)；若通路(回路)的所有顶点都各不相同，则称该通路(回路)为初级通路(回路)。
［例7.2.1］求下图的通路、回路、简单通路、简单回路、初级通路、初级回路
每一初级通路(回路)一定是简单通路(回路)；反之则不然。在简单图中，可以用顶点序列来表示通路(回路)，当然在不产生二义性的前提下也可以用边的序列来表示通路(回)路。
定理7.2.1　给定图G=<V，E>，|V|=n，u,vV。若存在一条从u到v的一条通路，则必有一条从u到v的长度不超过n-1的通路。
推论7.2.1　给定图G=<V，E>，|V|=n，u,vV。若存在一条从u到v的一条通路，则必有一条从u到v的长度不超过n-1的初级通路。
定理7.2.2　给定图G=<V，E>，|V|=n，uV。若存在经过u的一条回路，则必有一条经过u的长度不超过n的回路。
注： 在一个具有n 个顶点的图中，
（1）任何初级通路的长度均不大于n-1；
（2）任何初级回路的长度均不大于n。
7.2.2图的连同性
定义7.2.2　给定图G=〈V，E〉，u,vV。若存在从u到v的通路，则称从u到v是可达的或称u可达v。
规定任一个顶点总是可达自身。
定义7.2.3　给定无向图G=〈V，E〉。若G的任何两个顶点是相互可达的，则称G是连通图，否则称G是非连通图。
在无向图G=〈V，E〉中，定义关系R为： u,vV，uRv u可达v。则R是V上的一个等价关系，从而可以决定V的一个划分，我们称每一个由划分块诱导出的G的子图为G的连通分支，用p(G)表示G的连通分支数。
每个顶点在且仅在一个连通分支中。若p(G)＝1，则G是连通图。
［例7.2.2］　给出连通图、非连通图；图的连通分支。

定义7.2.4　给定有向图G=〈V，E〉。对任何两顶点u,vV，
（1）若u和v相互可达，则称G是强连通的；
（2）若u和v至少有一个可达另一个，则称G是单向连通的；
（3）若其基图是连通的，则称G是弱连通的。
［例7.2.3］　给出强连通图、单向连通图和弱连通图。
强连通图 => 单向连通图 => 弱连通图。
定理7.2.3　有向图G是强连通的G中有一回路，它至少通过每个顶点一次。
定义7.2.5　给定图G=〈V，E〉，u,vV。若u可达v，则称从u到v的长度最短的通路为u与v之间的短程线，其长度称为u到v的距离，记为d(u,v)。
7.2.3点割集，割点，边割集，桥
(1)点割集和割点
定义7.2.6设无向图G=〈V，E〉若存在顶点子集V´V，使G删除V´后，所得子图G-V´的连通分支数P(G-V´)>P(G),而删除V´的任何真子集后,P(G-)=P(G),则 V´为G的点割集,如果V´只有一个顶点v,则称v为割点
（2）边割集和桥
定义7.2.7设无向图G=〈V，E〉若存在边子集E´V，使G删除E´后，所得子图G-E´的连通分支数P(G-E´)>P(G),而删除E´的任何真子集后,P(G-)=P(G),则 E´为G的边割集,如果E´只有一个顶点e,则称e为桥.

7.3　图的矩阵表示
7.3.1无向图的关联矩阵
7.3.1　设有向图G=<V，E>，V={v1，v2，…，vn}，E={e1,e2,…,em},则nm阶方阵A=(aij)称为G的关联矩阵，记为M(G)=(mij),其中mij为vi与边ej 关联的次数(0,1,2)。
(1)M的每列元素之和等于2;
(2)M的第i行元素之和等于d(vi);
(3) M的所有元素之和2m;
(4) 若M的第i行元素之和等于0,则vi是孤立点;
7.3.1有向图的关联矩阵
定义7.3.2设无环有向图G=<V，E>，V={v1，v2，…，vn}，E={e1,e2,…,em},则nm阶矩阵A=(aij)称为G的关联矩阵，记为M(G)=(mij),其中

mij=
(1)M的每列元素之和等于0,M的所有元素之和0.
(2) M的所有值为1元素之和=值为-1元素之和=m.
7.3.3有向图的邻接矩阵
定义7.3.3　设有向图G=<V，E>，V={v1，v2，…，vn}，则n阶方阵A=(aij)称为G的邻接矩阵，其中aij为vi邻接vj 的边数。
在不考虑结点编序的情形下，图的邻接矩阵是唯一的；一个邻接矩阵可以完全确定一个有向图。在一个简单有向图G中,
deg+(vi)=aij=第行中元素的和 deg-(vi)=第i列中元素的和=akj
［例7.3.1］　求下图的邻接矩阵。
定理7.3.1　设A有向图G=<V，E>的邻接矩阵，V={v1，v2，…，vn}，则Ak＝()的第i行第j列元素等于从vi到vj长为k的通路数，等于经过vi长为k的回路数。
［例7.3.2］　求下图的顶点b到其他顶点长为3的通路数。　
7.3.4有向图的可达矩阵
定义7.3.4　设有向图G=<V，E>，V={v1，v2，…，vn}，则n阶方阵P=(pij)称为G的可达矩阵，其中
pij=
可达矩阵的元素的值表明图中任两个顶点间是否存在通路，以及经过某个结点是否存在回路。
若记B＝A＋A1＋…An-1=(bij)nn，则对i,j=1,2,…,n且ij，若 bij 0，则pij=1，否则 pij=0。pii=1，i=1,2,…,n。
［例7.3.3］　求下图的可达矩阵。
类似地，我们可以定义无向图的邻接矩阵和可达矩阵。无向图的邻接矩阵和可达矩阵一定是对称矩阵。
7.4　最短路径和关键路径
7.4.1赋权图和最短通路问题
定义7.4.1　对于有向图或无向图，给每一条边都赋予权(正实数)的图称为赋权图，记为G=<V，E，W>，称W(e)=Wij为边e的权, 称W(G)=为图G的权。
　　在赋权图中，通路的边的权权重之和叫通路的权重。
7.4.2最短路经
单源点的最短路径问题：给定带权有向图（或无向）G＝<V，E，W>和源点v∈V，求从v0到G中其余各顶点的最短路径。
问题解决算法。即由迪杰斯特拉（Dijkstra）提出的一个按路径长度递增的次序产生最短路径的算法。该算法的基本思想是：设置两个顶点的集合S和T＝V－S，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。初始状态时，集合S是空集，从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都要修改v0到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。此过程不断重复，直到集合T的顶点全部加入到S中为止。
Dijkstra算法的实现。
（1）S为已找到从v0出发的最短路径的终点的集合，它的初始状态为空集，T=V-S,。引进一个辅助向量D，它的每个分量D[i] 表示始点v0到每个终点vi 的最短路径的长度。它的初态为：若从v0到vi有弧（边），则D[i]为弧上的权值；否则置 D[i]为∞。
(2)顶点选取，D[u]=Min{D[i]| vi∈T}, S=S+{ vu }T=T-{vu};
（3）修改D[j] D[j]=Min{D[j], D[u]+Wuj } Vj∈V-S
其中，D[i] 或者弧（v, vj）上的权值，或者是D[u]和弧（Vu, Vj）上的权值之和。
(4)重复操作⑵、⑶共n-1次。由此求得从v 到图上其余各顶点的最短路径
［例7.4.1］　求下列赋权图中v1到其他顶点的距离。

7.4.3关键路径
若在带权的有向图中，以顶点表示事件，以有向边表示活动，边上的权值表
示活动的开销（如该活动持续的时间），则此带权的有向图称为AOE网(PERT图)。
利用AOE网进行工程管理时要需解决的主要问题是：
（1） 计算完成整个工程的最短路径。
（2）确定关键路径，以找出哪些活动是影响工程进度的关键。
3. 关键路径的确定
后继元集：
前导元集
为了在AOE网中找出关键路径，需要定义几个参量，并且说明其计算方法。
（1）事件的最早发生时间TE[Vi]
TE[Vi]是指从源点到顶点的最大路径长度代表的时间。这个时间决定了所有
从顶点发出的有向边所代表的活动能够开工的最早时间。
计算vk发生的最早时间的方法如下：
TE[Vl]=0
TE[Vi]=max{TE[Vj]+Wji,}。
（2）事件的最迟发生时间TL[Vi]
计算vk发生的最早时间的方法如下：
TL[Vn]=最长路经长度
TL[Vi]=min{TL[Vj]-Wij,}。
（3缓冲时间
ES(Vi)=TL(Vi)-TE(Vi)
［例7.4.2］求下列PERT图得关键路径

9