第七图的基本概念演示文稿

第七图的基本概念演示文稿当前1页，总共102页。优选第七图的基本概念当前2页，总共102页。图论的内容十分丰富,是一门交叉性很强、应用很广泛的学科。计算机科学、网络理论、信息论、运筹学、语言学、物理、化学等都以图作为工具,来解决理论问题和实际问题。离散数学研究的图是不同于几何图形、机械图形的另一种数学结构,不关心图中顶点的位置、边的长短和形状,只关心顶点与边的联结关系。当前3页，总共102页。目录7.1无向图及有向图7.2通路、回路、图的连通性7.3图的矩阵表示7.4最短路径问题及关键路径

当前4页，总共102页。7.1无向图及有向图设A,B为两集合,称

{{a,b}｜a∈A∧b∈B}为A与B的无序积,记作A＆B．将无序对{a,b}记作(a,b).当前5页，总共102页。定义7.1

一个无向图G是一个二元组<V,E>,即G＝<V,E>,其中,(1)V是一个非空的集合,称为G的顶点集,V中元素称为顶点或结点；

(2)E是无序积V＆V的一个多重子集,称E为G的边集,E中元素称为无向边或简称边.无向图元素可重复出现的集合为多重集当前6页，总共102页。例如：G=<V,E>,V={v1,v2,v3,v4,v5},E={(v1,v2),(v2,v2),(v2,v3),(v1,v3),(v1,v3),(v1,v4)}G的图形为：e5v5v4v3v2v1e4e3e2e1e6当前7页，总共102页。有向图定义7.2一个有向图D是一个二元组<V,E>,即D＝<V,E>,其中,(1)V同无向图中的顶点集；

(2)E是卡氏积的多重子集,其元素称为有向边,也简称边.有时用V(D),E(D)分别表示图D的顶点集和边集。当前8页，总共102页。例如：D=<V,E>,V={v1,v2,v3,v4,v5},E={<v1,v1>,<v3,v2>,<v3,v2>,<v3,v4>,<v2,v4>,<v4,v5>,<v5,v4>,<v1,v2>}G的图形为：e5v5v4v3v2v1e4e3e2e1e6e7e8当前9页，总共102页。设G＝<V,E>为一无向图或有向图

(1)若V,E都是有穷集合,则称G是有限图.(2)若｜V｜＝n,则称G为n阶图．

(3)若E＝,则称G为零图．特别是,若此时又有｜V｜＝1,则称G为平凡图.5阶图零图平凡图当前10页，总共102页。定义7.3设ek＝(vi,vj)为无向图G＝<V,E>中的一条边,称vi,vj为ek的端点,ek与vi(或vj)是彼此关联的.无边关联的顶点称为孤立点.若一条边所关联的两个顶点重合,则称此边为环.e5v5v4v3v2v1e4e3e2e1e6当前11页，总共102页。ek与vi(或vj)的关联次数1vi(vj)是ek的端点且vi≠vj,2vi(vj)是ek的端点且vi＝vj,0vi(vj)不是ek的端点e5v5v4v3v2v1e4e3e2e1e6当前12页，总共102页。定义7.4设无向图G=<V,E>,vi,vj∈V,ek,el∈E.(1)若存在一条边e以vi、vj为端点,即e=(vi,vj),则称vi,vj是彼此相邻的,简称相邻的．(2)若ek,el至少有一个公共端点,则称ek,el是彼此相邻的,简称相邻的．e5v5v4v3v2v1e4e3e2e1e6当前13页，总共102页。对有向图若ek＝〈vi,vj〉,除称vi,vj是ek的端点外,还称vi是ek的始点,vj是ek的终点,vi邻接到vj,vj邻接于vi.e5v5v4v3v2v1e4e3e2e1e6e7e8当前14页，总共102页。定义7.5设G＝<V,E>为一无向图,vi∈V,称vi作为边的端点的次数之和为vi的度数,简称度,记作d(vi).称度数为1的顶点为悬挂顶点,它所对应的边为悬挂边.v1v2v5v4v3d(vi)=?当前15页，总共102页。设D＝<V,E>为一有向图,vj∈V,称vj作为边的始点的次数之和,为vj的出度,记作d+(vj)；称vj作为边的终点的次数之和,为vj的入度,记作d-(vj)；称vj作为边的端点的次数之和,为vj的度数,简称度,记作d(vj).显然d(vj)＝d+(vj)＋d-(vj).当前16页，总共102页。d(v1)＝3，d+(v1)＝2，d-(v1)＝1；d(v2)＝3，d+(v2)＝2，d-(v2)＝1；d(v3)＝5，d+(v3)＝2，d-(v3)＝3；d(v4)＝d+(v4)＝d-(v4)＝0；d(v5)＝1，d+(v5)＝0，d-(v5)＝1；其中，v5是悬挂结点，<v1,v5>为悬挂边。例v5v1v2v3v4当前17页，总共102页。对于图G＝<V,E>,记Δ(G)＝max{d(v)｜v∈V},(G)＝min{d(v)｜v∈V},分别称为G的最大度和最小度.v1v2v5v4v3Δ＝4，＝0。当前18页，总共102页。若D＝〈V,E〉是有向图,除了Δ(D),(D)外,还有最大出度、最大入度、最小出度、最小入度,分别定义为v5v4v3v2v1当前19页，总共102页。定理7.1（握手定理）设图G＝<V,E>为无向图或有向图,V＝{v1,v2,...,vn},|E|=m(m为边数),则推论任何图(无向的或有向的)中,度为奇数的顶点个数为偶数.当前20页，总共102页。定理7.2设有向图D＝<V,E>,V＝{v1,v2,...,vn},｜E｜＝m,则设V＝{v1,v2,...,vn}为图G的顶点集,称(d(v1),d(v2),...,d(vn))为G的度数序列.当前21页，总共102页。例v1v2v5v4v3度数序列（4，4，3，1，0）度数序列（3，4，3，4，2）v5v4v3v2v1当前22页，总共102页。

(1)(3,3,2,3),(5,2,3,1,4)能成为图的度数序列吗？为什么？答：不能，由握手定理易知。

(2)已知图G中有10条边,4个3度顶点,其余顶点的度数均小于等于2.问G中至少有多少个顶点？为什么？答：至少有8个顶点。例当前23页，总共102页。定义7.6在无向图中,关联一对顶点的无向边如果多于1条,称这些边为平行边.平行边的条数称为重数.在有向图中,关联一对顶点的有向边如果多于1条,且它们的始点与终点相同,则称这些边为有向平行边,简称平行边.含平行边的图称为多重图.既不含平行边,也不含环的图称为简单图.当前24页，总共102页。e5v5v4v3v2v1e4e3e2e1e6

e4与e5是平行边

e3与e4是平行边

e7与e8不是平行边e5v5v4v3v2v1e4e3e2e1e6e7e8当前25页，总共102页。定义7.7设G=<V,E>是n阶无向简单图,若G中任何顶点都与其余的n-1个顶点相邻,则称G为n阶无向完全图,记作Kn.

设D=<V,E>为n阶有向简单图,若对于任意的顶点u,v∈V(u≠v),既有有向边<u,v>,又有<v,u>,则称D是n阶有向完全图.注：Kn均指无向完全图.当前26页，总共102页。图(1)中所示为K4,(2)所示为K5,(3)所示为3阶有向完全图.例(1)(2)(3)当前27页，总共102页。定义7.8设G=<V,E>,G'=<V',E'>是两个图.若V'V,且E'E,则称G'是G的子图,G是G'的母图,记做G'G.若G'G且G'≠G(即V'V或E'E),则G'是G的真子图.当前28页，总共102页。若G'G且V'=V则称G'是G的生成子图.设V1V,且V1≠,以V1为顶点集,以两端点均在V1中的全体边为边集的G的子图,称为V1导出的导出子图.

设E1

E,且E1≠,以E1为边集,以E1中关联的顶点的全体为顶点集的G的子图称为E1导出的导出子图.当前29页，总共102页。例下图给出了图G以及它的真子图G'和生成子图G''。G'是结点集{v1,v2,v4,v5,v6}的导出子图。当前30页，总共102页。v1v2v3v4e4e5e1e2e3v1v2v3v4e4e1e3v1v2e4e5v1

v2v3e4e1e2e3v1

v2v3e1e3v1v2e1例(1)(2)(3)(6)(5)(4)当前31页，总共102页。定义7.9设G=<V,E>是n阶无向简单图.以V为顶点集,以所有能使G成为完全图Kn的添加边组成的集合为边集的图,称为G相对于完全图Kn的补图,简称G的补图,记作G.

有向简单图的补图可类似定义.当前32页，总共102页。例互补互补当前33页，总共102页。观察下列图有何特点？图(a)、图(b)、图(c)和图(d)所表示的图形实际上都是一样的。bdcdcbadcbadcbaa图(a)图(b)图(c)图(d)当前34页，总共102页。定义7.10设两个无向图G1=<V1,E1>,G2=<V2,E2>,如果存在双射函数：V1→V2,使得对于任意的e=(vi,vj)∈E1当且仅当e'=((vi),(vj))∈E2,并且e与e'的重数相同,则称G1与G2是同构的,记作G1≌G2.当前35页，总共102页。(1)≌(2),顶点之间的对应关系为av1,bv2,cv3,dv4,ev5.当前36页，总共102页。(a)≌(b)≌(c)(a)所示图称为彼德森图.(a)(b)(c)1、顶点个数相同2、边的条数相同3、度数相同的结点数相同两图同构当前37页，总共102页。例(1)画出4个顶点3条边的所有可能非同构的无向简单图；

(1)(2)(3)当前38页，总共102页。(2)画出3个顶点2条边的所有可能非同构的有向简单图.(1)(2)(3)(4)当前39页，总共102页。7.2通路、回路、图的连通性定义7.11给定图G＝<V,E>.设G中顶点和边的交替序列为Γ＝v0e1v1e2…elvl,若Γ满足如下条件:vi-1和vi是ei的端点(在G是有向图时,要求vi-1是ei的始点,vi是ei的终点),i＝1,2,…,l,则称Γ为顶点v0到vl的通路.v0和vl分别称为此通路的起点和终点,Γ中边的数目l称为Γ的长度.

当v0＝vl时,此通路称为回路.当前40页，总共102页。若Γ中的所有边e1,e2,···,el互不相同,则称Γ为简单通路或一条迹.若回路中的所有边互不相同,称此回路为简单回路或一条闭迹.若通路的所有顶点v0,v1···,vl互不相同(从而所有边互不相同),则称此通路为初级通路或一条路径.若回路中,除v0＝vl外,其余顶点各不相同,所有边也各不相同,则称此回路为初级回路或圈.当前41页，总共102页。有边重复出现的通路称为复杂通路,有边重复出现的回路称为复杂回路.由定义可知,初级通路(回路)是简单通路(回路),但反之不真.注：上述定义既适合无向图，也适合有向图。当前42页，总共102页。例v1v0v4v2v3v5v8v6v7v1v0v4v2v3v1v0v4v2v3v1v0v4v2v3v5v8v6v7(1)为v0到v4的长为4的初级通路(2)为v0到v4的长为4的初级通路(3)为v0到v8的长为8的简单通路(4)为v0到v8的长为8的简单通路当前43页，总共102页。定理7.3在一个n阶图中,若从顶点vi到vj(vi≠vj)存在通路,则从vi到vj存在长度小于等于n-1的通路.推论在一个n阶图中,若从顶点vi到vj(vi≠vj)存在通路,则从vi到vj存在长度小于等于n-1的初级通路.当前44页，总共102页。定理7.4在一个n阶图中,如果存在vi到自身的回路,则从vi到自身存在长度小于等于n的回路.推论在一个n阶图中,如果vi到自身存在一条简单回路,则从vi到自身存在长度小于等于n的初级回路.当前45页，总共102页。定义7.12在一个无向图G中,若从顶点vi到vj存在通路(当然从vj到vi也存在通路),则称vi与vj是连通的.规定vi到自身总是连通的.

在一个有向图D中,若从顶点vi到vj存在通路,则称vi可达vj.规定vi到自身总是可达的.当前46页，总共102页。短程线(无向图)设vi,vj为无向图G中的任意两点,若vi与vj是连通的,则称vi与vj之间长度最短的通路为vi与vj之间的短程线,短程线的长度称为vi与vj之间的距离,记作d(vi,vj).短程线(有向图)设vi,vj为有向图D中任意两点,若vi可达vj,则称从vi到vj长度最短的通路为vi到vj的短程线,短程线的长度称为vi到vj的距离,记作d<vi,vj>.当前47页，总共102页。性质若vi不可达vj,规定d<vi,vj>＝∞.d<vi,vj>具有下面性质:(1)d<vi,vj>

≥0,当vi＝vj时,等号成立.(2)满足三角不等式,即

d<vi,vj>+d<vj,vk>≥d<vi,vk>.在无向图中,还有对称性,即

d(vi,vj)＝d(vj,vi).当前48页，总共102页。连通图(无向图)定义7.13若无向图G是平凡图,或G中任意两顶点都是连通的,则称G是连通图;否则,称G是非连通图.无向图中,顶点之间的连通关系是等价关系.设G为一个无向图,R是G中顶点之间的连通关系,按着R可将V(G)划分成k(k≥1)个等价类,记成V1,V2,···,Vk,由它们导出的导出子图G[V1],G[V2],…,G[Vk]称为G的连通分支,其个数记为p(G).当前49页，总共102页。G1是连通图，p(G1)＝1；G2是非连通图，且p(G2)＝3。G1G2例当前50页，总共102页。连通图(有向图)定义7.14设D是一个有向图,如果略去D中各有向边的方向后所得无向图G是连通图,则称D是连通图,或称D是弱连通图.若D中任意两顶点至少一个可达另一个,则称D是单向连通图.若D中任何一对顶点都是相互可达的,则称D是强连通图．当前51页，总共102页。例图a为弱连通图；图b为单向连通图；图c为强连通图。图a图b图c当前52页，总共102页。定义7.15设无向图G＝<V,E>,若存在顶点子集V'V,使G删除V'将V'中顶点及其关联的边都删除)后,所得子图G－V'的连通分支数与G的连通分支数满足

p(G-V')＞p(G),而删除V'的任何真子集V''后,p(G-V'')＝p(G),则称V'为G的一个点割集.若点割集中只有一个顶点v,则称v为割点.当前53页，总共102页。若存在边集子集E'E,使G删除E'(将E'中的边从G中全删除)后,所得子图的连通分支数与G的连通分支数满足p(G-E')＞p(G),而删除E'的任何真子集E''后,p(G-E'')＝p(G),则称E'是G的一个边割集.若边割集中只有一条边e,则称e为割边或桥.当前54页，总共102页。{v2,v7}，{v3}，{v4}为点割集，{v3}，{v4}为割点{e1,e2}，{e1,e3,e4}，{e6}，{e7,e8}，{e2,e3,e4}等都是割集，其中e6是桥。v5e8v6v7v1v4v2v3e1e2e3e4e5e6e7e9例当前55页，总共102页。本节概念:无向图、有向图、n阶图、零图、平凡图、彼此关联、相邻、度d(vi)、出度d+(vj)、入度d-(vj)、握手定理及其推论、度数序列、简单图、n阶无向完全图、子图、母图、生成子图、导出子图、补图、同构、通路、回路、连通图、点割集、边割集当前56页，总共102页。7.3图的矩阵表示

无向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵有向图的可达矩阵

当前57页，总共102页。无向图的关联矩阵设无向图G＝<V,E>,V＝{v1,v2,···,vn},E＝{e1,e2,···,em},令mij为顶点vi与边ej的关联次数,则称(mij)n×m为G的关联矩阵,记为M(G)mij0(vi与ej无关),1(vi与ej关联1次),

(vi与ej关联2次,

即ej是以vi为端点的环)．当前58页，总共102页。例e2v4v2v3v1e3e4e1e5当前59页，总共102页。关联矩阵M(G)的性质当前60页，总共102页。当前61页，总共102页。有向图的关联矩阵要求有向图D中无环存在.设D＝<V,E>,V＝{v1,v2,···,vn},E＝{e1,e2,···em},令则称(mij)n×m为D的关联矩阵，记作M(D).当前62页，总共102页。v4v3v2v1e1e2e3e4e5例当前63页，总共102页。关联矩阵M(D)的性质当前64页，总共102页。有向图的邻接矩阵设有向图D＝<V,E>.V={v1,v2,···,vn},|E|＝m.令aij

(1)

为vi邻接到vj的边的条数,称(aij

(1))m×n为D的邻接矩阵,记作A(D).当前65页，总共102页。v4v3v2v1例当前66页，总共102页。邻接矩阵A(D)的性质当前67页，总共102页。(3)为D中边的总数,也可看成D中长度为1的通路总数,而为D中环的个数,即D中长度为1的回路总数.

当前68页，总共102页。考虑Al(D)(简记Al),=

这里Al=()n×n(l≥2),则为顶点vi到vj长度为l的通路数,为它到自身长度为l的回路数.Al中所有元素之和为D中长度为l的通路数,而Al中对角线上元素之和为D中始于(终于)各顶点的长度为l的回路数.当前69页，总共102页。在图中,计算A2,A3,A4如下:v4v3v2v1当前70页，总共102页。定理7.5设A为有向图D的邻接矩阵,V=｛v1,v2…,vn},则Al(l≥1)中元素为vi到vj长度为l的通路数,为D中长度为l的通路总数,其中为D中长度为l的回路数.当前71页，总共102页。推论设Br=A+A2+…+Ar(r≥1),则Br中元素为D中vi到vj长度小于等于r的通路数,为D中长度小于等于r的通路总数,其中为D中长度小于等于r的回路总数.若再令矩阵

B1=A,B2=A+A2,……Br=A+A2+…+Ar,当前72页，总共102页。有向图的可达矩阵

设D=<V,E>为一有向,V={v1,v2,…,vn},令

pii=1,i=1,2,…,n.称(pij)n×n为D的可达矩阵,记作P(D),简记P.当前73页，总共102页。v4v3v2v1P=例当前74页，总共102页。P中元素可如下确定:

于是由D的邻接矩阵可求可达矩阵.当前75页，总共102页。7.4最短路径及关键路径

1.最短路径问题

2.关键路径问题当前76页，总共102页。权、带权图对于有向图或无向图G的每条边附加一个实数w(e)，则称w(e)为边e上的权.G连同附加在各边上的实数称为带权图.常记带权图为G=<V,E,W>.当前77页，总共102页。设G1是带权图G的子图,称为G1的权,记作W(G1).当然,W(G)是G的权.当无向边e=(vi,vj)或有向边e=<vi,vj>时,w(e)也记为wij.E(G1)当前78页，总共102页。最短路径问题

设带权图G=<V,E,W>.G中每条边带的权均大于等于0.u,v为G中任意两个顶点,从u到v的所有通路中带权最小的通路称为u到v的最短路径.设G=<V,E,W>是n阶简单带权图,wij≥0.若顶点vi与vj不相邻,令wij=∞.求G中顶点v1到其余各顶点的最短路径.当前79页，总共102页。路径长度的的具体含义取决于边上权值所代表的意义。

【例】交通网络中的带权图求最短路径的问题。

（1）两地之间是否有路相通?

（2）在有多条通路的情况下，哪一条最短?

其中，交通网络可以用带权图表示：图中顶点表示城镇，边表示两个城镇之间的道路，边上的权值可表示两城镇间的距离，交通费用或途中所需的时间等等。

当前80页，总共102页。当前81页，总共102页。(1)设为顶点v1到顶点vi最短路径的权,若顶点vi获得了标号,称vi在第r步获得了p标号(永久性标号),其中,r≥0.

(2)设为v1到vj的最短路径权的上界,若vj获得,在第r步获得t标号(临时性标号),r≥0.若干定义：当前82页，总共102页。(3)设Pr={v|v已获得p标号}为第r步通过集,r≥0.(4)设Tr=V-Pr为第r步未通过集,r≥0.当前83页，总共102页。Dijkstra(标号法）的算法：开始,r←0,v1获p标号:=0,P0={v1},T0=V-{v1}.vj(j≠1)的t标号:=w1j.

①求下一个p标号顶点.

设,将标在相应顶点vi处,表明vi获得p标号.修改通过集和未通过集:Pr=Pr-1∪{vi},Tr=Tr-1-{vi}.,

查Tr:若Tr=,则算法结束,否则转②.当前84页，总共102页。②修改Tr中各顶点的t标号:

是刚刚获得标号顶点的p标号.令r←r+1,转①.当前85页，总共102页。求图中顶点v0与v5的最短路径.

例解:可以将计算过程用一张表表示出来(见下页表)31v5v3v2v154712v02v46当前86页，总共102页。31v5v3v2v154712v0

2v46

vi

Kv0v1v2v3v4v5012345011/v0433/v1∞8877/v4∞644/v2∞∞

∞1099/v3013749当前87页，总共102页。由表可知,v5与v3相邻,v3与v4相邻,v4与v2相邻,v2与v1相邻,v1与v0相邻.这样从v5往前追踪,得v0到v5的最短路径为

Γ=v0v1v2v4v3v5.W(Γ)=9.

31v5v3v2v154712v02v46当前88页，总共102页。设D=<V,E>为一个有向图,v∈V,称为v的后继元集;为v的先驱元集.2.关键路径问题当前89页，总共102页。（1）PERT图（计划评审技术图）设D=<V,E>是n阶有向带权图,满足:1)D是简单图;2)D中无回路;3)有一个顶点入度为0,称此顶点为发点;有一个顶点出度为0,称此顶点为收点;4)记边<vi,vj>带的权为wij;它常表示时间;则称D为PERT图.当前90页，总共102页。通常把计划、施工过程、生产流程、程序流程的都当成一个工程。除了很小的工程外、一般都把工程分为若干个叫做“活动”的子工程。完成了这些“活动”的子工程，这个工程就可以完成了。

通常我们用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边

<vi,vj>表示活动vi必须先于活动vj进行。

这种的有向图叫做用边表示活动的网络，简称AOE（activeonedges）网络。

当前91页，总共102页。AOE网络在某些工程估算方面非常有用。他可以使人们了解：

（1）：研究某个工程至少需要多少时间？

（2）：那些活动是影响工程进度的关键？

在AOE网络中，有些活动可以并行的进行。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成整个工程所需的时间取决于从发点到收点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度就叫做关键路径（criticalpath）。当前92页，总共102页。

1956年，美国杜邦公司提出关键路径法，并于1957年首先用于1000万美圆化工厂建设，工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中，节省了100万美圆。

案例当前93页，总共102页。自发点(记为v1)开始沿最长路径到达vi所需要的时间,称为vi的最早完成时间,记作

TE(vi),i=1,2,…,n.vi(i≠1)的最早完成时间可按如下公式计算:

收点vn的最早完成时间TE(vn)就是从v1到vn的最长路径的权.（2）最早完成时间当前94页，总共102页。在保证收点vn的最早完成时间不增加的条件下,自v1最迟到达vi的时间称为vi的最晚完成时间,记作TL(vi).TL(vn)=TE(vn).i≠n时,vi的最晚完成时间由下面公式计算:

（3）最晚完成时间当前95页，总共102页。称TL(vi)-TE(vi)为vi的缓冲时间,记作

ES(vi)=