离散数学图的基本概论

离散数学图的基本概论第一页，共七十八页，编辑于2023年，星期日计算机科学广泛应用于运筹学，信息论，控制论，网络理论，化学生物学，物理学。原因在于这些学科的许多实际问题和理论问题可以概括为图论。第八、九章介绍与计算机科学关系密切的图论内容及其在实际中的应用。第二页，共七十八页，编辑于2023年，星期日8.1无向图及有向图称{{a,b}|aAbB}为A与B的无序积，记作：A&B。习惯上，无序对{a,b}改记成(a,b)有序组(a,b)均用<a,b>无序积：设A，B为二集合，一、基本图类及相关概念1.无向图第三页，共七十八页，编辑于2023年，星期日无向图：无向图G是一个二元组<V,E>，其中(1)V是一个非空集–––顶点集V(G)，每个元素为顶点或结点；(2)E是无序积V&V的可重子集(元素可重复出现)，E–––边集E(G)，E中元素称为无向边。第四页，共七十八页，编辑于2023年，星期日v4实际中，图是画出来的，画法：用小圆圈表示V中的每一个元素，如果(a,b)E，则在顶点a与b之间连线段。如：adcbe1e1e2e3e4e5e6e1e2e3e4e5e6v1v2v3v5第五页，共七十八页，编辑于2023年，星期日有向图：有向图D是一个二元组<V,E>，其中(1)V是非空集–––顶点集V(D)(2)E是笛卡尔积VV的可重子集，其元素为有向边实际中，画法同无向图，只是要根据E中元素的次序，由第一元素用方向线段指向第二元素。2.有向图第六页，共七十八页，编辑于2023年，星期日有限图：V，E均为有穷集合零图：E

平凡图：E

且|V|=1(n,m)图：|V|=n

且|E|=m顶与边关联：如果ek=(vi,vj)E，称ek与vi关联，或ek与vj关联。3.相关概念第七页，共七十八页，编辑于2023年，星期日顶与顶相邻：如果ek=(vi,vj)E，称vi与vj相邻；环：ek=<vi,vj>中，若vi=vj，则ek称为环。边与边相邻：如果ek和ei至少有一个公共顶点关联，则称ek与ei相邻。若ek为有向边，则称vi邻接到vj,vj邻接于vi

。第八页，共七十八页，编辑于2023年，星期日孤立点：无边关联的顶点。平行边：无向图中，关联一对结点的无向边多于一条，平行边的条数为重数；多重图：包含平行边的图。有向图中，关联一对顶点的无向边多于一条，且始、终点相同。简单图：既不包含平行边又不包含环的图。第九页，共七十八页，编辑于2023年，星期日度：(1)在无向图G=<V,E>中，与顶点v(vV)关联的边的数目(每个环计算两次)，记作：d(v)。二、度第十页，共七十八页，编辑于2023年，星期日(2)在有向图D=<V,E>中，以顶点v(vV)作为始点的边的数目，称为该顶点的出度，记作：d+(v)；出度与入度之和，称为顶点v的度：度是图的性质的重要判断依据。d(v)=d+(v)+d–(v)以顶点v作为终点的边的数目，称为该顶点的入度，记作：d–(v)。第十一页，共七十八页，编辑于2023年，星期日最大度：

(G)=max{d(v)|vV}最小度：(G)=min{d(v)|vV}度与边数的关系：在任何图中，顶点度数的总和等于边数之和的两倍。握手定理的推论：任何图中，度为奇数的顶点个数一定为偶数。(握手定理)第十二页，共七十八页，编辑于2023年，星期日出度与入度的关系：在有向图中，各顶点的出度之和等于各顶点的入度之和。度数序列：设V={v1,v2,…,vn}为图G的顶点集，称(d(v1),d(v2),…,d(vn))为G的度数序列。度数序列之和必为偶数(?)。第十三页，共七十八页，编辑于2023年，星期日例8.1(3,3,2,3)，(5,2,3,1,4)能成为图的度数序列吗？为什么？解：由于这两个序列中，奇数个数均为奇数，由握手定理知，它们不能成为图的度数序列。第十四页，共七十八页，编辑于2023年，星期日例8.2

已知图G中有10条边，4个3度顶点，其余顶点的度数均小于等于2，问G中至少有多少个顶点？为什么？解：图中边数m=10，由握手定理知，G中各顶点度数之和为20，4个3度顶点占去12度，还剩8度，若其余全是2度顶点,则需要4个顶点来占用8度，所以G至少有8个顶点。第十五页，共七十八页，编辑于2023年，星期日正则图：各顶点的度都相同的图为正则图；各顶点的度均为k的图为k次正则图。完全图：(1)设G=<V,E>是n阶的无向简单图，如果G中任何一个顶点都与其余n–1个顶点相邻，则G为无向完全图，记作：Kn。三、正则图与完全图第十六页，共七十八页，编辑于2023年，星期日(2)设D=<V,E>是n阶的有向简单图，如果D中任意顶点u，vV(uv)，即有有向边<u,v>，又有有向边<v,u>，则称D为n阶有向完全图。如：第十七页，共七十八页，编辑于2023年，星期日四、子图与母图：(1)G=<V,E>，G'=<V',E'>若V'V，E'E，则G是G'的母图，

G'是G的子图，记作：G'

G。(2)若G'G且

V'=V，则G'是G的生成子图。第十八页，共七十八页，编辑于2023年，星期日(3)设V1V，且V1，以V1为顶点集，以2端点均在V1中的全体边为边集的G的子图，称为V1导出的导出子图。(4)设E1E，且E1，以E1为顶点集，以E1中边关联的顶点的全体为顶点集的G的子图，称为E1导出的导出子图。第十九页，共七十八页，编辑于2023年，星期日例8.3

列举下图的一些子图、真子图、生成子图、导出子图。e3e1e2e4e5v3v4v1v2解：自己对照定义做一做！(1)子图：子图的定义？举例(2)真子图：举例(3)生成子图：定义？举例(4)导出子图：定义？举例第二十页，共七十八页，编辑于2023年，星期日补图：给定一个图G=<V,E>，以V为顶点集，以所有能使G成为完全图的添加边组成边集的图。记作：～G五、补图如:(1)(2)第二十一页，共七十八页，编辑于2023年，星期日相对补图：设G'G,如果另一个图G''=<V'',E''>，满足(1)E''=E–E'(2)V''中仅包含E''中的边所关联的结点。则G''是子图G'相对于G的补图。如：图为的子图，则图(1)(2)(3)为(1)相对于(2)的补图。第二十二页，共七十八页，编辑于2023年，星期日图同构：对于G=<V,E>，G'=<V',E'>，如果存在g:VV'

满足：

(1)任意边e=(vi,vj)E，当且仅当e'=(g(vi),g(vj))E'(2)e与e'的重数相同则说G

G'由于同构图顶点之间一一对应，边之间一一对应，关联关系对应相同，所以可以看成同一个图。六、同构图第二十三页，共七十八页，编辑于2023年，星期日例8.4

画出4个顶点3条边的所有可能非同构的无向简单图。解：直观上容易看出，下面三个图是4个顶点3条边的所有非同构的无向简单图。第二十四页，共七十八页，编辑于2023年，星期日例8.5

画出3个顶点2条边的所有可能非同构的有向简单图。解：3个顶点2条边的无向简单图只有一个：由这个图可派生出下列4个非同构的有向简单图：课堂练习：画出4个顶点4条边的无向简单图。第二十五页，共七十八页，编辑于2023年，星期日

8.2通路、回路、图的连通性通路与回路：给定图G=<V,E>，设G中顶点与边的交替序列

=v0

e1

v1

e2…el

vl

满足：vi–1vi是ei的端点，(G为有向图时,要求vi–1,vi分别为ei的始点、终点)，i=1,2,…,l，则为顶点v0到vl的通路。中边的数目l称为的长度。v0=vl时，称为回路。一、通路与回路的概念第二十六页，共七十八页，编辑于2023年，星期日简单通路：

=v0

e1

v1

e2…ek

vk为通路且边e1

e2…ek互不相同，又称之为迹，可简用v0

v1…vk来表示。简单回路(v0=vk)又称为闭迹。初级通路或基本通路：

=v0

e1

v1

e2…ek

vk为通路且顶点v0

v1…vk互不相同。初级通路一定是简单通路，但简单通路不一定是一条初级通路。基本回路：v0

=vk。第二十七页，共七十八页，编辑于2023年，星期日例8.6

就下面两图列举长度为5的通路，简单通路，回路，简单回路，再列举长度为3的基本通路和回路。v1e1e4v2v3v4v5e3e5e2e7e6(1)(2)v5v1e2e5v2v3v4e1e7e3e8e6e4解：试对照定义，自己做一做！如：第二十八页，共七十八页，编辑于2023年，星期日v1(1)中v1e1v2e2v5e3v1e1v2e4v3为v1到v3的通路；v1e1v2e4v3e5v4e7v5e3v1为v1到v1的一条简单回路；v1e1v2e4v3e5v4e6v2e2v5为v1到v5的一条简单通路。e1e4v2v3v4v5e3e5e2e7e6(1)第二十九页，共七十八页，编辑于2023年，星期日(2)中v1e2v2e5v3e7v4v1到v4的长度为了的基本通路；v1e2v2e3v5e1v1是v1到v1的长度为了的基本回路。(2)v5v1e2e5v2v3v4e1e7e3e8e6e4第三十页，共七十八页，编辑于2023年，星期日二、通路与回路的性质：(1)在一个n阶图中，如果从顶点vi到vj(vivj)存在通路，则从vi到vj存在长度小于或等于n–1的通路。如果L>n–1，则此通路的顶点数L+1>n，从而必有顶点vs，它在序列中不止出现一次，即有序列vi…vs…vs…vj

。证明：设vi…vk…vj为vi到vj的长度为L的一条通路，则序列中必有L+1个顶点。在路中去掉vs到vs的这些边，至少去掉一条边后仍是vi到vj的一条通路。此通路比原来如此重复下去，必可得到一条从vi到vj的不多于n–1条边的通路。通路的长度至少少1。第三十一页，共七十八页，编辑于2023年，星期日(2)在n阶图中，如果从vi到vj(vivj)存在通路，则必存在从vi到vj的长度小于等于

n–1的基本通路。(3)在n阶图中，如果存在从vi到自身的回路，则从vi到自身存在长度等于n的回路。(4)在n阶图中，如果从vi到自身存在一条简单回路，则从vi到自身存在长度等于n的初级回路。第三十二页，共七十八页，编辑于2023年，星期日两顶点连通：u,v为无向图G的两个顶点，u到v存在一条通路。连通图：G中任何两个顶点是连通的；否则是分离图。三、图的连通性第三十三页，共七十八页，编辑于2023年，星期日连通性的性质：无向图中顶点之间的连通关系是顶点集V上的等价关系。(1)自反性：由于规定任何顶点到自身总是连通的；证明：(2)对称性：无向图中顶点之间的连通是相互的；(3)传递性：由连通性的定义可知。第三十四页，共七十八页，编辑于2023年，星期日连通分支：无向图G中每个划分块称为G的一个连通分支，p(G)表示连通分支的个数。p(G)=1为连通图。第三十五页，共七十八页，编辑于2023年，星期日点割集：无向图G=<V,E>为连通图，如果V'V，且在G中删除V'中所有顶点(包括与该顶点关联的边)后所得子图是不连通的或是平凡图，而删除V'中任何真子集中的顶点时，所得子图仍连通，则V'是G的点割集。

如果点割集中只有一个顶点，该点为割点。四、连通图的连通度第三十六页，共七十八页，编辑于2023年，星期日点连通度：G为无向连通图，记k(G)=min{|V'|V'是G的点割集}，称k(G)为G的点连通度。由定义知，点连通度即使G不连通的需删除顶点的最少数目。完全图Kn的连通度k(G)=n–1。存在割点的连通图连通度为1，分离图的连通度为0；第三十七页，共七十八页，编辑于2023年，星期日边割集：设无向图G=<V,E>连通，边集E'E，在G中删除E'中所有边后所得子图不连通，而删除E'中的任何子集中的边后，所得子图仍连通，则E'为G的边割集。如果边割集中只有一边时，该边为割边(或桥)第三十八页，共七十八页，编辑于2023年，星期日边连通度：设G为无向连通图，记(G)=min{|E'|E'是G的边割集}，(G)为G的边连通度。连通度的性质：k(G)(G)(G)第三十九页，共七十八页，编辑于2023年，星期日五、有向图的连通性：(1)如果有向图D=<V,E>中所有有向边的方向去掉后所得图为无向连通图，则说D为弱连通图。(2)u,vV，如果存在u到v的一条通路，则说u可达v。(3)弱连通图<V,E>中，任何一对顶点之间，至少有一顶点可达另一个顶点，则<V,E>是单向连通的；任何两个顶点之间互相可达，称<V,E>强连通。第四十页，共七十八页，编辑于2023年，星期日有向连通图的性质：(1)强连通一定单向连通，单向连通一定弱连通。反过来都不成立。第四十一页，共七十八页，编辑于2023年，星期日(2)有向图D强连通，当且仅当D中存在一条回路，它至少经过每个顶点一次。(充分性)如果D中存在回路C，它经过D中的每个顶点至少一次，则D中的任意两个顶点都在回路中，所以，D中任意两个顶点都是可达的，因而D是强连通的。证明：第四十二页，共七十八页，编辑于2023年，星期日因为vi可达vi+1,i=1,2,…，n–1，让这些通路首尾相连，(2)有向图D强连通，当且仅当D中存在一条回路，它至少经过每个顶点一次。(必要性)D是强连通的，则D中任何两个顶点都是可达的。则得一回路。显然每个顶点在回路中至少出现一次。证明：所以vi到vi+1存在通路，不妨设D中的顶点为v1,v2,…,vn，且vn到v1也存在通路，第四十三页，共七十八页，编辑于2023年，星期日8.3图的矩阵表示邻接矩阵：设G=<V,E>是一个简单图，它有n个顶点，V={v1,v2,…,vn}，令aij=1<vi,vj>E(或(vi,vj)E)0<vi,vj>E(或(vi,vj)E)称A(G)=(aij)为G的邻接矩阵。一、邻接矩阵及其性质第四十四页，共七十八页，编辑于2023年，星期日邻接矩阵的特性：在无向图中：(1)邻接阵是对称阵；(2)同一行或者同一列的元素和为对应顶点的度数(3)矩阵中所有元素的和为边数的2倍第四十五页，共七十八页，编辑于2023年，星期日在有向图中：(1)同一行的元素和为对应顶点的出度(2)同一列的元素和为对应顶点的入度(3)aij=2m(边的数目)第四十六页，共七十八页，编辑于2023年，星期日邻接矩阵可推广到多重图或带权图，这时令aij为vi到vj的边的重数或边上的权值W(vi,vj)。邻接阵多用于有向图。第四十七页，共七十八页，编辑于2023年，星期日关联矩阵：(1)设G=<V,E>为(n,m)无向图,V={v1,v2,…,vn},E={e1,e2,…,em},令：mij=10称M(G)=(mij)nxm为G的关联矩阵。vi

关联ejvi

不关联ej二、关联矩阵及其性质第四十八页，共七十八页，编辑于2023年，星期日(2)设D=<V,E>是有向图且无环，令：mij=10则称M(D)=(mij)nxm为D的关联矩阵。–1D中vi是ej的始点vi

与ej不关联vi

是ej的终点第四十九页，共七十八页，编辑于2023年，星期日无向图的关联矩阵的性质：(握手定理)第五十页，共七十八页，编辑于2023年，星期日有向图的关联矩阵的性质：由mij的定义知第五十一页，共七十八页，编辑于2023年，星期日通路数与回路数的矩阵算法：(1)设A是有向图D的邻接矩阵，V={v1,v2,…,vn}，Al(l1)中元素aij(l)为vi到vj长度为l的通路数通路总数回路数三、应用1.求通路数与回路数第五十二页，共七十八页，编辑于2023年，星期日(2)设A是有向图D的邻接矩阵，B1=A，B2=A+A2,……，Br=A+A2+…+Ar，则Br中元素bij(r)

为D中vi到vj长度小于等于r的通路数，2.求可达矩阵第五十三页，共七十八页，编辑于2023年，星期日可达矩阵：设D=<V,E>为一有向图，V={v1,v2,…,vn}，令pij=10ijpii=1i=1,2,…,n

称(pij)nxn

为D的可达矩阵。vi

可达vj否则第五十四页，共七十八页，编辑于2023年，星期日例.求下图的可达矩阵，判断它是否为强连通图？V1V4V2V3V5解：1.写出邻接矩阵第五十五页，共七十八页，编辑于2023年，星期日2.计算A2,A3,A4,A5.第五十六页，共七十八页，编辑于2023年，星期日3.计算B=A+A2+A3+A4+A5,并求出第五十七页，共七十八页，编辑于2023年，星期日可达矩阵的求法：由邻接矩阵A计算A2,A+A2,……A+A2+…+A(n–1)=B=(bij(n–1))nn

pij=1bij(n–1)

00bij(n–1)

=0则i

jpii=1即得可达矩阵P(D)=(pij)nxn

第五十八页，共七十八页，编辑于2023年，星期日8.4最短路径问题带权图：对于有向图或无向图的每条边附加一个实数w(e)，则得带权图。如果G1是带权图G的子图，称w(e)为边e上的权(当e=<vi,vj>时，权记作wij)，记作：G=<V,E,W>一、带权图及其最短路径问题第五十九页，共七十八页，编辑于2023年，星期日G=<V,E,W>为带权图，且G中各边带的权均大于等于0，从顶点u到顶点v的所有通路中求带权最小的通路问题，称为最短路径问题。最短路径问题：如果v1v2…vn–1vn是v1到vn的最短路径，则v1v2…vn–1也必然是v1从到vn–1的最短路径。求最短路径的标号法的基本思想：第六十页，共七十八页，编辑于2023年，星期日标号法：(1)符号说明(i)li(r)*为顶点v1到顶点vi最短路径的权(ii)lj(r)为v1到vj最短路径权的上界，如果vj获得lj(r)

，称vj在第r步获得t标号lj(r)(r0)如果顶点vi获得了标号li(r)*，称vi在第r步获得p标号li(r)*(iii)Pr={v|v已获得p标号}，称之为第r步通过集(r0)(iv)Tr=V–Pr

称之为第r步未通过集(r0)二、求最短路径问题的标号法第六十一页，共七十八页，编辑于2023年，星期日(2)算法：开始，r0，v1获p标号：l1(0)*=0，P0={v1}，T0=V–{v1}，vj(j1)的t标号：lj(0)=w1j=w1j

0v1与vj相邻v1与vj不相邻第六十二页，共七十八页，编辑于2023年，星期日修改通过集和未通过集：Pr=Pr–1∪{vi}，

Tr=Tr–1∪{vi}，step1.求下一个p标号顶点设lj(r)*=min{lj(r–1)}，r1。vjTr–1顶点vi处，表明vi获得p标号。查Tr：若Tr=，则算法结束，否则转step2将lj(r)*标在相应第六十三页，共七十八页，编辑于2023年，星期日step2.修改Tr中各顶点的t标号lj(r)=min{lj(r–1),li(r)*+wij}，li(r)*是刚刚获得p标号顶点的p标号。令r

r+1，转step1。第六十四页，共七十八页，编辑于2023年，星期日例8.7

求下图中顶点v0与v5之间的最短路径v0v2v1v4v3v5121475326第六十五页，共七十八页，编辑于2023年，星期日解：利用标号法算法解此题开始，r0，v0获p标号：

l0(0)*=0l1(0)=w01=1通过集P0={v0}，未通过集T0={v1，

v2，v3，

v4，v5}，l2(0)=w02=4l4(0)=

=l5(0)

l3(0)=w03=未通过集的t标号：v0v2v1v4v3v5121475326第六十六页，共七十八页，编辑于2023年，星期日第一步：r=1，计算=l1(1)*=1，所以i=1，P1={v0,v1}，T1={v2,v3,v4,v5}修改未通过集的t标号：l2(1)=min{l2(0),l1(1)*+w12}=min{4,3}=3l3(1)=min{l3(0),l1(1)*+w13}=min{,8}=8l4(1)=min{l4(0),l1(1)*+w14}=6l5(1)=min{l5(0),l1(1)*+w15}=vi获p标号l1(1)*，修改通过集与未通过集:第六十七页，共七十八页，编辑于2023年，星期日修改通过集与未通过集

P2={v0,v1,

v2}，T2={v3,v4,v5}修改未通过集的t标号：l3(2)=min{l3(1),l2(2)*+w23}=min{8,3+}=8l4(2)=min{l4(1),l2(2)*+w24}=min{6,3+1}=4l5(2)=min{l5(0),l2(2)*+w25}=min{,3+}=第六十八页，共七十八页，编辑于2023年，星期日修改通过集与未通过集

P3={v0,v1,

v2,v4},T3={v5,v3}修改未通过集的t标号：l3(3)=min{l3(2),l4(3)*+w43}=min{8,4+3}=7l5(3)=min{l5(2),l4(3)*+w45}=min{,4+