离散数学-图论基础课件

第七章图论基础

Graphs第七章图论基础

Graphs30十月2022第一节图的基本概念一个图G定义为一个三元组：G=<V,E,Φ>V——非空有限集合，V中的元素称为结点(node)或

顶点(vertex)E——有限集合（可以为空），E中的元素称为边(edge)Φ——从E到V的有序对或无序对的关联映射(associativemapping)v1v2v3(a)v1v2v3(b)v1v2v3(c)22十月2022第一节图的基本概念一个图G定义为一个三30十月2022图的基本概念图G=<V,E,Φ>中的每条边都与图中的无序对或有序对联系若边eE与无序对结点[va,vb]相联系，即Φ(e)=[va,vb]

（va,vb

V）则称e是无向边（或边、棱）若边eE与有序对结点<va,vb>相联系，即Φ(e)=<va,vb>

（va,vb

V）则称e是有向边（或弧）

va是e的起始结点，vb是e的终结点v1v2v3(a)v1v2v3(b)v1v2v3(c)22十月2022图的基本概念图G=<V,E,Φ>中的30十月2022图的基本概念若va和vb与边（弧）e相联结，则称va和vb是e的端结点

va和vb是邻接结点，记作：va

adjvb

(adjoin)

也称e关联va和vb，或称va和vb关联e若va和vb不与任何边（弧）相联结，则称va和vb是非邻接结点，记作：va

nadjvb关联同一个结点的两条边（弧），称为邻接边（弧）关联同一个结点及其自身的边，称为环(cycle)，环的方向没有意义v1v2v3(a)v1v2v3(b)v1v2v3(c)22十月2022图的基本概念若va和vb与边（弧）e相联30十月2022图的基本概念若将图G中的每条边（弧）都看作联结两个结点

则G简记为：<V,E>每条边都是弧的图，称为有向图(directedgraph)（如图b）

每条边都是无向边的图，称为无向图(undirectedgraph)

（如图a）

有些边是弧，有些边是无向边的图，称为混合图（如图c）v1v2v3(a)v1v2v3(b)v1v2v3(c)22十月2022图的基本概念若将图G中的每条边（弧）都看30十月2022图的基本概念若图G中的任意两个结点之间不多于一条无向边（或不多于一条同向弧），且任何结点无环，则称G为简单图（如图c）若图G中某两个结点之间多于一条无向边（或多于一条同向弧），则称G为多重图（如图a,b）

两个结点间的多条边（同向弧）称为平行边（弧），

平行边（弧）的条数，称为重数v1v2v3(a)v1v2v3(b)v1v2v3(c)22十月2022图的基本概念若图G中的任意两个结点之间不30十月2022图的基本概念在多重图的表示中，可在边（弧）上标注正整数，以表示平行边（弧）的重数把重数作为分配给边（弧）上的数，称为权(weight)

将权的概念一般化，使其不一定是正整数，则得到加权图的概念：给每条边（弧）都赋予权的图，叫做加权图(weightedgraph)

记作G=<V,E,W>，W是各边权之和v1v2v3(a)v1v2v3(b)v1v2v3(c)111111221122十月2022图的基本概念在多重图的表示中，可在边（弧30十月2022图的基本概念在无向图G=<V,E>中，V中的每个结点都与其余的所有结点邻接，即 (va)(vb)(va,vb

V[va,vb]E)，如图(a)

则称该图为无向完全图(completegraph)，记作K|V|

若|V|=n，则|E|=C

=n(n-1)/2v1v2v3(a)v1v2v3(b)2n22十月2022图的基本概念在无向图G=<V,E>中，30十月2022图的基本概念在有向图G=<V,E>中，V中的任意两个结点间都有方向相反的两条弧，即

(va)(vb)(va,vbV<va,vb>E∧<vb,va>E)，如图(a)

则称该图为有向完全图，记作K|V|

若|V|=n，则|E|=P=n(n-1)v1v2v3(a)v1v2v3(b)2n22十月2022图的基本概念在有向图G=<V,E>中，30十月2022图的基本概念在图G=<V,E>中，若有一个结点不与其他任何结点邻接

则该结点称为孤立结点，如图(a)中的v4仅有孤立结点的图，称为零图，零图的E=，如图(b)仅有一个孤立结点的图，称为平凡图(trivialgraph)，如图(c)v1v2v3(a)v1v2v3(b)v1(c)v422十月2022图的基本概念在图G=<V,E>中，若有30十月2022问题问题1：是否存在这种情况：25个人中，由于意见不同，每个人恰好与其他5个人意见一致？问题2：是否存在这种情况：2个或以上的人群中，至少有2个人在此人群中的朋友数一样多？22十月2022问题问题1：是否存在这种情况：25个人中30十月2022结点的次数二、结点的次数定义：在有向图G=<V,E>中，对任意结点vV以v为起始结点的弧的条数，称为出度(out-degree)

（引出次数），记为d+(v)以v为终结点的弧的条数，称为入度(in-degree)

（引入次数），记为d-(v)v的出度和入度的和，称为v的度数(degree)

（次数），记为d(v)=d+(v)+d-(v)v1v2v3(a)22十月2022结点的次数二、结点的次数v1v2v3(a30十月2022结点的次数定义：在无向图G=<V,E>中，对任意结点vV结点v的度数d(v)，等于联结它的边数若结点v上有环，则该结点因环而增加度数2记G的最大度数为：(G)=max{d(v)|vV}

记G的最小度数为：(G)=min{d(v)|vV}v1v2v3(a)v1v2v3(b)v422十月2022结点的次数定义：在无向图G=<V,E>30十月2022结点的次数在图G中的任意一条边eE，都对其联结的结点贡献度数2定理：在无向图G=<V,E>中，

d(v)

=2|E|通常，将度数为奇数的结点称为奇度结点

将度数为偶数的结点称为偶度结点定理：在无向图G=<V,E>中，奇度结点的个数为偶数个22十月2022结点的次数在图G中的任意一条边eE30十月2022结点的次数问题1：是否存在这种情况：25个人中，由于意见不同，每个人恰好与其他5个人意见一致？在建立一个图模型时，一个基本问题是决定这个图是什么

——什么是结点？什么是边？在这个问题里，我们用结点表示对象——人；

边通常表示两个结点间的关系——表示2个人意见一致。

也就是说，意见一致的2个人（结点）间存在一条边。22十月2022结点的次数问题1：是否存在这种情况：2530十月2022结点的次数问题1：是否存在这种情况：25个人中，由于意见不同，每个人恰好与其他5个人意见一致？这样我们可以知道，如果存在题目所述情况，那么每个结点都与其他5个结点相关联。

也就是说，每个结点的度为5。由定理可知：奇度结点的个数为偶数个。

现在是否能够得出结论了？22十月2022结点的次数问题1：是否存在这种情况：2530十月2022结点的次数类似问题：晚会上大家握手言欢，握过奇数次手的人数一定是偶数碳氢化合物中，氢原子个数是偶数是否有这样的多面体，它有奇数个面，每个面有奇数条棱？22十月2022结点的次数类似问题：30十月2022结点的次数问题2：是否存在这种情况：两个人或以上的人群中，至少有两个人在此人群中的朋友数一样多？以人为结点，仅当二人为朋友时，在此二人之间连一边，得一“友谊图”G(V,E)，设V={v1,v2,…,vn}，不妨设各结点的次数为d(v1)≤d(v2)≤…≤d(vn)≤n-1。假设命题不成立，则所有人的朋友数都不一样多，则

0≤

d(v1)<d(v2)<…<d(vn)≤n-1。22十月2022结点的次数问题2：是否存在这种情况：两个30十月2022结点的次数问题2：是否存在这种情况：两个人或以上的人群中，至少有两个人在此人群中的朋友数一样多？若0≤

d(v1)<d(v2)<…<d(vn)≤n-1，则有：由于d(v1)≥0，则有d(v2)≥1，d(v3)≥2，…，d(vn)≥n-1；又因为d(vn)≤n-1，所以：d(vn)=n-1因为d(vn)=n-1，则每个结点皆与vn相邻，则d(v1)≥1。于是有：d(v2)≥2，d(v3)≥3，…，d(vn)≥n，矛盾。故假设不成立，即d(v1)<d(v2)<…<d(vn)中至少有一个等号成立，命题成立。22十月2022结点的次数问题2：是否存在这种情况：两个30十月2022结点的次数定义：在无向图G=<V,E>中，若每个结点的度数都是k，即 (v)(v

V

d(v)=k)，则称G为k度正则图(regulargraph)v1v2v6v33度正则图v4v5v7v8v9v103度正则图v1v5v6v2v3v422十月2022结点的次数定义：在无向图G=<V,E>30十月2022子图三、子图定义：给定无向图G1=<V1,E1>，G2=<V2,E2>若V2

V1，E2

E1，则称G2是G1的子图(subgraph)，

记作G2

G1若V2

V1，E2

E1，且E2≠

E1，则称G2是G1的真子图，记作G2

G1若V2=

V1，E2

E1，则称G2是G1的生成子图(spanningsubgraph)，记作G2

G1V2=

V122十月2022子图三、子图V2=V130十月2022子图例如：v2v1(a)v3v4v5(a)的真子图v2v3v4v5(a)的生成子图v2v3v4v5v122十月2022子图例如：v2v1(a)v3v4v5(a30十月2022子图定义：对于图G=<V,E>，G1=<V,E>=G，G2=<V,

>

G1和G2都是G的生成子图，称为平凡生成子图定义：设G2=<V2,E2>是G1=<V1,E1>的子图对任意结点u,vV2，若有[u,v]E1，则有[u,v]E2，

则G2由V2唯一地确定，则称G2是V2的诱导子图

记作G[V2]，或G2=<V2>若G2中无孤立结点，且由E2唯一地确定，则称

G2是E2的诱导子图，记作G[E2]，或G2=<E2>22十月2022子图定义：对于图G=<V,E>，G1=30十月2022子图例如：v2v1G=<V,E>v3v4v5G’=<V’,E’>

V’或E’的诱导子图v2v3v4v522十月2022子图例如：v2v1G=<V,E>v3v30十月2022补图定义：

设G1=<V1,E1>和G2=<V2,E2>是G=<V,E>的子图，

若E2=E-E1，且G2是E2的诱导子图，即G2=<E2>

则称G2是相对于G的G1的补图22十月2022补图定义：

设G1=<V1,E1>和G30十月2022补图 图G1和G2互为相对于G补图G1v2v1v3v4v5G2v2v3v4v5Gv2v1v3v4v522十月2022补图 图G1和G2互为相对于G补图G1v30十月2022补图定义：

给定图G1=<V,E1>，若存在图G2=<V,E2>

且E1E2=，及图<V,E1

E2

>是完全图

则称G2是相对于完全图的G1的补图，记作G2=G122十月2022补图定义：

给定图G1=<V,E1>30十月2022补图

G2=G1v2v1G1v3v4v5v2v1K5v3v4v5G2v2v3v4v5v122十月2022补图 G2=G1v2v1G1v3v30十月2022图的同构四、图的同构定义：

给定图G1=<V1,E1>，G2=<V2,E2>

若存在双射函数f:V1V2，使得对于任意u,vV1

有 [u,v]E1[f(u),f(v)]E2

（或<u,v>E1<f(u),f(v)>E2）

则称G1与G2同构(isomorphic)，记作G1

G222十月2022图的同构四、图的同构30十月2022图的同构例7.1.1证明下面两个图G1=<V1,E1>，G2=<V2,E2>同构证明：V1={v1,v2,v3,v4},V2={a,b,c,d}构造双射函数f:V1V2，f(v1)=a，f(v2)=b

f(v3)=c，f(v4)=d可知，边[v1,v2],[v2,v3],[v3,v4],

[v4,v1]被分别映射成[a,b],

[b,c],[c,d],[d,a]，故G1

G2v2v1G1v3v4badcG222十月2022图的同构例7.1.1证明下面两个图G130十月2022图的同构例7.1.2证明下面两个有向图是同构的。G1eabcd证明：如图所示，G1=<V1,E1>，G2=<V2,E2>，结点编号如图所示。 构造函数f:V1V2，使得f(a)=1,f(b)=3,f(c)=4,f(d)=5,f(e)=2 则<a,e>,<b,a>,<b,c>,<c,e>,<d,a>,<d,c>,<e,b>,<e,d>被分别映射成<1,2>,<3,1>,<3,4>,<4,2>,<5,1>,<5,4>,<2,3>,<2,5>

故f是双射函数，所以G1与G2同构G13124522十月2022图的同构例7.1.2证明下面两个有向图30十月2022图的同构可以给出图的同构的必要条件：结点数相等边数相等度数相等的结点数相等要注意的是，这不是充分条件22十月2022图的同构可以给出图的同构的必要条件：30十月2022图的同构例7.1.3证明下面两个无向图是不同构的G1v1v2v3v4v5v6v7v8G2abcdefghv1是3度结点，故f(v1)只能是c或d或g或h。若f(v1)=c，由于v2、v4和v5与v1邻接，因此f(v2)、f(v4)和f(v5)应当分别为与c邻接的b、d和g。但是，v2、v4和v5中，只有一个3度结点，而b、d、g中却有2个3度结点，故f(v1)≠c。同理可说明，f(v1)也不可能是d、g和h。因此这样的f是不存在的。因此G1和G2是不同构的。22十月2022图的同构例7.1.3证明下面两个无向图30十月2022第二节路(链)与回路(圈)一、路(链)与回路(圈)定义：给定图G=<V,E>，令v0,v1,…,vmV，e1,e2,…,emE称交替序列v0e1v1

e2

v2…emvm为连接v0到vm的链（路）称v0和vm为链（路）的始结点和终结点链的长度为边（弧）的数目m若v0=vm，该链（路）称为圈（回路,circuit）22十月2022第二节路(链)与回路(圈)一、路(链)30十月2022链和圈在链中：若任意ei只出现一次，则称该链（路）为简单链（路）若任意vi只出现一次，则称该链（路）为基本链（路）基本链必定是简单链在圈中：若任意ei只出现一次，则称该圈（回路）为简单圈（回路）若任意vi只出现一次，则称该圈（回路）为基本圈（回路）22十月2022链和圈在链中：30十月2022链和圈例7.2.1下图中：v3v1v4v5v2e1e2e3e4e5e6e7e8P1=(v1e1v2e7v5)

也可以表示为：P1=(e1e7)

是一个基本链，也是一个简单链P2=(v2e2v3e3v3e4v1e1v2)

也可以表示为：P2=(e2e3e4e1

)

是一个简单圈，但不是基本圈P3=(v4e6v2e7v5e8v4e6v2e2v3)是一个链P4=(v2e7v5e8v4e6v2)是一个基本圈，也是一个简单圈22十月2022链和圈例7.2.1下图中：v3v1v30十月2022链和圈链和圈可以只用边的序列表示

上例中：(v2e2v3e3v3e4v1e1v2)也可表示为(e2e3e4e1)

(v4e6v2e7v5e8v4e6v2e2v3)也可表示为(e6e7e8e6e2)对于简单图来说，链和圈可以仅用结点序列表示v3v1v4v5v2e1e2e4e5e6e3e8图中：

(v2e2v3e4v1e1v2e3v5e8v4)

可表示为(e2e4e1e3e8)

也可表示为(v2v3v1v2v5v4)22十月2022链和圈链和圈可以只用边的序列表示

上例中30十月2022链和圈定理：在一个图中，若从结点vi到结点vj存在一条链（路）， 则必有一条从vi到vj的基本链（路）证明：1)若从vi到vj给定的链本身就是基本链，定理成立2)若从vi到vj给定的链不是基本链，则至少含有一个结点vk，它在该链中至少出现两次以上。也就是说，经过vk有一个圈，于是可以从原有链中去除中所有出现的边（弧）。对于原链中所含的所有圈都做此处理，最终将得到一条基本链（路）22十月2022链和圈定理：在一个图中，若从结点vi到结30十月2022链和圈问题：在一个图中，若从结点vi到结点vj存在一个圈，

则必有一个从vi到vj的基本圈吗？例7.2.2若u和v是一个圈上的两个结点，u和v一定是某个基本圈上的结点吗？(习题7-16)答：不一定vaudcb本图中，u和v在一个圈上，但是却不在一个基本圈上22十月2022链和圈问题：在一个图中，若从结点vi到结30十月2022链和圈定理：在一个具有n个结点的图中，任何基本链（路）的长度不大于n-1任何基本圈（回路）的长度不大于n证明：1)根据基本链的定义可知，出现在基本链中的结点都是不同的。因此在长度为m的基本链中，不同的结点数为m+1又因为图中仅有n个结点，故m+1≤n，即m≤n-12)根据基本圈的定义可知，长度为k的基本圈中，不同的结点数为k，图中共有n个结点，所以k≤n22十月2022链和圈定理：在一个具有n个结点的图中，30十月2022可达二、连通图定义：

在一个图中，若从vi到vj存在任何一条链

则称从vi到vj是可达的(accessible)，简称vi可达vj规定：每个结点vi到自身都是可达的22十月2022可达二、连通图30十月2022连通无向图（一）连通无向图对于无向图G=<V,E>而言，可证明“可达性”是一个___关系。它对V给出一个划分，每个块中的元素形成一个诱导子图。两个结点间是可达的，当且仅当它们属于同一个子图

称这样的子图为G的连通分图，G的连通分图的个数记为(G)若G中只有一个连通分图，则称G是连通图(即任意两结点可达)

否则称G为非连通图，或分离图等价22十月2022连通无向图（一）连通无向图等价30十月2022连通无向图定义：在无向图G=<V,E>中若任意两个结点可达，则称G是连通的(connected)，

称G为连通无向图；

否则称G是非连通的，称G为非连通图或分离图。若G的子图G’是连通的，且不存在包含G’的更大的G的

子图G’’是连通的，则称G’是G的连通分图(connectedcomponents)，简称分图。G中连通分图的个数记为(G)。22十月2022连通无向图定义：在无向图G=<V,E>30十月2022连通无向图例7.2.3v3v1v4v5v2v3v1v4v5v2G1G2G1是连通图，(G1)=1G2是非连通图，(G2)=222十月2022连通无向图例7.2.3v3v1v4v5v30十月2022连通无向图定义：从图G=<V,E>中删除结点集S，是指V-SE-{与S中结点相连结的边}而得到的子图，记做G-SG-{v3}v3v1v4v5v2Gv3v1v4v5v2v3v1v4v5v222十月2022连通无向图定义：从图G=<V,E>中删30十月2022连通无向图定义：从图G=<V,E>中删除结点集S，是指V-SE-{与S中结点相连结的边}而得到的子图，记做G-SG-{v3}v1v4v5v2G22十月2022连通无向图定义：从图G=<V,E>中删30十月2022连通无向图定义：从图G=<V,E>中删除边集T，是指V不变E-T而得到的子图，记做G-TG-{e1,e3,e4}v3v1v4v5v2Ge1e2e3e4e5e6e7v3v1v4v5v222十月2022连通无向图定义：从图G=<V,E>中删30十月2022连通无向图定义：从图G=<V,E>中删除边集T，是指V不变E-T而得到的子图，记做G-TG-{e1,e3,e4}v3v1v4v5v2Ge2e5e6e722十月2022连通无向图定义：从图G=<V,E>中删30十月2022连通无向图定义：给定连通无向图G=<V,E>，SV若(G-S)>(G)=1且对任意TS，(G-T)=(G)则称S是G的一个分离结点集(cut-setofnodes)若S中仅含有一个元素v，则称v是G的割点(cut-node)22十月2022连通无向图定义：给定连通无向图G=<V,30十月2022连通无向图例7.2.4 G如下图所示，S={v1,v3}v2v1v5v6v4Gv3v2v1v5v6v4G-Sv3v2v5v6v4G-S(G)=1，(G-S)=2

(G-S)>(G)22十月2022连通无向图例7.2.4 G如下图所示，S30十月2022连通无向图例7.2.4 G如下图所示，S={v1,v3}v2v1v5v6v4Gv3(G)=1，(G-S)=2

(G-S)>(G)(G-{v1})=1v2v5v6v4G-{v1}v322十月2022连通无向图例7.2.4 G如下图所示，S30十月2022连通无向图例7.2.4 G如下图所示，S={v1,v3}v2v1v5v6v4Gv3(G)=1，(G-S)=2

(G-S)>(G)(G-{v1})=1v2v1v5v6v4G-{v3}(G-{v3})=122十月2022连通无向图例7.2.4 G如下图所示，S30十月2022连通无向图例7.2.4 G如下图所示，S={v1,v3}v2v1v5v6v4Gv3v2v5v6v4G-S(G)=1，(G-S)=2

(G-S)>(G)

(G-{v1})=1(G-{v3})=1S是G的分离结点集22十月2022连通无向图例7.2.4 G如下图所示，S30十月2022连通无向图例7.2.5 G如下图所示，S={v2}v1v4v5v3Gv2(G)=1，(G-S)=2

(G-S)>(G)v1v4v5v3G-Sv2是G的割点不存在其他的G的割点22十月2022连通无向图例7.2.5 G如下图所示，S30十月2022连通无向图定义：给定连通无向图G=<V,E>，TE若(G-T)>(G)=1且对任意FT，(G-F)=(G)则称T是G的一个分离边集(cut-setofedges)若T中仅含有一个元素e，则称e是G的割边(cut-edge)，或桥22十月2022连通无向图定义：给定连通无向图G=<V,30十月2022连通无向图例7.2.6 G如下图所示，T={e1,e2}(G)=1，(G-T)=2

(G-T)>(G)v1v3v4Gv2e1e4e2e3v1v3v4G-Tv2e4e322十月2022连通无向图例7.2.6 G如下图所示，T30十月2022连通无向图例7.2.6 G如下图所示，T={e1,e2}(G)=1，(G-T)=2

(G-T)>(G)v1v3v4Gv2e1e4e2e3v1v3v4G-{e1}v2e4e2e3(G-{e1})=122十月2022连通无向图例7.2.6 G如下图所示，T30十月2022连通无向图例7.2.6 G如下图所示，T={e1,e2}(G)=1，(G-T)=2

(G-T)>(G)v1v3v4Gv2e1e4e2e3(G-{e1})=1(G-{e2})=1v1v3v4G-{e2}v2e1e4e322十月2022连通无向图例7.2.6 G如下图所示，T30十月2022连通无向图例7.2.6 G如下图所示，T={e1,e2}(G)=1，(G-T)=2

(G-T)>(G)v1v3v4Gv2e1e4e2e3v1v3v4G-Tv2e4e3(G-{e1})=1(G-{e2})=1T是G的分离边集22十月2022连通无向图例7.2.6 G如下图所示，T30十月2022连通无向图例7.2.7 G如下图所示，T={e1}(G)=1，(G-T)=2

(G-T)>(G)v1v3v4Gv2e1e2e3v1v3v4G-Tv2e2e3e1是G的割边e2和e3都是G的割边22十月2022连通无向图例7.2.7 G如下图所示，T30十月2022连通无向图定义：对连通的非平凡图G=<V,E>，称

(G)=min{|S||S是G的分离结点集}

为G的结点连通度(node-connectivity)

它表明产生分离图需要删去结点的最少数目对分离图G而言，(G)=0对存在割点的连通图G而言，(G)=1SV22十月2022连通无向图定义：对连通的非平凡图G=<V30十月2022连通无向图例7.2.8 求G1和G2的结点连通度v2v1v5v6v4G1v3(G1)=2(G2)=1v1v4v5v3G2v222十月2022连通无向图例7.2.8 求G1和G2的结30十月2022连通无向图定义：对连通的非平凡图G=<V,E>，称

(G)=min{|T||T是G的分离边集}

为G的边连通度(edge-connectivity)

它表明产生分离图需要删去边的最少数目对分离图G而言，(G)=0对存在割边的连通图G而言，(G)=1对无向完全图Kn，(Kn)=?TEn-122十月2022连通无向图定义：对连通的非平凡图G=<V30十月2022连通无向图例7.2.9 求G1和G2的边连通度(G1)=2(G2)=1v1v3v4G1v2e1e4e2e3v1v3v4G2v2e1e2e322十月2022连通无向图例7.2.9 求G1和G2的边30十月2022连通无向图定理：对于任何一个无向图G，有(G)≤(G)≤

(G)证明：1)若G是分离图，则(G)=(G)=0，而(G)≥02)若G是连通图，先证明 (G)≤(G)若G是平凡图，则(G)=0=(G)若G不是平凡图，则当删去所有联结一个具有最小度的结点的边（除了环）后，便产生了一个分离图，因此(G)≤(G)再证明 (G)≤(G)

若(G)＝1，则G存在一个割边，显然(G)=(G)=1v3v1v4v5v2v1v1v3v4Gv2e1e2e3v1v3v4G–{e1}v2e2e3v1v3v4Gv2e1e2e3v1v3v4G–{e1}v2e2e3v3v4G–{v1}v2e322十月2022连通无向图定理：对于任何一个无向图G，有30十月2022连通无向图若(G)≥2，则删去某(G)条边后，G就成为分离图若只删除(G)-1条边，则仍得到连通图且存在一割边e=[u,v]对于(G)-1条边中的每一条边，选取一个不同于u和v的结点，把这些结点删去，将必须至少删去(G)-1条边若这样会产生分离图，则 (G)≤(G)-1<

(G)若这样产生的仍是连通图且e是割边，再删除结点u或v必将产生分离图，因此 (G)≤(G)v1v3v4Gv2e1e4e2e3v1v3v4G–{v2}e2e3v1v4G–{v3}综上所述，有(G)≤(G)≤

(G)22十月2022连通无向图若(G)≥2，则删去某30十月2022连通无向图定理：一个连通无向图G中的结点v是割点，充要条件是存在两个结点u和w，使得联结u和w的每条链都经过v证明：1)充分性：若G中联结u和w的每条链都经过v，删去v，则在子图G-{v}中，u和w必定不可达，故v是G的割点2)必要性：若v是G的割点，删去v，则子图G-{v}中至少有两个连通分图G1=<V1,E1>和G2=<V2,E2>

，任取两个结点

uV1，wV2，u和w不可达。故G中联结u和w的每条链必经过v22十月2022连通无向图定理：一个连通无向图G中的结点30十月2022连通无向图同理可以证明：定理：一个连通无向图G中的边e是割边，充要条件是存在两个结点u和w，使得联结u和w的每条链都经过e定理：一个连通无向图G中的边e是割边，充要条件是e不包含在G的任何基本圈中证明：教材P172（定理7.8)22十月2022连通无向图同理可以证明：30十月2022乌拉姆猜想（1929）左右两张相片，捂住左边相片的一部分，也捂住右边相片的相应部分，例如都捂住左眼，能看到的相片的大部分形象一致；再分别捂住左右相片的另一个对应部分，例如右耳，结果能看到的相片的大部分仍然一致。如此轮番地观察各次对应的暴露部分，都会看到相同的形象，那么谁都会相信这两张照片是同一个人或孪生兄弟的留影。数学描述：有图G1={V1,E1}和G2={V2,E2}，

V1={v1,v2,…,vn}，V2={u1,u2,…,un}（n≥3）。

如果G1-{vi}≌G2-{ui}，i=1,2,…,n，则G1≌G222十月2022乌拉姆猜想（1929）左右两张相片，捂住30十月2022连通有向图（二）连通有向图对于有向图G=<V,E>而言，结点间的可达性不再是等价关系，它仅仅是自反的和可传递的，一般不是对称的定义：对于给定的有向图G，要略去G中每条边的方向，

便得到一个无向图G’，称G’是G的基础图22十月2022连通有向图（二）连通有向图30十月2022连通有向图定义：在简单有向图G中，若任何两个结点间都是可达的，则称G是强连通的若任何两个结点间，至少是从一个结点可达另一个结点，则称G是单向连通的若G的基础图是连通的，则称G是弱连通的22十月2022连通有向图定义：在简单有向图G中，30十月2022连通有向图例7.2.10判断G1、G2和G3是强连通？单向连通？弱连通？G1是强连通的v1v3v4G1v2v1v3v4G2v2v1v3v4G3v2G2是单向连通的G3是弱连通的22十月2022连通有向图例7.2.10判断G1、G230十月2022连通有向图由定义可知：若G是强连通的，则它必定是单向连通的

反之未必真若G是单向连通的，则它必是弱连通的

反之未必真22十月2022连通有向图由定义可知：30十月2022连通有向图定理：有向图G是强连通的，当且仅当G中有一回路，它至少通过每个结点一次证明：1)充分性：若G中存在一条回路，它至少通过每个结点一回，则G中任何两个结点都是互相可达的，所以G是强连通的。2)必要性：若G是强连通的，则G中任何两个结点都是互相可达的，因此可以做出一条回路经过G中所有结点，否则，必有某结点v不在该回路上，v与回路上的各结点不可能都互相可达。与G是强连通的矛盾22十月2022连通有向图定理：有向图G是强连通的，当且30十月2022连通有向图定义：在简单有向图G中具有强连通性质的极大子图，称为强分图具有单向连通性质的极大子图，称为单向分图具有弱连通性质的极大子图，称为弱分图22十月2022连通有向图定义：在简单有向图G中30十月2022连通有向图例7.2.11 求G的强分图、单向分图和弱分图v3v2v1Gv4v5v6v3v2v1v4v5v6G的强分图有：定理：简单有向图G中的任意一个结点，恰位于一个强分图中22十月2022连通有向图例7.2.11 求G的强分图、30十月2022连通有向图定理：简单有向图G中的任意一个结点，恰位于一个强分图中证明：由强分图的定义可知，G中每个结点位于一个强分图中假设G中存在结点v位于两个强分图G1和G2中则由强分图的定义可知，G1中的每个结点与v互相可达，G2中的每个结点也与v互相可达故G1中的每个结点与G2中的每个结点通过v，能够互相可达，这与G1和G2是两个强分图矛盾因此G中每个结点只能位于一个强分图中22十月2022连通有向图定理：简单有向图G中的任意一个30十月2022连通有向图例7.2.11 求G的强分图、单向分图和弱分图G的单向分图有：v3v2v1Gv4v5v6v3v2v1v4v5v5v6定理：简单有向图G中的每个结点和每条弧,至少位于一个单向分图中22十月2022连通有向图例7.2.11 求G的强分图、30十月2022连通有向图例7.2.11 求G的强分图、单向分图和弱分图G的弱分图有：v3v2v1Gv4v5v6v3v2v1v4v5v6定理：简单有向图G中的每个结点和每条弧

恰位于一个弱分图中22十月2022连通有向图例7.2.11 求G的强分图、30十月2022结点间的距离三、结点间的距离定义：在图G中，若结点u可达结点v，它们之间可能存在不止一条链（路）。

在所有链中，最短链的长度称为结点u和v之间的距离

（或短程线、测地线）。记做：d<u,v>22十月2022结点间的距离三、结点间的距离30十月2022结点间的距离距离满足下面性质：d<u,v>≥0d<u,u>=0d<u,v>+d<v,w>≥d<u,w>若u不可达v，则d<u,v>=+即使u和v互相可达，d<u,v>未必等于d<v,u>

22十月2022结点间的距离距离满足下面性质：30十月2022有向图在计算机中的应用四、有向图在计算机中的应用这里给出一个简单有向图在计算机中的应用——

利用资源分配图来纠正和发现死锁22十月2022有向图在计算机中的应用四、有向图在计算机30十月2022有向图在计算机中的应用在多道程序的计算机系统中，同一时间内有多个程序需要同时执行。每个程序都共享计算机资源：如CPU、内存、外存、输入设备、编译系统等，操作系统将对这些资源分配给各个程序。当一个程序需要使用某种资源的时候，要向操作系统发出请求，操作系统必须保证这个请求得到满足，才能运行该程序22十月2022有向图在计算机中的应用在多道程序的计算机30十月2022有向图在计算机中的应用对资源的请求可能发生冲突，发生死锁。例如：程序P1占有资源r1，请求资源r2程序P2占有资源r2，请求资源r1有冲突的请求必须要解决，可以利用有向图来模拟对资源的请求，从而帮助发现和纠正“死锁”状态22十月2022有向图在计算机中的应用对资源的请求可能发30十月2022有向图在计算机中的应用令Pt={P1,P2,P3,P4}是t时刻运行的程序集合

Rt={r1,r2,r3,r4}是t时刻所需要的的资源集合P1占有资源r4，请求资源r1P2占有资源r1，请求资源r2和r3P3占有资源r2，请求资源r3P4占有资源r3，请求资源r1和r4可得到资源分配图G如图所示r4r3r2r1P1P3P2P2P4P4可证：t时刻系统处于死锁状态G中包含多于一个结点的强分图22十月2022有向图在计算机中的应用令Pt={P1,30十月2022有向图在计算机中的应用t时刻系统处于死锁状态G中包含多于一个结点的强分图解决办法：

使G中的每个强分图中

都是单个结点r4r3r2r1P1P3P2P2P4P4r4r3r2r1P1P3P2P222十月2022有向图在计算机中的应用t时刻系统处于死锁30十月20223x+1猜想（卡拉兹）20世纪30年代，汉堡大学的卡拉兹（Callatz）提出一个猜想：x0是一个自然数，若x0是偶数，则取x1=x0/2，若x0是奇数，则取x1=(3x0+1)/2。将x1应用上述规则得到x2，……如此进行下去，则到达某一步，xk=1。东京大学的N.永内达（NabuoYoneda）用计算机检验了所有不超过240≈1.2×1012的自然数，结果都符合卡拉兹的猜想。22十月20223x+1猜想（卡拉兹）20世纪30年代，30十月20223x+1猜想（卡拉兹）如果把一批自然数放在最高层，用3x+1问题的规则算出第二层的值，继而算出第三层的值……。图中的结点是自然数，当数1算出数2时，则在图上画上有向边<数1,数2>，得到的有向图称为卡拉兹有向图，如图所示。3x+1猜想中，卡拉兹图的最底层结点是1。22十月20223x+1猜想（卡拉兹）如果把一批自然数放30十月2022第三节图的矩阵表示一、图的矩阵表示定义：给定简单图G=<V,E>，V={v1,v2,…,vn}

V中的结点按照下标由小到大编序（编序与矩阵形式有密切关系），则n阶方阵AG=(aij)称为图G的邻接矩阵(adjacencymatrix)。其中：aij= i,j=1,2,…,n1 viadjvj

0 vinadjvj22十月2022第三节图的矩阵表示一、图的矩阵表示ai30十月2022邻接矩阵例7.3.1图G=<V,E>如图所示v4v5v3v2v10111110100110101010110010AG=G的邻接矩阵为：0100110101010110010111110AG’=G’的邻接矩阵变为：v3v4v2v1v5若G’中结点编序如下图所示22十月2022邻接矩阵例7.3.1图G=<V,E>30十月2022邻接矩阵例7.3.2图G=<V,E>如图所示0101001010010100AG=G的邻接矩阵为：v1v3v4v2若G’中结点编序如下图所示v4v3v1v20100001010011100AG’=G’的邻接矩阵变为：22十月2022邻接矩阵例7.3.2图G=<V,E>30十月2022邻接矩阵对于仅仅结点编序不同的图，是同构的

它们的邻接矩阵也是相似的G1

G2 存在置换矩阵P，使得

AG2=P-1AG1P对于由结点编序不同引起的邻接矩阵的不同将被忽略

任取图的任意一个邻接矩阵作为该图的矩阵表示22十月2022邻接矩阵对于仅仅结点编序不同的图，是同构30十月2022邻接矩阵图G的邻接矩阵AG可以展示图G的一些性质：若邻接矩阵AG的元素全是零，则G是若邻接矩阵AG的元素主对角线上全是0，其他元素全是1，

则G是无向图G的邻接矩阵AG是在简单有向图的邻接矩阵中，第i行元素是由结点vi出发的弧所确

定的，故第i行元素为1的数目，等于vi的，即d+(vi)=aik

第j列元素是由到达结点vj的弧所确定的，故第j列元素为1的数目，

等于vj的，即d-(vj)=akjn

k=1n

k=1零图连通的简单完全图对称矩阵出度入度22十月2022邻接矩阵图G的邻接矩阵AG可以展示图G的30十月2022邻接矩阵定理：设A为简单图G的邻接矩阵，则An中的i行j列的元素

aijn等于G中联结vi和vj的长度为n的链（路）的数目证明：1)当n=1时，An=A1=A，定理成立2)设n=k时定理成立，即aijk为G中联结vi和vj的长度为k的链的数目3)当n=k+1时，An=Ak+1=Ak×A，即aijk+1=airk×

arj

根据假设可知，airk为G中联结vi和vr的长度为k的链的数目，arj为G中联结vr和vj的长度为1的链的数目，因此aijk+1为G中联结vi和vj的长度为k+1的链的数目22十月2022邻接矩阵定理：设A为简单图G的邻接矩阵，30十月2022邻接矩阵例7.3.3图G=<V,E>如图所示，求A,A2,A3,A40101001010010100A=v1v3v4v20110100102010010A2=1011020101201001A3=1202012020120201A4=22十月2022邻接矩阵例7.3.3图G=<V,E>30十月2022邻接矩阵由上面的定理可知：

若要判断图G中结点vi到vj是否可达，可以利用G的邻接矩阵A，

计算A,A2,A3,…,An,…

若发现某个Ar（r是正整数）中aijr

≥1，则表明vi到vj可达。由上一节的定理可知：

对于含有n个结点的图G，任何基本链（路）的长度不大于，

任何基本圈（回路）的长度不大于因此，仅考虑aijr（1≤r≤n）即可n-1n22十月2022邻接矩阵由上面的定理可知：

若要判断图G30十月2022邻接矩阵因此，只要计算Bn=(bij)=A+A2+A3+…+An

Bn

中元素bij表示vi到vj的长度小于等于n的不同路径的总数bij≠

0时，vi可达vj；

若i=j，则说明存在经过vi的回路bij＝

0时，vi不可达vj；

若i=j，则说明不存在经过vi的回路22十月2022邻接矩阵因此，只要计算Bn=(bij)30十月2022邻接矩阵例7.3.4图G=<V,E>如图所示，求Bnv1v3v4v2Bn=A+A2+A3+A40110100102010010+1011020101201001+1202012020120201+0101001010010100=2424133233341312=22十月2022邻接矩阵例7.3.4图G=<V,E>30十月2022邻接矩阵问题：如何判断某无向图G是否为连通图？求出Bn=(bij)=A+A2+A3+…+An若有某个bij为0(i≠j)，则说明结点vi和vj处于不同的连通分图中，图G为分离图；

否则G为连通图（即非主对角线上元素都不为0）。思考：主对角线上元素bii表示什么？22十月2022邻接矩阵问题：如何判断某无向图G是否为连30十月2022可达矩阵若关心的只是结点间的可达性或结点间是否有链存在

至于存在多少条链以及长度为多少无关紧要

则可以使用可达矩阵P=(pij)来表示结点间的可达性：pij= 1, vi

可达vj

0, vi

不可达vj22十月2022可达矩阵若关心的只是结点间的可达性或结点30十月2022可达矩阵可达矩阵P=(pij)的计算之一：通过Bn

可令Bn=(bij)=A+A2+A3+…+An

再将Bn中非零元素改为1，零元素不变，即可得到P

pij= 1, bij≠

0

0, bij＝

0注意：可达矩阵中，主对角线元素aii只表现了是否存在经过

结点vi的圈，并不描述结点到自身的可达性。22十月2022可达矩阵可达矩阵P=(pij)的计算之一30十月2022可达矩阵例7.3.5图G=<V,E>如图所示，求可达矩阵Pv1v3v4v2Bn=A+A2+A3+A42424133233341312=1111111111111111P=由P可知：G中任意两个结点彼此可达任意结点处都有圈存在

G是强连通图22十月2022可达矩阵例7.3.5图G=<V,E>30十月2022可达矩阵如何判定有向图G是否为强连通图？强连通图G的可达矩阵P中所有元素aij都为1（aii是否必然为1？）如何判定有向图G是否为单向连通图？若P∨PT中非主对角线上元素都为1，则G是单向连通图

（主对角线上元素aii是否必然为1？）如何判定有向图G是否为弱连通图？根据G的基础图G’的邻接矩阵A’，求出G’的可达矩阵P’，

其中非主对角线上元素都为122十月2022可达矩阵如何判定有向图G是否为强连通图？30十月2022可达矩阵可达矩阵P=(pij)的计算之二：布尔矩阵运算

布尔矩阵中的元素，属于集合{0,1}

对布尔矩阵B和C，定义运算：B和C的布尔和：B∨C

(B∨C)ij=bij∨cijB和C的布尔积：B°C

(B°

C)ij=∨(bik∧ckj)n

k=122十月2022可达矩阵可达矩阵P=(pij)的计算之二30十月2022可达矩阵可达矩阵P=(pij)的计算之二：布尔矩阵运算

对邻接矩阵A，记A°A=A(2)A(r-1)

°A=A(r)=(aij(r))

aij(r)=1表示vi

到vj至少存在一条长度为r的链；否则aij(r)=0 由此，可得可达矩阵P =A∨A(2)∨A(3)∨…∨A(n)

=∨A(k)n

k=122十月2022可达矩阵可达矩阵P=(pij)的计算之二30十月2022可达矩阵例7.3.6图G=<V,E>如图所示，求可达矩阵Pv1v3v4v2P=A∨A(2)∨A(3)∨A(4)0110100101010010∨

1011010101101001∨

1101011010110101∨

0101001010010100=1111111111111111=22十月2022可达矩阵例7.3.6图G=<V,E>30十月2022可达矩阵可达矩阵P=(pij)的计算之三：Warshall算法

P18022十月2022可达矩阵可达矩阵P=(pij)的计算之三30十月2022可达矩阵定理：给定简单图G中的任意结点vi

，若P=(pij)是G的可达矩阵，PT=(pji)是P的转置矩阵，则P∧PT的第i行元素为1的列号j为下标的结点vj的集合，与vi构成了强分图证明：若vi

可达vj，则有pij=1若vj

可达vi，则有pji=1，即则有pijT=1因此vi

和vj互相可达，则pij∧pijT=1，即(P∧PT)ij=122十月2022可达矩阵定理：给定简单图G中的任意结点v30十月2022可达矩阵例7.3.7图G=<V,E>如图所示，求可达矩阵Pv3v2v1P=A∨A(2)

∨A(3)011000110=110000011∨

011000110∨

111000111=101101101PT=101000101P∧PT={v1,v3}和{v2}构成G的两个强分图22十月2022可达矩阵例7.3.7图G=<V,E>30十月2022可达矩阵在计算机中的应用二、可达矩阵在计算机中的应用这里给出一个可达矩阵在计算机中的应用——

确定某过程是否为递归(Recursion)22十月2022可达矩阵在计算机中的应用二、可达矩阵在计30十月2022可达矩阵在计算机中的应用设程序P中的过程集合为：P={p1,p2,…,pn}

做有向图G=<P,E>，对于<pi,pj>

E表示pi调用pj若G中包含pi的回路，可以断言pi是递归的由G的邻接矩阵算出的可达矩阵中，

若主对角线上某元素aii=1，则pi是递归的22十月2022可达矩阵在计算机中的应用设程序P中的过程30十月2022可达矩阵在计算机中的应用已知程序P中的过程集合为：P={p1,p2,p3,p4,p5}

各个过程的调用关系如图所示：

p4p5p3p2p10100000010100000000101000其邻接矩阵为：0101101011110110101101011可达矩阵为：22十月2022可达矩阵在计算机中的应用已知程序P中的