第七章-图的基本概念

第五章图的基本概念图论起源于1736年欧拉(Enler)的第一篇图论论文,解决了“哥尼斯堡的七桥问题”。在哥尼斯堡的匹格河上有七座桥。

陆地岛屿岛屿陆地哥尼斯堡七桥问题如何不重复地走完七桥后回到起点？

。。。。ABCD当时人们热衷于这样的游戏：设想从任一个地方出发通过每座桥一次且仅一次后回到原地,这是否可能?但多次实践都发现不行1727年欧拉的朋友向欧拉提出了这个问题是否有解？1736年欧拉用图论的方法解决了这个问题,写了第一篇图论的论文,成为图论的创始人。后来称此问题为哥尼斯堡七桥问题。在图a中,用边表示桥,顶点表示岛屿和河的两岸,便得到一个图,如图b所示。很显然,通过哥尼斯堡七座桥中每一座一次且仅一次的问题等价于在右图(b)中找一条闭链,使得它的每一边出现一次且仅一次,也就是如何一笔画的问题。但在此之后100年间，没有大的进展。直到Kirchhoff(克希霍夫)用树的理论解决了电网络问题，这些结果引起了人们的重视,图论的研究进入了一个发展时期,在此期间,出现了两个著名的问题:四色问题和Hamilton回路问题,成为不少数学家的研究目标。但在19世纪后期和二十世纪初，图论的研究再次处于停顿状态。直到1920年,科尼格(Konig)撰写了许多图论方面的论文。在1936年科尼格(Konig)发表了第一本图论书籍《有限图与无限图理论》,总结了200年来图论研究的主要成果。此后的50年,图论经历了一场爆炸性的发展,成为数学科学中一门独立的学科。主要分支有图论、超图理论、极值图论、算法图论、网络图论和随机图论等。几十年来图论在理论上和应用上都得到很大的发展,特别是在近30多年来由于计算机的广泛应用而又得到飞跃的发展。在计算机科学、运筹学、化学、物理和社会科学等方面都取得了不少成果，对计算机学科中的操作系统研究、编译技术、人工智能和计算机网络等方面都有广泛的应用。这里主要讨论图的基本概念和算法,为今后的学习和研究打下基础。

概述图论是一个应用十分广泛而又极其有趣的数学分支。物理、化学、生物、科学管理、计算机等各个领域都可找到图论的足迹。本章主要介绍图论的一些基本知识、图论中常用的初等方法。试图在抽象理论和具体编程之间为同学们架设一座桥梁。为了让大家知道图论主要讲些什么，我们先举几个例子。例7.1图7—1画的是一个“图”,当然究竞什么叫做“图”,以后还要仔细讲。这里只要先记住,我们研究的图,指的是由顶点和线组成的图形。V10走哪条路最近？这个问题通常叫做最短路径问题。这是一个有很大现实意义的问题,它不仅出现在各种运输问题中,而且在电路设计等问题中也有用。因为这种问题研究的是从V1到V10的所有路径中,哪一条路最短?因此它是一个极大极小问题,即极值问题,而它又和一个“图”密切联系着,因此这种问题就叫做图论中的极值问题。

我们先把图7—1看成是一个公路,V1,V1,…,V10是一些城镇,每条线旁边的数字代表这一段公路的长度。现在问要从V1把货物运到图7-1其公路网的一个站点或者至少破坏敌人哪几个站点,就可摧毁敌方整个运输线。这类问题称为图的连通性问题。原来的公路网,任意两个站点之间互相可达,这样的图称作连通图。一旦删去一些(或一个)点以及和它们关联的边时,这张图就不再成为一张完整的连通图了。军事指挥中这类问题就很多。图7-1例7.2还是把图7—1看成公路网,V1,V1,…,V10看成公路网的一个站点,若这个公路网目前被敌方占领。请分析一下,能否仅破坏例7.3

飞行大队有若干个来自各地的驾驶员,专门驾驶一种型号的飞机,这种飞机每架有两个驾驶员。由于种种原因,例如相互配合的图7-2问题,有些驾驶员,不能在同一架飞机上飞行,问如何搭配驾驶员才能使出航的飞机最多。

为简单起见,假设有10个驾驶员,图7-2中的V1,…V10就代表这10个驾驶员。如果两个人可以同机飞行,就在代表他们两个之间连一条线;两个人不能同机飞行,就不连。例如V1和V2可以同机飞行,而V1和V3就不行。图7-2图中没有公共端点的一组线叫做一个“匹配”。上面问题就成为:如何找一个包含最多线的匹配?这个问题叫做图的最大匹配问题。请大家试试看，能不能从图7—2中找出一个包含4条线的匹配,再试试能不能找到包含5条线的匹配。像上述例子那样,将实际生活中的事物分析转化为图论问题的实例还很多,后面还要讲,这里就不多介绍了。画了这个图后,就可以研究搭配飞行员的问题了。图7—2中画的3条租线就代表了一种搭配方案。由于一个飞行员不能同时派往两架飞机。因此任何两条粗线不能有公共的端点,把一个

v4v2v3e1e3e2e4e5e6e7图论研究的对象是图,什么是图呢?什么是图？从前面我们可以看出：一个图一般用图形表示。它可以由两部分组成：一部分是一些点，我们称其为结点，如下图中的v1,v2,v3,v4诸点；另一部分是连接这些点的线，我们称其为边，如下图中的e1,e2,e3,e4,e5,e6,e7,。

图G是由非空结点集合V={v1,v2,…,vn}以及边集合E={e1,e2,…,en}所组成，其中每条边可用一个结点对表示之，这样的一个图G可用示为

G=＜V，E＞v1边。例如V1与V2之间有两条边。若连接两个顶点的边有多条,则这些边称之为平行边。V2与V3之间有一条边,V2与V4之间没有边……等等。V1与V1本身也有边相连,这样的边叫做环。当然,也可能出现某顶点与图中除它外的每一顶点均不相连的情况,这种顶点称为孤立点,例如与V11

。也就是说图有若干个不同的点V1,…,V11,称之为顶点。这些顶点中有一些是用直线段或曲线段连接的,这些直线段和曲线段称作例7.4有四座城市：v1,v2,

v3,v4，其中v1与v2间

v1与v4间；v2与v3间有直达长话线相联，将此事实用图的方法表示之。解：图中的结点集为

V={v1,v2,

v3,v4}图中的边集为E={e1,e2,

e3}其中，e1=(v1,v2)e2=(v1,v4)

e3=(v2,

v3)

这个图可用G=<V,E>表示v1v2v3v4e1e3e2无向图：图中所有的边均为无向边例7.5有四个程序：v1,v2,

v3,v4，它们间有一些调用关系：v1能调用v2；v2能调用v3；v3能调用v4，将此事实用图的方法表示之。解：图中的结点集为

V={v1,v2,

v3,v4}图中的边集为E={e1,e2,

e3}其中，e1=(v1,v2)e2=(v2,v3)

e3=(v2,

v4)

这个图可用D=<V,E>表示v1v2v3v4e1e3e2有向图：图中所有的边均为有向边第五章图的基本概念定义5.1

一个无向图G是一个二元组<V,E>，即G=<V,E>，其中(1)V≠φ称为顶点集,其元素称为顶点或结点(2)E称为边集,它是无序积V&V的多重子集，其元素称为无向边，简称为边。设A,B为任意的两个集合,称{(a,b)|a∈A∧b∈B}为A与B的无序积,记作A&B.元素可以重复出现的集合称为多重集合，某个元素重复出现的次数称为该元素的重复度。例如在集合{a,b,b,a,a}中，a,b的重复度分别为3,2.定义5.2

一个有向图是一个有序的二元组<V,E>,记作D,其中(1)V≠,称为顶点集，其元素称为顶点或结点。(2)E称为边集，它是笛卡儿积V×V的多重子集,其元素称为有向边，简称为边。用图形表示无(有)向图时，常用小圆圈或实心点表示顶点，用顶点之间的连线表示无向边，用有方向的边表示有向边。注意到无向图与有向图集合表示的异同了吗？例5.6

画出下列图形。G=<V,E>,其中V={v1,v2,v3,v4,v5},E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v1,v5),(v2,v5),(v4,v5)}。(2)D=<V,E>,其中V={a,b,c,d},E={<a,a>,<a,b>,<a,b>,<a,d>,<c,d>,<d,c>,<c,b>}。例5.7

画出下列图形。G=<V,E>,其中V={v1,v2,v3,v4,v5},E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v1,v5),(v2,v5),(v4,v5)}。v1v2v3v4v5e1e2e3e4e5e6例5.8

画出下列图形。(2)D=<V,E>,其中V={v1,v2,v3,v4},E={<v1,v1>,<v1,v2>,<v2,v1>,<v1,v4>,<v3,v4>,<v4,v3>,<v3,v2>}。v1v2v3v4e1e2e3e4e5e6e7与图有关的概念和规定设G=<V,E>为一有向图或无向图。V、E分别表示G的顶点集、边集，|V|、|E|分别表示G的顶点数、边数。若|V|=n,则称G为n阶图。(2)若|V|、|E|均为有限数，则称G为有限图这是本书讨论的重点。(3)在图G中，若E=

,则称G为零图.此时若|V|=n，则称G为n阶零图，记作Nn。若|V|=1，则称G为平凡图。(a)图(b)零图(c)完全图没有任何边的图称为零图；只有一个点的图称为平凡图；任意两点之间都有边的图称为完全图。定义5.3

设G=<V,E>为无向图，ek=<vi,vj>∈E,则称vi,vj为ek的端点，ek与vi或ek与vj是彼此关联的。无边关联的顶点称为孤立点。若一条边所关联的两个顶点重合，则称此边为环。vi≠vj，则称ek与vi或ek与vj的关联次数为1，若vi=vj，则称ek与vi的关联次数为2；若vi不是ek的端点，则称ek与vi的关联次数0。例7.4:

P156图7.1(1)中,e2=(v1,v2),与v1,v2的关联次数均为1,v5是孤立点,e1是环,e1与v2的关联次数为2。定义5.4设G=<V,E>为无向图，vi,vj∈V,ek,el∈E,若存在一条边e以vi,vj端点，即e=(vi,vj)则称vi与vj是彼此相邻的。简称相邻的。(2)若ek与el至少有一个公共端点，则称ek与el

是彼此相邻的。简称相邻的。设D=<V,E>为有向图,vi,vj∈V,ek,el∈E,若ek=<vi,vj>,除称vi,vj是ek的端点外,还称vi为ek的始点，vj为ek的终点，并称vi邻接到vj,vj

邻接于vi,若ek的终点为el的始点,称ek与el是相邻例7.5:

P156图7.1(2)中,e2=<v1,v2>,v1是e2的始点,v2是e2的终点,v1邻接到v2,v2邻接于v2定义5.5

设G=<V,E>为一无向图，vi∈V,称vi作为边的端点的次数之和为vi的度数，简称为度，记作d(vi).

设D=<V,E>为一有向图，vj∈V,称vj作为边的始点的次数之和,为vj的出度，记作d+(vj);称vj作为边的终点的次数之和,为vj的入度，记作d-(vj);称d+(vj)+d-(vj)为vj的度数，记作d(vj).例5.6:P156图7.1(1)中,d(v1)=4,d(v2)=4,d(v5)=0,……,在图(2)中,d+(v1)=2,d-(v1)=1d(v1)=3,d+(v2)=1,d-(v2)=3,d(v2)=4，……abcdd1a1b1c1d(a1)=0;d(c)=1;d(a)=2;d(c1)=3;也就是说：一个图中以v为结点的边的条数称为该结点v的度，记为d(v)。如：例5.9

在上图(1)中,d(v1)=4,d(v2)=4,d(v5)=0,……,在图(2)中,d+(v1)=2,d-(v1)=1,d(v1)=3d+(v2)=1,d-(v2)=3,d(v2)=4,……v1v2v3v4v5e1e2e3e4e5e6(1)v1v2v3v4v5e1e2e3e4e5e6e7e8(2)称度数为1的顶点为悬挂顶点,它所对应的边为悬挂边。例

P119图5.1(a)中,v4为悬挂顶点,e6为悬挂边在无向图G中,令△(G)=max{d(v)|v∈V(G)}

(G)=min{d(v)|v∈V(G)

}

称△(G)和

(G)分别为G的最大度和最小度。在有向图D中,可类似定义△(D)、

(G)。另外,令

△+(G)=max{d+(v)|v∈V(D)

}

+(G)=min{d+(v)|v∈V(D)

}

△-(G)=max{d-(v)|v∈V(D)

}

-(G)=min{d-(v)|v∈V(D)

}分别为D的最大出度、最小出度、最大入度、最小入度。简记作△、、△+、

+、△-、

-。v1v2v3v4v5e1e2e3e4e5e6(1)v1v2v3v4v5e1e2e3e4e5e6e7e8(2)例5.10

在上图(1)中,最大度△=4,最小度=0,在图(2)中,最大度△=4,最小度=2,最大出度△+=3,最大入度△-=3最小出度

+=1,最小入度

-=0第五章图的基本概念定理5.1——握手定理

设G=<V,E>为无向图或有向图，V={v1,v2,…,vn},|E|=m(m为边数)则证明：G中每条边（包括环）均提供2个端点，故在计算各顶点度数的和时，每条边均提供2度，m条边共提供2m度。=2m即每个顶点度数之和等于边数的2倍。推论

任何图(无向的或有向的)中，度为奇数的顶点个数为偶数定理5.2——握手定理

设D=<V,E>为任意有向图，

V={v1,v2,…,vn},|E|=m,则证明：D中每条边（包括环）均关联两个顶点，故在计算各顶点度数的和时，每条边均提供2度，即1个出度和1个入度，m条边则提供m个出度，m个入度，共2m度。设V={v1,v2,…,vn}为图的顶点集,称(d(v1),d(v2),…d(vn))为G的度数序列

例5.11在上图①中的度数序列为（4,4,3,1,0)在上图②中的度数序列为（3,4,3,4,2)v1v2v3v4v5e1e2e3e4e5e6(1)v1v2v3v4v5e1e2e3e4e5e6e7e8(2)例5.12①(3,3,2,3),(5,2,3,1,4)能成为图的度数序列吗？为什么？②已知图G中有10条边,4个3度顶点,其余顶点的度数均不大于2,问G中至少有多少个顶点?为什么？解:①由于这两个序列中,奇数个数均为奇数,由握手定理的推论可知,它们都不能成为图的度数序列。

②图中边数m=10,由握手定理可知,G中各顶点度数之和为20，4个3度顶点占去12度，还剩8度若其余全是2度顶点,还需要4个顶点来占用这8度，所以G至少有8个顶点。考察下列各图的度序列。abcd(1)2,6,3,3(2)入度序列：3,1,2,2出度序列：1,2,3,2（1）（2）v1v2v3v4v5e1e2e3e4e5e6v1v2v3v4v5e1e2e3e4e5e6e7e8定义5.6

在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数。例在左上图中e4与e5是平行边v1v2v3v4v5e1e2e3e4e5e6v1v2v3v4v5e1e2e3e4e5e6e7e8定义5.6在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点与终点相同(即方向相同)，则称这些边为平行边。例如在右上图中e3与e4是平行边,e7与e8不是平行边（因为e7与e8方向不同）如：。a。be。d。c。含平行边的图称为多重图，既不含平行边也不含环的图称为简单图。如：K3K6考虑：Kn的边数为？？？答案：m=Cn2=n(n-1)/2定义5.7

设G为n阶无向简单图，若G中每个顶点均与其余的n-1个顶点相邻，则称G为n阶无向完全图，简称n阶完全图，记作Kn(n≥1)。∵Cn2=n!2!(n-2)!如：3阶有向完全图考虑：n阶有向完全图,？？？答案：n(n-1)定义5.7-2

设D为n阶有向简单图，若D中每个顶点都邻接到其余的n-1个顶点，又邻接于其余的n-1个顶点，则称D为n阶有向完全图。

完全图任意两点之间都有边的图称为完全图。定义5.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的真子图。

若G`G且V`=V，则称G`为G的生成子图。

V1

V且V1≠,以V1为顶点集,以两端点均在V1中的全体边为边集的G的子图,称为V1导出的导出子图。E1E且E1≠,以E1为边集,以E1中边关联的顶点的全体为顶点集的G的子图,称为E1导出的导出子图abcda1b1abcdd1a1b1c1abcdd1b1abcdd1a1b1c1母图真子图V'V或E'E生成子图G'G且V'=V导出子图V'V或E'

E例5.14在上图中,(2),(3)均是(1)的子图。(2)是顶点子集

v1,v2的导出子图，也是边子集

e4,e5的导出子图,(3)又是边子集

e1,e3,e4的导出子图。v1v2v3v4v1v2v1v2v3v4e1e2e3e4e5e4e5e1e3e4(1)(2)(3)例5.15在上图中,(5),(6)均是(4)的子图。(5)是生成子图，也是边子集

e1,e3的导出子图,(6)是边子集

e1的导出子图。注意：每个图都是本身的子图。v1v2v3v1v2v1v2e1e3e4e3e1(4)(5)(6)e2v3v1e1(1)abdce1e2e3e4e5e6bdce3e4e5(2)(3)母图同时也是(1)的生成子图G=<V,E>子图、真子图V={b,c,d}E={e3,e4,e5}子图、真子图生成子图V={a,b,c,d}E={e2,e3,e4,e5}cabde3e4e5e2例5.16：判断下列各图的母子关系。如：

(1)(2)定义5.9

设G=<V,E>为n阶无向简单图,以V为顶点集，以所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作G。

(1)(2)例5.17

在下图中,(1)是(2)的补图,当然(2)也是(1)的补图,就是说,(1),(2)互为补图同样,(3),(4)互为补图(3)(4)定义5.10

设G1=<V1,E1>,G2=<V2,E2>为两个无(有)向图，若存在双射函数f:V1→V2,于

vi,vj∈V1,(vi,vj)∈E1(<vi,vj>∈E1)

(f(vi),f(vj))∈E2(<f(vi),f(vj)>∈E2)并且(vi,vj)(<vi,vj>)与(f(vi),f(vj))(<f(vi),f(vj)>)重数相同，则称G1与是G2同构的，记作G1≌G2。

也就是说:两个图G1=<V1,E1>,G2=<V2,E2>,如果它们的节点间存在一一对应关系（双射），而且这种对应关系也反映在表示边的结点对中,(如果是有向边则对应的结点对还保持相同的顺序),则称此两图是同构的。如何判断两个图是否同构呢？答案：迄今为止还没有有效的算法。根据定义，则(1)结点数目相等(2)边数相等(3)度数相同的结点数目相同。但这仅仅是G1≌G2的必要条件。注意：我们把同构的图看成是一个图

还记得代数系统同构吗？两个代数系统同构满足的3个条件：①它们必须是同一类型的②两个集合间的元素是一一对应的③它们的运算定义法则是相同的(1)-G(2)-G'例5.18

在下图中,(1)和(2)结点集的元素一一对应v1b,

v2d,v3e,v4c,v5a;边集(v1,v2)(b,d),

(v2,v3)(d,e),(v3,v4)(e,c),(v4,v5)(c,a),(v5,v1)(a,b);度数相同的结点数目相同

∴是同构的。同理(3)和(4)也是同构的(3)-G(4)-G'av3v1v2v4v5edcbv1v2v3v41243

。。。。例5.19：试证下列两个有向图G1=<V1,E1>和G2=<V2,E2>同构？abcd。。。。v1G1v2v3v4G2证明:由图可知,V1=a,b,c,d和V2=

v1,v2,v3,v4

令映射g:V1

V2

即结点和边的对应关系分别为g(a)V1,g(b)V2,g(c)V3,g(d)V4,<a,b>

<v1,v2>,<a,d>

<v1,v4><b,c>

<v2,v3><d,c>

<v4,v3>显然,映射g是双射,G1和

G2同构。

。。。。。。2-a

。。。。。。2-b一般说来，证明两个图是同构的并非是件轻而易举的事情，往往需要花些气力，常常用下述三个判断同构必要条件进行判断。(1)结点数目相等(2)边数相等(3)度数相同的结点数目相同。例5.20：判断两组图是否同构？§7.2通路、回路、图的连通性考察下图中开始于结点1结束于结点3的通路是：1234P1:(1,2,3),P2:(1,4,3)P3:(1,2,4,3)P4:(1,2,4,1,2,3)P5:(1,2,4,1,4,3)P6:(1,1,2,3)有向图中各边全不相同的通路叫简单通路。

有向图中各点全不相同的通路叫初级通路。一条初级通路一定是简单通路,反之不然。如P5:是简单通路但不是初级通路。P1,P2,P3是初级通路,(当然也是简单通路）P4,P6则即非初级通路亦非简单通路§5.2通路、回路、图的连通性图中一条通路如果其起始结点与终止结点相同则称此通路为回路。可见回路是一种特殊的通路。1234图中各边全不同的回路叫简单回路，各点全不同的叫初级回路。C1:(1,1),C2:(1,2,1)C3:(1,2,3,1)C4:(1,4,3,1)C5:(1,2,3,2,1)C6:(1,2,3,2,3,1),

C1,C2,C3,C4是初级回路,(当然也是简单回路),C5是简单回路但非初级回路,而C6既非初级回路亦非简单回路。§5.2通路、回路、图的连通性定义5.11

给定图G=<V,E>,设G中顶点与边的交替序列

Γ=v0e1v1e2…

elvl，若Γ满足如下条件：vi-1和vi

是ei的端点(在G是有向图时,要求vi-1

是ei的始点,vi

是ei的终点),i=0,1,…,l,则称Γ为顶点v0到vl的通路。v0和vl分别称为此通路的起点和终点,Γ中边的数目l称为Γ的长度。若v0=vi，则称此通路为回路。若Γ中所有边各异，则称Γ为简单通路若回路中所有边各异，则称Γ为简单回路。§5.2通路、回路、图的连通性若通路中所有顶点v0,v1,

…

,vl各异，所有边也各异，则称此通路为初级通路或一条路径。若回路中，除v0=vi外，其余顶点各不相同，所有边也各异，则称此回路为初级回路或圈。有边重复出现的通路称为复杂通路，有边重复出现的回路称为复杂回路。由定义可知，初级通路（回路）是简单通路（回路），但反之不真。

一般说来，通路、回路是图的子图。v0v1v2v3v4v0v1v2v7v3v4v5v6v8v0=v5v1v2v3v4v0=v8v1v2v6v3v4v5v71234图(1)为v0到v4的长为4的初级通路(路径)图(2)为v0到v8的长为8的简单通路图(3)为v0到v5(=v0)的长为5的初级回路图(4)为v0到v8(=v0)的长为8的简单回路

在无向图中,环和两条平行边构成的回路分别为长度为1和2的初级回路(圈)v0v1v2v3v4v0v1v2v7v3v4v5v6v8v0=v5v1v2v3v4v0=v8v1v2v6v3v4v5v71234图(1)为v0到v4的长为4的初级通路(路径)图(2)为v0到v8的长为8的简单通路图(3)为v0到v5(=v0)的长为5的初级回路图(4)为v0到v8(=v0)的长为8的简单回路

在有向图中,环和两条方向相反边构成的回路分别为长度为1和2的初级回路(圈)定理5.3

在n阶图G中，若从顶点vi到vj(vi≠vj)存在通路，则从vi到vj存在长度小于或等于（n-1）的通路。推论在n阶图G中，若从顶点vi到vj(vi≠vj)存在通路，则vi到vj一定存在长度小于或等于n-1的初级通路（路径）。定理5.4

在一个n阶图G中，若存在vi到自身的回路，则一定存在vi到自身长度小于或等于n的回路。推论在一个n阶图G中，若存在vi到自身的简单回路，则一定存在长度小于或等于n的初级回路。(e2),(e3,e4,e2),(e3,e5,e6,e10,e2),(e3,e5,e6,e7,e1)是从C到B的4个有向路。这4条有向路只有第一条，第四条是简单的；ABCDEFe1e2e3e4e5e6e7e9e8e10(e3,e4),(e3,e5,e6,e10),(e8),(e9)是4条有向回路;有向图G中,从B到其它任意点都没有有向路。例：求下图回路数和C到B的通路

要求各找出4个以上图的连通性一个无向图(有向图忽略其方向)G=<V,E>,如果它的任何两点均是可达的,则称图G为连通图，否则称为非连通图v1v2v3v5v4v1v2v3v4v5v6v1v2v3v4v5v6左图和中图均是连通图，但右图则是非连通图，因为结点v1,v2,v3与结点v4,v5,v6间是不可达的。定义5.12

在一个无向图G中，若从顶点vi到vj存在通路(当然从vj到vi也存在通路),则称vi与vj是连通的。规定vi到自身总是连通的。在一个有向图D中，若从顶点vi到vj存在通路，则称vi可达vj。规定vi到自身总是可达的设vj,vi为无向图G中任意两点,若vj与vi是连通的,则称vj与vi之间长度最短的通路为vj与vi之间的短程线,并称为vj与vi之间的距离,记作d<vj,vi>,当vj不可达vi时,规定d<vj,vi>=∞距离有以下性质：1.d<vj,vi>≥0，vj=vi时，等号成立。2.在无向图中还有对称性:d(vj,vi)=d(vj,vi)3.满足三角不等式：

d<vj,vi>+d<vj,vk>≥d<vi,vk>v3

。。。。。v1e4v2v4v5e1e3e5e6e7v3

。。。。。v1v2v4v5e1e3e5e6连通图分离图定义5.14

若无向图G是平凡图或G中任何两个顶点都是连通的，则称G为连通图，否则称G为非连通图或分离图。

显然，一个图G是连通的，当且仅当G中任意两点都是相连的。v3

。。。。。v1e4v2v4v5e1e3e5e6e7v3

。。。。。v1v2v4v5e1e3v3

。。。V1

v2133

若无向图中,顶点之间的连通关系是等价关系,设G是一个无向图,R是G中顶点之间的连通关系,按着R可将V(G)划分成k(k≥1)个等价类,记成V1,V2,…,Vk,由它们导出的导出子图G[Vi](I=1,2,…,k)称为G的连通分支，连通分支数个数记为p(G).例:下列图的连通分支数分别为:定义5.14

设D=<V,E>为一个有向图。若略去D中各有向边的方向后所得无向图G是连通图,则称D是连通图，或称D是弱连通图，简称为连通图。若D中任意两点至少一个可达另一个,则称D是单向连通图。若D中任何一对顶点都是相互可达的,则称D是强连通图。(1)(2)(3)(1)为强连通图,(2)为单向连通图,(3)为弱连通图也就是说:一个有向图如果其任何两点间均是互相可达的则称图G是强连通的；如果其任何两点间至少存在一向是可达的则称图G是单向连通的；如果忽略边的方向后其无向边连通的则称图G是弱连通的(在有向图中强连通图在无向图中是单连通的，也是弱连通的)。(1)(2)(3)(1)为强连通图,(2)为单向连通图,(3)为弱连通图(4)为非连通图(4)v1v2v3v1v2v3v1v2v3v1v2v3强连通的ABCDEFe1e2e3e4e5e6e7e9e8e10单向连通的

r弱连通的割点:如果在图G中删去结点v(及与其相关联的所有边后),图G的分图数增加,则称结点是G的割点v3v2v1v4v5v6v7v8v1v2v3v6v7v8v1v2v3v4v5v7v8(1)(2)(3)例7.20图(1)是连通图,原本只有一个分图,在去掉结点v6(及与v6相关联的边后,图(1)就出现两个分图,图(2),去掉结点v4(及与v4相关联的边后,图(1)就出现三个分图,图(3),∴v4和v6均为割点。v5定义5.15设无向图G=<V,E>,若存在V`V,且V`≠,使得P(G-V`)>P(G),而对于V`的任意真子集V``,即V``

V`,均有P(G-V``)=P(G),则称V`是G的点割集,若点割集中只有一个顶点v,则称v为割点.v3v2v1v4v5v6v7e2e1e3e4e5e6e7e8e9在右图中{v3,v5},{v2},{v6},为点割集。{v4,v2}不是点割集,因为它的真子集{v2}已经是点割集了，类似地,{v1,v6}也不是点割集。割边:如果在图G中删去边(vi,

vj)后,图G的分图数增加,则称边(vi,

vj)是G的割边v3v2v1v4v5v6v7v8v1v2v3v6v7v8v1v2v3v4v5v7v8(1)(2)(3)例5.21图(1)中边(v4,

v5)和(v4,

v6)均是割边,因为当从G中去掉这两条边中的任何一条边后,G都变得不连通。去掉边(v4,

v6)后得图(2),包含2个分图;去掉边(v4,

v5)得图(3)也包含2个分图。v4v6v5定义5.16设无向图G=<V,E>,若存在E`

E,且E`≠

，使得P(G-E`)>P(G)，而对于E`的任意的真子集E``,即E``

E`,均有P(G-E``)=P(G),则称E`是G的边割集。或简称为割集。若边割集中只有一条边e,则称e为割边或桥.v3v2v1v4v5v6v7e2e1e3e4e5e6e7e8e9在右图中{e3,e4},{e1,e2,e3},{e1,e2,e4},{e9}等都是边割集,其中e9是割边。{e6,e7,e9}不是边割集,因为它的真子集{v9}已是割边集，类似地,{v6,v8,v1,v2,v5}{e4,e5}也不是割边集。例5.22:请判断下列路况,并指明其长度.

v1v3e4

。。。。。v2v4v5e1e2e3e5e6e7v1e1v2e6v5e6v2

v1e1v2e6v5e4v4e7v2e1v1

v1e1v2e6v5e4v4e7v2v1e1v2e2v3e3v4e7v2e6v5e5v1v1e5v4e6v2v1e1v2e7v4e4v5e5v1v1到v2的通路v1到v2的简单通路v1到v2的路径v1到v1的回路v1到v1的简单回路v1到v1的圈例5.23：判断各图与图G的关系。GG-e2v1v3e4

。。。。。v2v4v5e1e2e3e5e6e7v3

。。。。。v1e4v2v4v5e1e3e5e6e7e4v3

。。。。。v1v2v4v5e1e3e5e6v3e4

。。。。v2v4v5e2e3e6e7e4

。

。。v2v4v5e6e7v3e4

。。。。v2v4v5e2e3e6e7e1G-{e2,e7}G-v1G-{v1,v3}G-v1+e1§7.3图的矩阵表示定义5.16

设无向图G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令mij为顶点vi与边ej的关联次数，则称(mij)n×m为G的关联矩阵，记作M(G)。结点数为距阵的行数,边为距阵的列数

。。。。。。v3v1e4v2v4v5e1e3e5e6e7v6e210001000000010010010001100100011000200010关联矩阵的性质P163.显然mij可能取制值为0(vi与ej不关联),1(vi与ej关联1次),2(vi与ej关联2次,即ej是以vi为端点的环)v1v2v3v4v5v6e1e2e3e4e5e6e7如下图的关联矩阵

1,vi为ej的始点mij=0，vi与ej是不关联的-1，vi为ej的终点则称(mij)n×m为D的关联矩阵，记作M(D)。定义7.17

设有向图D=<V,E>中无环,V={v1,v2,…,vn},E={e1,e2,…,em},令mij为顶点vi与边ej的关联次数，则称(mij)n×m为G的关联矩阵，记作M(G)。1-1000-101-110000-101-110M(D)=v1v2v3v4e1e2e3e4e5e1e2e3e4e5V1V2V3v4v1v2v3v4e1e2e3e4e5无向图与关联矩阵的对