离散数学及其应用-09 图论

9.1图的基本概念9.2通路、回路、图的连通9.3图的矩阵表示第九章

图

论。

无序积与多重子集为定义图,需定义无序积与多重子集。（1）令A,B为任意两非空集合,A与B的无序积A&B定义为：A&B={(a,b)|a∈A∧b∈B},则有(a,b)=(b,a)。（2）元素可重复的集合称为多重集合,多重集合不要求其中元素互异。9.1.1图的相关定义令集合A={a,b,c,d},B={0,1},定义A&A,A&B,B&A,B&B。（1）A&A={(a,a),(a,b),(a,c),(a,d),(b,b),(b,c),(b,d),(c,c),(c,d),(d,d)}（2）A&B={(a,0),(a,1),(b,0),(b,1),(c,0),(c,1),(d,0),(d,1)}（3）B&A={(a,0),(a,1),(b,0),(b,1),(c,0),(c,1),(d,0),(d,1)}（4）B&B={(0,0),(0,1),(1,1)}9.1.1图的相关定义图的相关概念

边均为无向边的图称为无向图或简称为图,边均为有向边的图称为有向图(digraph),有向图通常可以用D=<V,E>表示。同时存在有向边和无向边的图称为混合图,本课程对混合图只举一例,不作介绍。

解

图(a)、(b)、(c)由左至右依次为：无向图、有向图和混合图。9.1.1图的相关定义（a）（c）（b）9.1.1图的相关定义

这样一来,可以定义图的基本概念。图的相关定义

图(graph)G=<V,E>是顶点集V与边集E组成的二元组,V和E二者关系如下:（1）V=V(G)为图G的顶点集(vertexset),是非空集合,其中元素称为顶点或节点,可用拉丁字母或希腊字母表示。（2）E=E(G)为图G的边集(edgeset),是顶点集V(G)的无序积V&V或笛卡尔积V×V的多重子集,记作E⊆[V]2,其中E的元素称为边。如果多重子集E⊆V&V,则E中元素为无序对,均为无向边;如果E⊆V×V,则E中元素为有序对,均为有向边。图的相关概念（续）

（1）无向图中,称边e=(u,v)关联顶点u和v,并称u和v为e的端点。（2）有向图中,称边e=<u,v>关联顶点u和v,并称u为e的起点,v为e的终点。同一条边e关联的一对顶点称为邻接点。

当u=v时,边(u,v)和<u,v>均称为环。没有边与之关联的顶点称为孤立顶点。关联同一对顶点的m(m≥2)条边称为重边或平行边，m称为重数。

注意有向重边方向相同,即由相同的顶点有序对定义;因此用V&V或V×V的多重子集定义边集。

9.1.1图的相关定义判断下图中的（a）、（b）图的环与重边。

解

图(a)为无向图,顶点v1定义了环(v1,v1),顶点v2和顶点v3定义两条重边(v2,v3),顶点v3和顶点v4定义两条重边(v3,v4)。

图(b)为有向图,顶点v1定义环<v1,v1>,顶点v2到顶点v3定义两条重边<v2,v3>,注意顶点v3和顶点v4之间两条边<v3,v4>和<v4,v3>方向相反,非重边。

9.1.1图的相关定义（a）（b）图的相关概念（续）图G=<V,E>,按照顶点和边的特征可以定义不同种类的图：（1）当V和E为有限集时,G为有限图,否则称G为无限图。本课程研究有限图。（2）如果图G有n个顶点,m条边,即|V|=n,|E|=m,图G通常可以称为(n,m)图。有n个顶点,即|V|=n的图称为n阶图。（3）n=|V|=1,m=|E|=0的图称为平凡图。n=|V|=0的图为空图,本课程不讨论空图。（4）顶点集非空而边集为空集的图称为零图。（5）当边集E中存在元素重数m≥2时,G为重图。9.1.1图的相关定义图的相关概念（续）

图G=<V,E>,按照其顶点和边的特征可以定义不同种类的图（续）：（6）无重边而且无环的图称为简单图。（7）每对顶点均有边关联的简单无向图称为完全无向图,n阶完全无向图记作Kn,其边数为|E(Kn)|=n·(n-1)/2。（8）在完全无向图的每条边上任取一方向得到的有向图称为竞赛图。（9）每对顶点恰有一对方向相反的边关联的简单有向图称为完全有向图,n阶完全有向图记作Dn,其边数为|E(Dn)|=2·|E(Kn)|=n·(n-1)。9.1.1图的相关定义判断如下组图中的各类图。

解

上图分别展示了：(a)平凡图,(b)零图,(c)简单图,(d)4阶完全无向图K4,(e)4阶竞赛图,(f)4阶完全有向图D4。

注意到完全无向图K4中边的条数mK通过顶点数n=4得到mK=n·(n-1)/2=6。而完全有向图D4顶点数与K4同,任意对顶点之间恰有一对方向相反的有向边,边的条数为mD=2·mK=12。

9.1.1图的相关定义（d）（f）（e）（a）（c）（b）

研究图的过程中通常用到图中顶点所邻接边的条数,对此有若干概念：图的顶点数与计数（1）图G中,顶点v的度(degree)是关联顶点v的边的条数,记作d(v)。注意,顶点v如恰有一环,对d(v)的贡献值为2。（2）度数为1的顶点称为悬挂点,与悬挂点关联的边称为悬挂边。（3）图G的最大度定义为ΔG=max{d(v)|v∈V(G)}。（4）图G的最小度定义为δG=min{d(v)|v∈V(G)}。9.1.2顶点度与计数图的顶点数与计数（续）（5）有向图中,顶点v的出度是顶点作为起点的关联边的条数,记作d+(v);顶点v的入度是顶点作为终点的关联边的条数,记作d-(v);顶点v的度是顶点的出度与入度之和,记作d(v)=d+(v)+d-(v)。（6）有向图D的最大出度定义为Δ+D=max{d+(v)|v∈V(D)}。（7）有向图D的最小出度定义为δ+D=min{d+(v)|v∈V(D)}。（8）有向图D的最大入度定义为Δ-D=max{d-(v)|v∈V(D)}。（9）有向图D的最小入度定义为δ-D=min{d-(v)|v∈V(D)}。（10）每个顶点度均为k的简单无向图称为k-正则图。注意到n阶完全图均为(n-1)-正则图。9.1.2顶点度与计数图的度数列

在任意图G=<V,E>中,令V={v1,v2,…,vn},可定义各顶点对应的度组成的度数列：d(v1),d(v2),…,d(vn)。

如果G为有向图,可进一步分别定义（1）出度数列：d+(v1),d+(v2),…,d+(vn)（2）入度数列：d-(v1),d-(v2),…,d-(vn)

后文将指出,如果所有顶点的度已知,则边数可求。9.1.2顶点度与计数介绍下组图中各图度数列。

解

图(a)无向图为简单图,各顶点v1,v2,v3,v4,v5的度数列为1,3,2,0,2,有孤立顶点v4和悬挂顶点v1,悬挂边e=(v1,v2)。

图(b)无向图无环有重边,各顶点v1,v2,v3,v4的度数列为4,6,3,3,顶点v1,v2间有3条重边,顶点v2,v3间有2条重边。

图(c)无向图为简单图,各顶点v1,v2,v3,v4,v5的度数列为3,2,3,3,1,有悬挂顶点v5,悬挂边(v4,v5)。9.1.2顶点度与计数（a）（c）（b）介绍下组图中各图度数列（续）。

解

图(d)有向图顶点v1和v2间有重边,各顶点v1,v2,v3的度数列为4,3,3,出度数列为3,0,2,入度数列为1,3,1。

图(e)有向图各顶点v1,v2,v3,v4的度数列为3,2,3,2,出度数列为3,1,1,0,入度数列为0,1,2,2。

图(f)有向图顶点v3有环,各顶点v1,v2,v3的度数列为2,2,4,出度数列为2,1,1,入度数列为0,1,3。9.1.2顶点度与计数（a）（c）（b）

9.1.2顶点度与计数

9.1.2顶点度与计数

9.1.2顶点度与计数

令长度为n的非负整数序列an之和为偶数,是否存在以an为度数列的图?为什么?证明

一定有。非负整数序列an之和为偶数,则（1）所有ai均为偶数：ai=2·ki,存在n阶图,其任一顶点vi（1≤i≤n）可以对应序列an的第i个元素,有ki个环,此图恰以an

为度数列。（2）为奇数的ai（1≤i≤n）有偶数个：对任一值为奇数的元素ai有ai=2·ki+1,ki为非负整数;n阶图中对应此类奇数ai的顶点恰有偶数个,令此类顶点各自有ki个环,再将此偶数个顶点成对作一边关联,所得n阶图恰以an为度数列。

9.1.2顶点度与计数

对图G=<V,E>,有的研究聚焦图中某一部分,可以删除原图中的顶点或（和）边来得到,由此引入子图等相关概念。子图相关定义令两图G=<V,E>,G'=<V',E'>同为无向图（有向图）：（1）如果(V'⊆V)∧(E'⊆E),则称图G'为图G的子图,G为G'的母图,记作G'⊆G。（2）如果(G'⊆G)∧((V'⊂V)∨(E'⊂E)),则称图G'为图G的真子图,记作G'⊂G⇔(G'⊆G)∧(G'≠G)。（3）如果(V'=V)∧(E'⊆E),则称图G'为图G的生成子图。（4）如果(G'⊆G)∧(E'=E∩[V']2),则称图G'是由V'导出的导出子图,记作G'=G[V']。（5）如果(G'⊆G)∧(V'=V(E')),则称图G'是由E'导出的导出子图,记作G'=G[E']。9.1.3子图与补图

说明下图的(a)、(b)、(c)、(d)是否为图(a)的子图,说明生成子图以及由部分顶点或边得到的导出子图。9.1.3子图与补图（a）（c）（b）（d）

说明下图的(a)、(b)、(c)、(d)是否为图(a)的子图,说明生成子图以及由部分顶点或边得到的导出子图。解

图(a)为6阶完全无向图G=K6=<V,E>,G是自己的子图,其他图均为G的子图。图(b)包含G的所有顶点和部分边,是G的生成子图。图(b)还是边集E的子集E'={C1C2,C1C6,C2C3,C2C5,C2C6,C3C4,C3C5,C4C5,C5C6}的导出子图G[E']。图(c)是顶点子集V-{C6}的导出子图G[V-{C6}],为5阶完全无向图K5。图(d)是边集E的子集E'={C1C2,C2C4,C2C6,C3C4,C3C6}的导出子图G[E']。9.1.3子图与补图图的补图

图G=<V,E>为n阶简单图,由G的顶点集V和能使G成为完全图的添加边组成的图称为G相对于完全图的补图,简称为G的补图,记作Ḡ。

对于图G=<V,E>和其补图Ḡ,有n=|V|,m=|E|,有以下结论：（1）G与Ḡ互为补图。（2）E(G)∪E(Ḡ)=E(Kn),E(G)∩E(Ḡ)=⌀。（3）完全图Kn与n阶零图互为补图。（4）G与Ḡ是完全图Kn的生成子图。9.1.3子图与补图

说明(a)、(b)、(c)图之间的关系。解

令图（a）为G,图（b）为与G具有相同数量顶点的完全图K6,删除图K6与G共有的边得到G的补图,为图（c）。9.1.3子图与补图（a）（c）（b）

图多种多样,而作为研究对象,图的顶点和边的位置通常并不重要,外观大相径庭的图可以是同一个图。同构

两图G1=<V1,E1>,G2=<V2,E2>,如果存在双射f:V1→V2令：（1）无向图中(vi,vj)∈E1⇔(f(vi),f(vj))∈E2。（2）有向图中<vi,vj>∈E1⇔<f(vi),f(vj)>∈E2。如有重边则重数相同,称图G1与图G2同构（isomorphism）,记作G1≅G2。9.1.4同

构

判断无向图中是否有同构图。解

左中右图具有相同的顶点数,边数和顶点度。中图和右图同构,同构图之间保持图的属性均不变,而左图中找到0个四边形,中图和右图却找到5个。同构图之间顶点的度一致只是必要条件而非充分条件。另外,如果图之间顶点度不保持一致则可以排除为同构图。9.1.4同

构（a）（c）（b）

判断无向图中是否有同构图。解

左中右图具有相同的顶点数、边数。右图无度为3的顶点,而左图和中图各有1个。左图度为3的顶点邻接1个悬挂顶点,中图度为3的顶点却邻接2个悬挂顶点。因此,左中右图任意两图均不同构。9.1.4同

构（a）（c）（b）

判断有向图中是否有同构图。解

左中右图具有相同的顶点数、边数、顶点度。令中图顶点v0,v1,v2,v3依次对应左图中顶点u3,u2,u0,u1则有左图和中图之间保持图的属性均不变,二者同构。右图中可以找到顶点w0出度为3,入度为0,而左图和中图无顶点符合这一条件,右图与左中二图无同构。9.1.4同

构（a）（c）（b）

判断有向图中是否有同构图。解

左中右图具有相同的顶点数、边数(包括环)。左图、中图不同构,二者度为2的顶点分别只有u4,v2,而左图u4出度为0,入度为2,中图v2出度入度均为1。右图与左图中图均不同构,因为左图、中图唯一度为4的顶点u3,v1出度为3,入度为1,而右图唯一度为4的顶点w4出度为1,入度为3。9.1.4同

构（a）（c）（b）9.1图的基本概念9.2通路、回路、图的连通9.3图的矩阵表示第九章

图

论

图论中图的通路与回路,以及图的连通程度等一系列基本概念与重要结论为现实世界中诸多应用提供了理论基础。通路

图G=<V,E>的一条通路（walk）是一个由起点和终点,顶点和边交替组成的序列P:vi1ei1vi2ei2…viseisvis+1,vik∈V,(1≤k≤s)。（1）G为无向图：eik∈E,eik=(vik,vik+1)（2）G为有向图：eik=<vik,vik+1>。

9.2.1通路与回路回路

通路P以顶点vi1为起点,顶点vis+1为终点,并称起点与终点为通路的端点,起点、终点重合时通路称为回路(closedwalk)。通路包含的边数称为通路的长度(length)。

通路P=<VP,EP>是图G的一个非空子图,有VP={vi1,vi2,…,vis,vis+1},EP={ei1,ei2,…,eis}。如果图G为简单图,无重边,则可用顶点序列表示通路P:vi1vi2…visvis+1,忽略边。

注意

通路的长度允许为0,长度为1的回路是环。9.2.1通路与回路

通路和回路中顶点或边是可重复的,针对其是否重复,通路和回路细分定义如下：（1）顶点可重复而边不重复的通路称为简单通路（迹）。（2）顶点不重复的通路称为初级通路（路径）。（3）顶点可重复而边不重复的回路称为简单回路（闭迹）。（4）除起点、终点之外，顶点均不重复的回路称为初级回路（圈）。

易知顶点无重复则边无重复,反之则不然。9.2.1通路与回路如下图所示,为通路、回路、初级通路、初级回路等举例。解

（a）为无向图,有通路v1e1v2e5v4e7v5e6v2e4v3e3v2e6v5,回路v1e2v3e3v2e4v3e3v2e1v1,有简单通路v1e1v2e3v3e4v2,简单回路v2e4v3e3v2e5v4e7v5e6v2,有初级通路v1e1v2e5v4e7v5,初级回路v2e5v4e7v5e6v2。9.2.1通路与回路（a）（b）如下图所示,为通路、回路、初级通路、初级回路等举例。解（续）

（b）为有向图,有通路如v1e1v2e5v4e7v5e6v2e3v3,通路为简单通路,边无重复,其中v1e1v2e5v4e7v5为初级通路;回路v2e5v4e7v5e6v2,顶点无重复则边无重复,因此既是简单回路又是初级回路。9.2.1通路与回路（a）（b）定理

在一n阶图中,若从顶点u到顶点v(u≠v)存在通路,则存在u到v的初级通路,长度不大于n-1。证明

令顶点u到顶点v的通路Puv:vi1ei1vi2ei2…viseisvis+1,vi1=u,vis+1=v,u≠v。若Puv中存在vip=vit,ip,it∈{i1,i2,…,is,is+1},则Puv包含的vipeipvip+1eip+1…vit-1eit-1vit是以vip为起点和终点的回路。删掉Puv中这一回路中的vipeipvip+1eip+1…vit-1eit-1,所得仍为u到v的通路。重复上述过程至所得通路中顶点再无重复,所得P'uv为初级通路,无重复顶点则无重复边,作顶点和边的集合计数运算：n阶图G顶点集|V|=n,V(P'uv)⊆V(Puv)⊆V(G),则有|V(P'uv)|≤n,|E(P'uv)|=|V(P'uv)|-1≤n-19.2.1通路与回路推论

在一n阶图中,任意初级回路的长度不大于n。证明令任意初级回路中一顶点为u,Lu:ue1u1e2u2…es-1us-1esu。Lu长度为s,则删去回路终点得到Lu的子图Pu,us-1:ue1u1e2u2…es-1us-1为u到us-1的初级通路。Lu的长度为包含的边数,边无重复,则有|E(Lu)|=|E(Pu,us-1)|+1≤n。9.2.1通路与回路定理

简单无向图G=<V,E>,δ(G)≥2,存在长度大于或等于δ(G)+1的初级回路和长度大于或等于δ(G)的初级通路。证明

令Pv1,vk:v1e1v2e2…vk-1ek-1vk为G中最长的初级通路,长度为k-1。而d(vk)≥δ(G),G为简单图,无环无重边,则Pv1,vk端点vk有d(vk)个不同邻接点,不包括vk。可以证明端点vk的d(vk)个邻接顶点均在最长初级通路Pv1,vk中。反证,存在vk的某邻接点vk+1∉V(Pv1,vk),则定义边ek=(vk,vk+1)∉Pv1,vk,定义G的初级通路Pv1,vk+1=Pv1,vk∪{ek}:v1e1v2e2…vk-1ek-1vkekvk+1,有Pv1,vk+1长度为k,大于Pv1,vk,与最长初级通路Pv1,vk矛盾。因此端点vk的d(vk)个邻接顶点均出现在最长初级通路Pv1,vk中。9.2.1通路与回路定理

简单无向图G=<V,E>,δ(G)≥2,存在长度大于或等于δ(G)+1的初级回路和长度大于或等于δ(G)的初级通路。证明（续）

最长初级通路Pv1,vk中出现的端点vk所有d(vk)个邻接点中,vk沿着Pv1,vk中顶点经过的初级通路长度最大的邻接点为vt(1≤t<k),则Pv1,vk包含这条以vt和vk为端点的子初级通路Pv1,vk:vtetvt+1et+1…vk-1ek-1vk,而Pv1,vk中出现vk的所有邻接点（否则与vk,vt在Pv1,vk中相距最远矛盾）。9.2.1通路与回路定理

简单无向图G=<V,E>,δ(G)≥2,存在长度大于或等于δ(G)+1的初级回路和长度大于或等于δ(G)的初级通路。证明（续）

定义端点vk与邻接点vt的边ek,t=(vk,vt),则有回路Lvt,vt=Pv1,vk∪{ek,t}:vtetvt+1et+1…vk-1ek-1vkek,tvt为包含vk和vk所有邻接点的初级回路。初级通路Pv1,vk顶点不重复则边不重复,初级回路Lvt,vt（除起始顶点）的顶点不重复边不重复,可以运用集合计数运算,顶点集|V(Lvt,vt)|=|V(Pvt,vk)|,边集|E(Lvt,vt)|=|E(Pvt,vk)|+1。G无环无重边,与vk邻接的d(vk)个顶点均异于vk而均出现在Pvt,vk中且各不相同,vk也出现在Pvt,vk中,|V(Pvt,vk)|≥d(vk)+1≥δ(G)+1,因此|E(Lvt,vt)|=|E(Pvt,vk)|+1=|V(Pvt,vk)|≥δ(G)+1。9.2.1通路与回路推论

简单无向图G=<V,E>,δ(G)≥2,存在长度大于等于3的初级回路。证明（略）9.2.1通路与回路

无向图G中顶点u和顶点v之间存在通路,则称u与v连通。规定任意顶点与自己是连通的,通路长度为0。如果G中任意两顶点均连通,则称G是连通图,否则称G为非连通图或分离图。

易知连通无向图中任意两点之间存在长度小于顶点数n的初级通路。在G=<V,E>上定义二元关系：R={<u,v>|u∈V,v∈V,u和v连通}。

无向图顶点的连通关系自反、对称、传递,是等价关系。则有划分V1⊆V,V2⊆V,…,Vk⊆V,得到导出子图G[V1],G[V2],…,G[Vk]构成图G的连通分支,连通分支数记作P(G)=k。G是连通图⇔P(G)=1。不难证明,连通关系等价类数量为连通分支数。9.2.2图的连通

判断下图G为连通图或非连通图。

图G非连通,有4个连通分支,P(G)=4,为G[{v1,v2}],G[{v3,v4,v5,v6}],G[{v7}],G[{v8}]。注意孤立顶点v7,v8均为各自的连通分支。9.2.2图的连通定理

无向图中只有两个奇度数顶点,则二顶点连通。证明

反证,令两个奇度数顶点u与v不连通,则u∈G[Vi],v∈G[Vj],G[Vi],G[Vj]为G的两个连通分支。图G[Vi]和图G[Vj]中各只有1个奇度数顶点,与任意图中奇度数顶点有偶数个矛盾。9.2.2图的连通定理

连通图G=<V,E>的顶点总可以排序成v1,v2,…,vn,使得对任意1≤i≤n,均有Gi=G[v1,v2,…,vi]连通。证明

数学归纳i。

任意顶点v=v1∈V,G1=G[v1]为平凡图,顶点与自己连通。

i=k<n时,存在序列v1,v2,…,vk,有Gk=G[v1,v2,…,vk]连通。

9.2.2图的连通定理

连通图G=<V,E>的顶点总可以排序成v1,v2,…,vn,使得对任意1≤i≤n,均有Gi=G[v1,v2,…,vi]连通。证明（续）

i=k+1≤n时令G-{v1,v2,…,vk}≠⌀,令u∈G-{v1,v2,…,vk}。G连通,则顶点vk,u连通,有初级通路Pvk,u。令顶点vk+1为沿着顶点vk到u的初级通路Pvk,u:vkek…u中第1个不属于序列v1,v2,…,vk的顶点。则Pvk,u中沿着端点vk到vk+1的子初级通路为Pvk,vk+1:vkek…vk+1⊆G[v1,v2,…,vk,vk+1],由此可知vk与vk+1在G[v1,v2,…,vk,vk+1]中连通,而连通为等价关系,vk与Gk中任一顶点连通,由等价关系传递知Gk+1=G[v1,v2,…,vk,vk+1]连通。9.2.2图的连通

连通无向图中,删除若干顶点或边,得到的子图是否仍然连通是重要的问题。换言之,如何删除最少的顶点或边令连通图不再连通是重要的问题。为衡量这一特征介绍相关概念。割集相关定义无向图G=<V,E>中,（1）若存在非空顶点集V'⊂V令P(G-V')>P(G),任意非空顶点集V″⊂V'均有P(G-V″)=P(G),则称V'为G的一个点割集。如果G的某个点割集只有一个顶点,则称此顶点为割点。（2）若存在非空边集E'⊂E令P(G-E')>P(G),任意非空边集E″⊂E'均有P(G-E″)=P(G),则称E'为G的一个边割集。如果G的某个边割集只有一条边,则称此边为割边(桥)。

9.2.2图的连通注意

平凡图和n阶零图无法通过删除顶点来扩大其连通分支个数,因此无点割集;二者均无边,因此无边割集。非平凡n阶完全图删除一个顶点只能得到n-1阶完全图或平凡图,只需注意到非平凡n阶完全图的边数m=n·(n-1)/2,顶点度数均为d(v)=n-1;删除任意一顶点得到的图有边数m'=(n-1)·(n-2)/2条边,顶点度数均为d'(v)=n-2,或仍为完全图,或成为平凡图,因此无点割集。

一般来说,图的点割集和边割集不唯一。连通无向图G=<V,E>有点割集V'则P(G-V')≥2;有边割集E'则P(G-E')=2。9.2.2图的连通点连通度与边连通度连通无向图G=<V,E>的点连通度κ(G)(vertexconnectivity)和边连通度λ(G)(edgeconnectivity)定义为:（1）κ(G)=min{|V'||V'是G的点割集或令G-V'成为平凡图}。κ(G)≥k则称G是k-连通的。（2）λ(G)=min{|E'||E'是G的边割集}。λ(G)≥k则称G是k-边连通的。

平凡图G或n阶零图G无点割集,无边割集,规定κ(G)=λ(G)=0。此外,规定非连通图G有κ(G)=λ(G)=0。非平凡n阶完全图Kn删除n-1个顶点得到平凡图,κ(Kn)=n-1。Kn任意两顶点邻接,d(v)=n-1,λ(Kn)=n-1。如果G有割点,则κ(G)=1;G有割边则λ(G)=1。9.2.2图的连通定理

图G有κ(G)≤λ(G)≤δ(G)。证明

（略；参考《离散数学及其应用》,168-170页）

9.2.2图的连通

阐述右图G的点与边连通度。解

G=<V,E>为连通图,删除v4可得到2个连通分支,为子图G[{v1,v2,v3}]和子图G[{v5,v6,v7,v8}],则v4为割点。G最少删除3条边达到非连通,例如删除(v1,v2),(v1,v3),(v1,v4),可得2连通分支,为孤立顶点v1和子图G[V-{v1}]。κ(G)=1,λ(G)=3。因此,图G是1-连通的,而不能是大于等于2-连通的;图G是3-边连通,因此可以是1-边连通和2-边连通的。9.2.2图的连通有向图的连通

有向图D中,如果从顶点u到顶点v存在通路,则称顶点u可达顶点v。规定任意顶点到自己是可达的。如果u可达v同时v可达u,则称u与v相互可达。（1）如果简单有向图D中任意两顶点均相互可达,则称D是强连通图;（2）如果任意两顶点至少从一顶点可达另一顶点,则称D是单向连通图;（3）如果忽略D中边的方向,D是连通无向图,则称D为弱连通图。

强连通图是单向连通图和弱连通图,单向连通图是弱连通图。

9.2.2图的连通定理

有向图D强连通的充分必要条件是D中有一条包含每一个顶点至少一次的回路。证明

令顶点集V,|V|=n,令二元关系viRvj⇔vi可达vj⇔Pvi→vj=viei0vi1ei1…vikeikvj。易知可达关系R自反,传递。充分条件:如果存在包含所有顶点都至少出现一次的回路Lv1→v1=v1Rv2R…RvnRv1,则∀vi,vj∈V,1≤i<j≤n由可达关系R的传递知viRvi+1,vi+1Rvi+2,…,vj-1Rvj⇒viRvj。Lv1→v1为回路,有vjRvj+1,vj+1Rvj+2,…,vnRv1,v1Rv2,…,vi-1Rvi⇒vjRvi。vi则与vj相互可达,则D强连通。9.2.2图的连通定理

有向图D强连通的充分必要条件是D中有一条包含每一个顶点至少一次的回路。证明（续）必要条件:如果D强连通,则∀vi,vi+1∈V,1≤i<n,viRvi+1,所以存在通路Pvi→vi+1,另有vnRv1,所以存在通路Pvn→v1,令Pv1→v2∪Pv2→v3∪…∪Pvn-1→vn∪Pvn→v1,则得到回路Lv1→v1,其中所有顶点都至少出现一次。9.2.2图的连通定理

有向图D单向连通的充分必要条件是D中有一条包含每一个顶点至少一次的通路。证明（略；参考《离散数学及其应用》,171页）9.2.2图的连通强分图/单向分图/弱分图

简单有向图D中,如果D'⊆D是D的极大强连通子图,则称D'为D的一个强分图。如果D'⊆D是D的极大单向连通子图,则称D'为D的一个单向分图。如果D'⊆D是D的极大弱连通子图,则称D'为D的一个弱分图。注意

对子图某一特征,如强连通,单向连通,弱连通,加以极大这一修饰的含义是,如果子图再加入母图中子图之外其他任何顶点,则所得导出子图不再具有这一特征。9.2.2图的连通

判断有向图D是否连通。解

有向图D非连通,从左向右依次有子图D1=D[{v1,v2,v3,v4,v5,v6,v7}],D2=D[{v8,v9}],D3=D[{v10,v11,v12}]。子图D1内各顶点均相互可达,强连通;D1是D的极大强连通子图,为强分图。D2内顶点v8可达v9而v9不可达v8,单向连通,D2为单向分图。D3内顶点v10,v12相互均不可达,而忽略方向为连通无向图,弱连通,D3为弱分图。9.2.2图的连通定理

简单有向图D=<V,E>中每个顶点在且只在一个强分图中。证明

有向图任意两顶点强连通关系即相互可达,相互可达关系自反、对称、传递,是等价关系。

强连通关系可将图D作一划分,每个顶点在且只在一个划分块中。任一划分块中顶点组成的导出子图强连通,加入其他划分块内任意顶点均不再强连通,则为D的强分图。9.2.2图的连通

图的应用问题离不开对其顶点之间不同通路的量化描述,如果二顶点之间有通路,则用距离量化衡量二者之间长度最短的通路。二顶点距离

图G=<V,E>中从顶点u到顶点v存在通路,则从u到v长度最短的通路称为u到v的短程线,短程线的长度称为u到v的距离,无向图这一距离记作d(u,v),