离散数学课件(第7章)

1、离散数学离散数学教案教案计算机科学与技术学院计算机科学与技术学院课程学时：课程学时：64主主 讲：宋讲：宋 成成河南理工大学河南理工大学电子教案电子教案 图论是最近几年发展迅速而又应用广泛的一图论是最近几年发展迅速而又应用广泛的一门新兴科学。图论是一个重要的数学分支。它门新兴科学。图论是一个重要的数学分支。它最早起源一些数学游戏的难题研究，数学家欧最早起源一些数学游戏的难题研究，数学家欧拉拉1736年发表了关于图论的第一篇论文，解决年发表了关于图论的第一篇论文，解决了著名的哥尼斯堡七桥问题。克希霍夫对电路了著名的哥尼斯堡七桥问题。克希霍夫对电路网络的研究、凯来在有机化学的计算中都应用网络的研究

2、、凯来在有机化学的计算中都应用了树和生成树的概念。以及在民间广为流传的了树和生成树的概念。以及在民间广为流传的一些游戏问题：例如迷宫问题、棋盘上马的行一些游戏问题：例如迷宫问题、棋盘上马的行走路线问题等等。这些古老的问题当时吸引了走路线问题等等。这些古老的问题当时吸引了许多学者的注意，从而在这些问题研究的基础许多学者的注意，从而在这些问题研究的基础上，又提出了著名的四色猜想和环游世界各国上，又提出了著名的四色猜想和环游世界各国的问题的问题第四篇：图论第四篇：图论第四篇篇：图论第四篇篇：图论 图论的不断发展，他在解决运筹学、网络理图论的不断发展，他在解决运筹学、网络理论、信息论、控制论、博弈论以

3、及计算机科学论、信息论、控制论、博弈论以及计算机科学等各个领域的问题时，显示出越来越大的效果等各个领域的问题时，显示出越来越大的效果 对于这样一门应用广泛的学科，其包含的内对于这样一门应用广泛的学科，其包含的内容是丰富的，本篇首先给出图、简单图、完全容是丰富的，本篇首先给出图、简单图、完全图、子图、路和图的同构等概念，接着研究了图、子图、路和图的同构等概念，接着研究了连通图性质和规律，给出了邻接矩阵、可达性连通图性质和规律，给出了邻接矩阵、可达性矩阵、连通矩阵和完全关联矩阵的定义。最后矩阵、连通矩阵和完全关联矩阵的定义。最后介绍了欧拉图与哈密尔顿图、平面图、对偶图介绍了欧拉图与哈密尔顿图、平面

4、图、对偶图与着色、树与生成树与着色、树与生成树。为今后有关学科及课程为今后有关学科及课程的学习和研究提供方便的学习和研究提供方便第七章：图论第七章：图论7.1 图的基本概念图的基本概念7.2 路与回路路与回路7.3 图的矩阵表示图的矩阵表示7.4 欧拉图与哈密尔顿图欧拉图与哈密尔顿图7.5 平面图平面图7.6 对偶图和着色对偶图和着色 7.7 树与生成树树与生成树第七章：图论第七章：图论教学目的及要求：教学目的及要求： 深刻理解和掌握图的有关概念和表示深刻理解和掌握图的有关概念和表示教学类容：教学类容： 图的基本概念、路与回路、图的矩阵表示、欧拉图图的基本概念、路与回路、图的矩阵表示、欧拉图与

5、汉密尔顿图、平面图、对偶图与着色、树与生与汉密尔顿图、平面图、对偶图与着色、树与生成树。成树。教学重点：教学重点： 图、路、图的矩阵表示、平面图、对偶图与着色、图、路、图的矩阵表示、平面图、对偶图与着色、树与生成树树与生成树教学难点：教学难点： 树与生成树。树与生成树。第七章：图论第七章：图论7.1 图的基本概念图的基本概念 7.1.1图图 两个个体两个个体x，y的无序序列称为无序对，记为的无序序列称为无序对，记为(x,y)。在无序对。在无序对(x,y)中，中，x，y是无序的，它们的是无序的，它们的顺序可以颠倒，即顺序可以颠倒，即(x,y)=(y,x)。【定义【定义7.1.1】 图图G是一个三

6、重组是一个三重组 V(G),E(G), G 其中：其中：V(G)是非空结点集。是非空结点集。 E(G)是边集。是边集。 G是边集到结点的有序对或是边集到结点的有序对或 无序对集合的函数。无序对集合的函数。第七章：图论第七章：图论【例【例7.1】G= V(G),E(G), G 其中：其中：V(G)= a,b,c,d E(G)= e1,e2,e3,e4 G： G(e1)=(a,b) G(e2)=(b,c) G(e3)=(a,c) G(e4)=(a,a)试画出试画出G的图形。的图形。 解：解：G的图形如图的图形如图7.1所示所示。第七章：图论第七章：图论 由于在不引起混乱的情况下，图的边可以用有由于

7、在不引起混乱的情况下，图的边可以用有序对或无序对直接表示。因此，图可以简单的表示序对或无序对直接表示。因此，图可以简单的表示为：为： G= V,E 其中：其中：V是非空的结点集。是非空的结点集。 E是边的有序对或无序对组成的集合。是边的有序对或无序对组成的集合。 按照这种表示法，按照这种表示法，例例7.1中的图可以简记为：中的图可以简记为： G= V,E 其中：其中：V= a,b,c,d E= (a,b), (b,c), (a,c), (a,a) 第七章：图论第七章：图论【定义【定义7.1.2 】 若图若图G有有n个结点，则称该图为个结点，则称该图为n阶图。阶图。【定义【定义7.1.3】 设设

8、G为图，如果为图，如果G的所有边都是有向边，则的所有边都是有向边，则称称G为有向图。如果为有向图。如果G的所有边都是无向边，则称的所有边都是无向边，则称G为无向为无向图。如果图。如果G中既有有向边，又有无向边，则称中既有有向边，又有无向边，则称G为混合图。为混合图。 图图7.2的的(a)是无向图，是无向图，(b)是有向图，是有向图，(c)是混合图。是混合图。 第七章：图论第七章：图论 在一个图中，若两个结点由一条边在一个图中，若两个结点由一条边(有向边或无向边有向边或无向边)关联，则称其中的一个结点是另一个结点的邻接点。并称关联，则称其中的一个结点是另一个结点的邻接点。并称这两个结点相互邻接。

9、这两个结点相互邻接。 在一个图中不与任何结点相邻接的结点，称为孤立点。在一个图中不与任何结点相邻接的结点，称为孤立点。 在一个图中，如果两条边关联于同一个结点，则称其在一个图中，如果两条边关联于同一个结点，则称其中的一个边是另一个边的邻接边。并称这两个边相互邻接。中的一个边是另一个边的邻接边。并称这两个边相互邻接。关联于同一个结点的一条边叫做环或自回路。在有向图中关联于同一个结点的一条边叫做环或自回路。在有向图中环的方向可以是顺时针，也可以是逆时针，它们是等效的。环的方向可以是顺时针，也可以是逆时针，它们是等效的。【定义【定义7.1.4】 由孤立点组成的图叫做零图。由一个孤立由孤立点组成的图叫

10、做零图。由一个孤立点组成的图叫做平凡图。点组成的图叫做平凡图。 根据根据定义定义7.1.4，平凡图一定是零图。平凡图一定是零图。 第七章：图论第七章：图论7.1.2结点的度及其性质结点的度及其性质【定义【定义7.1.5】设设G= V,E 是图，是图，v V，与，与v相关联相关联的边数叫做结点的边数叫做结点v的度。记为的度。记为deg(v)。规定，自回。规定，自回路为所在结点增加路为所在结点增加2度。度。 在图在图G= V,E 中，度数最大中，度数最大(小小)的结点的度的结点的度叫做图叫做图G的最大的最大(小小)度，记为度，记为 (G)( (G)。图。图G的的最大度和最小度表示为：最大度和最小度

11、表示为： (G)=max deg(v) | v V (G)= min deg(v) | v V 在图在图7.1中，中， (G)=4， (G)=0。 第七章：图论第七章：图论【定理【定理7.1.1】在任何图在任何图G= V,E 中，所有结点度中，所有结点度数的和等于边数的数的和等于边数的2倍。即：倍。即：= 2|E| 证明：证明：图的每一条边都和两个结点相关联，图的每一条边都和两个结点相关联，为每个相关联的结点增加一度为每个相关联的结点增加一度, 给图增加两度。给图增加两度。所以所有结点度数的和等于边数的所以所有结点度数的和等于边数的2倍。倍。 推论推论 在任何图在任何图G= V,E 中，度数为

12、奇数的中，度数为奇数的结点必为偶数个。结点必为偶数个。第七章：图论第七章：图论【定义【定义7.1.6】设设G= V,E 是有向图，是有向图，v V，射入，射入(出出)结点结点v的边数称为结点的边数称为结点v的入的入(出出)度。记为度。记为deg(v) (deg(v)。 显然，任何结点的入度与出度的和等于该结显然，任何结点的入度与出度的和等于该结点的度数，即点的度数，即deg(v)=deg(v)+deg(v)。【定理【定理7.1.2】在有向图中，所有结点入度的和等在有向图中，所有结点入度的和等于所有结点出度的和。于所有结点出度的和。 证明：证明：在有向图中每一条边对应一个入度和在有向图中每一条边

13、对应一个入度和一个出度，为图的入度和出度各增加一个出度，为图的入度和出度各增加1。所以，。所以，所有结点入度的和等于边数，所有结点出度的和所有结点入度的和等于边数，所有结点出度的和也等于边数。也等于边数。 第七章：图论第七章：图论7.1.3多重图、简单图、完全图和正则图多重图、简单图、完全图和正则图【定义【定义7.1.7 】 在图在图G中，连接同一对结点的多条相中，连接同一对结点的多条相同边称为平行边。平行边的条数称为该平行边的重数。同边称为平行边。平行边的条数称为该平行边的重数。含平行边的图叫多重图。不含平行边和环的图叫简单含平行边的图叫多重图。不含平行边和环的图叫简单图。图。 例如，在图例

14、如，在图7.3(a)中结点中结点a和和b之间有两条平行边，之间有两条平行边，结点结点b和和c之间有三条平行边，结点之间有三条平行边，结点b上有两条平行边，上有两条平行边，这两条平行边都是环。图这两条平行边都是环。图7.3(a)不是简单图。不是简单图。 又如，在图又如，在图7.3(b)中结点中结点v1和和v2之间有两条平行之间有两条平行边。边。v2和和v3之间的两条边，因为方向不同，所以不是之间的两条边，因为方向不同，所以不是平行边。图平行边。图7.3(b)不是简单图。不是简单图。 简单图不含平行边和环。简单图不含平行边和环。 第七章：图论第七章：图论第七章：图论第七章：图论【定理【定理7.1.

15、3 】 设设G为为n阶简单无向图，则阶简单无向图，则 (G)n1。 证明：证明：因为因为G有有n个结点，个结点，G的任何结点的任何结点v最多只能最多只能与其余的与其余的n1结点相邻接；又因为结点相邻接；又因为G为简单图，既无平为简单图，既无平行边，又无环。所以行边，又无环。所以deg(v)n1。由。由v的任意性，就有的任意性，就有 (G) =max deg(v) | v V n1。【定义【定义7.1.8 】 设设G为为n阶简单无向图，若阶简单无向图，若G中的每个结中的每个结点都与其余的点都与其余的n1个结点相邻接，则称个结点相邻接，则称G为为n阶无向完阶无向完全图。记为全图。记为Kn。在。在n

16、阶无向完全图中，给每一条边任意阶无向完全图中，给每一条边任意确定一个方向，所得到的图称为确定一个方向，所得到的图称为n阶有向完全图。也记阶有向完全图。也记为为Kn。 今后，将今后，将n阶无向完全图和阶无向完全图和n阶有向完全图统称为阶有向完全图统称为n阶完全图。阶完全图。 第七章：图论第七章：图论【定理【定理7.1.4】 n阶完全图阶完全图Kn的边数为的边数为 证明：证明：在在Kn中，每个结点都与其余的中，每个结点都与其余的n1结点结点相邻接，即任何一对结点之间都有一条边，故边数相邻接，即任何一对结点之间都有一条边，故边数应为应为 【定义【定义7.1.9 】设设G为为n阶简单无向图，若阶简单无

17、向图，若G中每个结中每个结点都是点都是k度的，则称度的，则称G为为k次正则图。次正则图。 ) 1(212nnCn) 1(212nnCn第七章：图论第七章：图论7.1.4图的同构图的同构 在图论中只关心结点间是否有连线，而不关心结在图论中只关心结点间是否有连线，而不关心结点的位置和连线的形状。因此，对于给定的图而言，点的位置和连线的形状。因此，对于给定的图而言，如果将图的各结点安排在不同的位置上，并且用不同如果将图的各结点安排在不同的位置上，并且用不同形状的弧线或直线表示各边，则可以得到各种不同图形状的弧线或直线表示各边，则可以得到各种不同图形。所以，同一图的图形并不惟一。由于这种图形表形。所以

18、，同一图的图形并不惟一。由于这种图形表示的任意性，可能出现这样的情况：看起来完全不同示的任意性，可能出现这样的情况：看起来完全不同的两种图形，却表示着同一个图。的两种图形，却表示着同一个图。 例如，在图例如，在图7.4中，中，(a)和和(b)两个图的图形不同，两个图的图形不同，但它们的结构完全相同，是同一个图。但它们的结构完全相同，是同一个图。 为了描述看起来不同，而其结构完全相同的图，为了描述看起来不同，而其结构完全相同的图，引入了同构的概念。引入了同构的概念。 第七章：图论第七章：图论第七章：图论第七章：图论【定义【定义7.1.10】 设设G1= V1,E1 与与G2= V2,E2 是两是

19、两个无向图个无向图( (有向图有向图) )，若存在双射函数，若存在双射函数f：V1V2， v1 V1， v2 V1(v1,v2) E1( v1,v2E1)当且仅当当且仅当(f(v1),f(v2) E2)( f(v1),f(v2)E2)并且并且(v1,v2)( v1,v2 )与与(f(v1),f(v2)( f(v1),f(v2) )的重的重数相同，则称图数相同，则称图G1与图与图G2同构。记为同构。记为G1G2。双。双射函数射函数f称为图称为图G1与图与图G2的同构函数。的同构函数。 第七章：图论第七章：图论 两个图同构必须满足下列条件：两个图同构必须满足下列条件： 结点数相同。结点数相同。 边

20、数相同。边数相同。 度数相同的结点数相同。度数相同的结点数相同。 这三个条件是两个图同构的必要条件，不是充分条这三个条件是两个图同构的必要条件，不是充分条件。一般的，用上述三个必要条件判断两个图是不同构件。一般的，用上述三个必要条件判断两个图是不同构的。的。 两个图同构，它们的同构函数必须实现同度结点对两个图同构，它们的同构函数必须实现同度结点对应同度结点。应同度结点。 第七章：图论第七章：图论 7.1.5补图、子图和生成子图补图、子图和生成子图【定义【定义7.1.11】设设G= V,E 是是n阶简单无向图，阶简单无向图，G中的所有结点和所有能使中的所有结点和所有能使G成为完全图的添加边成为完

21、全图的添加边组成的图称为图组成的图称为图G的相对于完全图的补图，简称的相对于完全图的补图，简称为为G的补图。记的补图。记为为 。若。若G ，则称则称G为自补图。为自补图。 在图在图7.5中，中，(b)是是(a)的补图，的补图，(a)与与(b)同构，所同构，所以以(a)是自补图。是自补图。 GG第七章：图论第七章：图论【定义【定义7.1.12】设设G= V,E 与与G1= V1,E1 是两个图。是两个图。如果如果V1 V且且E1 E，则称，则称G1是是G的子图，的子图，G是是G1的的母图；如果母图；如果V1 V且且E1 E，则称，则称G1是是G的真子图；的真子图；如果如果V1V且且E1 E则称则

22、称G1是是G的生成子图。的生成子图。 在图在图7.6中，中，(b)是是(a)的子图、真的子图、真子图、生成子图、生成子图。子图。第七章：图论第七章：图论7.2 路和回路路和回路【定义【定义7.2.1】 设设G= V,E 是图，是图，G中的结点与边的交替序列中的结点与边的交替序列L：v0e1v1e2v2envn叫做叫做v0到到vn的路。其中的路。其中vi- -1与与vi是是ei的端点，的端点，i=1,n。v0和和vn分别叫做路分别叫做路L的始点和终点。路的始点和终点。路L中边的条数叫中边的条数叫做该路的长度。做该路的长度。 例如，在图例如，在图7.7中，中， L1：v5e8v4e5v2e6v5e

23、7v3 是从是从v5到到v3的路，的路，v5是始点，是始点， v3是终点，长度为是终点，长度为4。 L2：v1e1v2e3v3 是从是从v1到到v3的路，的路，v1是始点，是始点， v3是终点，长度为是终点，长度为2。 在简单图中没有平行边和环，路在简单图中没有平行边和环，路L：v0e1v1e2v2envn完全由完全由它的结点序列它的结点序列v0v1v2 vn确定。所以，在简单图中的路可以用结确定。所以，在简单图中的路可以用结点序列表示。点序列表示。 第七章：图论第七章：图论 【定义【定义7.2.2】 设设G= V,E 是图，是图，L是从是从 v0到到vn的路。若的路。若v0=vn，则称，则称

24、L为回路。若为回路。若L中所有边各异，则中所有边各异，则称称L为简单路。若此时又有为简单路。若此时又有v0=vn，则称则称L为简单回路。若为简单回路。若L中所有结中所有结点各异，则称点各异，则称L为基本路。若此时为基本路。若此时又有又有v0=vn，则称，则称L为基本回路。若为基本回路。若L既是简单路，又是基本路，则称既是简单路，又是基本路，则称L为初级路。若此时又有为初级路。若此时又有v0=vn，则，则称称L为初级回路。为初级回路。 在图在图7.7中，中，L1是一条简单路。是一条简单路。L2是一条简单路、基本路、初级路是一条简单路、基本路、初级路。 第七章：图论第七章：图论【 定理定理7.2.

25、1】 在在n阶图阶图G中，若从结点中，若从结点vi到到vj(vivj)存在一条存在一条路，则必存在长度小于等于路，则必存在长度小于等于n- -1的路。的路。 证明：证明：设设L：vie1v1e2v2ejvj是是G中一条从结点中一条从结点vi到到vj长度长度为为l的路，路上有的路，路上有l+1个结点。个结点。 若若ln- -1，则定理已证。，则定理已证。 否则，否则，ln- -1，此时，此时，l+1n，即路，即路L上的结点数上的结点数l+1大大于图于图G中的结点数中的结点数n，此路上必有相同结点。设，此路上必有相同结点。设vk和和vs相同。相同。于是，此路两次通过同一个结点于是，此路两次通过同一

26、个结点vk(vs)，所以在，所以在L上存在上存在vs到自到自身的回路身的回路Cks。在。在L上删除上删除Cks上的一切边和除上的一切边和除vs以外的一切结以外的一切结点，得路点，得路L1：vie1v1ekvsejvj。L1仍为从结点仍为从结点vi到到vj的路，且的路，且长度至少比长度至少比L减少减少1。若路。若路L1的长度小于等于的长度小于等于n- -1，则定理已，则定理已证。否则，重复上述过程。由于证。否则，重复上述过程。由于G有有n个结点，经过有限步后，个结点，经过有限步后，必得到从必得到从vi到到vj长度小于等于长度小于等于n- -1的路。的路。第七章：图论第七章：图论推论推论 在在n阶

27、图阶图G中，若从结点中，若从结点vi到到vj(vivj)存在路，存在路，则必存在长度小于等于则必存在长度小于等于n- -1的初级路。的初级路。 由定理由定理7.2.1的证明过程知，本推论成立。的证明过程知，本推论成立。 类似的可证明下列定理和推论。类似的可证明下列定理和推论。【定理【定理7.2.2】 在在n阶图阶图G中，若存在结点中，若存在结点vi到自身到自身的回路，则必存在的回路，则必存在vi到自身长度小于等于到自身长度小于等于n的回路。的回路。 推论推论 在在n阶图阶图G中，若存在结点中，若存在结点vi到自身的简单回到自身的简单回路，则必存在路，则必存在vi到自身长度小于等于到自身长度小于

28、等于n的初级回路。的初级回路。 【定义【定义7.2.3】 在无向图在无向图G中，如果结点中，如果结点u和结点和结点v之间存在之间存在一条路，则称结点一条路，则称结点u和结点和结点v连通。记为连通。记为uv。规定，。规定，G中中任意结点任意结点v和自身连通，即和自身连通，即vv。 在无向图中，如果结点在无向图中，如果结点u和结点和结点v连通，即连通，即uv，那么，那么，结点结点v和结点和结点u连通，即连通，即vu。所以，无向图结点间的连通。所以，无向图结点间的连通是对称的。是对称的。 设设G= V,E 是无向图，在图是无向图，在图G的结点集的结点集V上建立一个上建立一个二元关系二元关系R：R=u

29、,v | u Vv Vu和和v连通连通 R叫做无向图叫做无向图G的结点集的结点集V上的连通关系。上的连通关系。 因为因为R是自反的、对称的、传递的，所以是自反的、对称的、传递的，所以R是是V上的等上的等价关系。无向图价关系。无向图G的结点集的结点集V上的连通关系是等价关系。上的连通关系是等价关系。第七章：图论第七章：图论 设设G是图是图7.8。结点集。结点集V上的连通关系为上的连通关系为R，以下验证，以下验证R是是V上的等价关系，并找出所有等价类。上的等价关系，并找出所有等价类。 R=a,a , a,b , a,c , b,a , b,b , b,c , c,a , c,b , c,c , d

30、,d , e,e , e,f , e,g , e,h , f,e , f,f , f,g , f,h , g,e , g,f , g,g , g,h , h,e , h,f , h,g , h,h = a,b,c a,b,c d d e,f,g,h e,f,g,h 根据定义，根据定义，R是是V上的等价关上的等价关系。等价类有三系。等价类有三个，分别是：个，分别是： a,b,c ， d ， e,f,g,h 。第七章：图论第七章：图论【定义【定义7.2.4】 若无向图若无向图G中的任何两个结点都是连通中的任何两个结点都是连通的，则称的，则称G为连通图。规定，平凡图是连通图。为连通图。规定，平凡图是

31、连通图。【定义【定义7.2.5】 设设G= V,E 是图是图 V1 V且且V1，E1是是G中两个端点都在中两个端点都在V1中的边中的边组成的集合，图组成的集合，图G1= V1,E1 叫做叫做G的由的由V1导出的子图，导出的子图，记为记为GV1。 E2 E且且E2，V2是由是由E2中的边所关联的结点中的边所关联的结点组成的集合，图组成的集合，图G2= V2,E2 叫做叫做G的由的由E2导出的子图，导出的子图，记为记为GE2。 在图在图7.9中，设图中，设图G为为(a)，取，取V1= a,b,c ，则，则G的由的由V1导出的子图导出的子图GV1是是(b)。取。取E2= (a,b),(d,c) ，G

32、的由的由E2导出的子图导出的子图GE2是是(c)。第七章：图论第七章：图论第七章：图论第七章：图论【定义【定义7.2.6】 设设G= V,E 是无向图，是无向图， R是是V上的连通上的连通关系，关系，V/R= Vi Vi是是R的等价类，的等价类，i=1,k 是是V关于关于R的商集，的商集，GVi是是Vi导出的子图，称导出的子图，称GVi( i=1, k)为为G的连通分支。的连通分支。G的连通分支数记为的连通分支数记为W(G)。 设图设图7.8为为G，在，在G中，连通关系中，连通关系R的三个等价类的三个等价类是是 a,b,c ， d ， e,f,g,h ，它们导出的，它们导出的G的子图分别的子图

33、分别是图是图7.8中的中的(a)，(b)，(c)。它们都是。它们都是G的连通分支。的连通分支。G的连通分支数的连通分支数W(G)=3。 每一个连通分支中任何两个结点是连通的，而位每一个连通分支中任何两个结点是连通的，而位于不同连通分支中的任何两个结点是不连通的。即每于不同连通分支中的任何两个结点是不连通的。即每一个连通分支都是原图的最大的连通子图。在图一个连通分支都是原图的最大的连通子图。在图7.8中，中，(a)，(b)，(c)都是最大的连通子图。都是最大的连通子图。 第七章：图论第七章：图论【定义【定义7.2.7】 设设u，v是无向图是无向图G中的任意两个结点，若中的任意两个结点，若u和和v

34、连连通，则通，则u和和v之间最短路的长叫做结点之间最短路的长叫做结点u与结点与结点v的距离，记为的距离，记为d(u,v)。若。若u和和v不连通，规定，不连通，规定，u与与v的距离为的距离为。即。即d(u,v)= 设设G= V,E 是无向图，是无向图，u、v和和w是是V中的任意结点，中的任意结点，G的结的结点间的距离有以下的性质：点间的距离有以下的性质： d(u,v)0 d(u,u)=0 d(u,v)d(v,w)d(u,w) d(u,v)=d(v,u) 在在n阶无向完全图阶无向完全图Kn中，每两个不同结点间都有一条边，中，每两个不同结点间都有一条边，它们的距离是它们的距离是1。在零图中，每两个不

35、同结点间都没有路，它。在零图中，每两个不同结点间都没有路，它们的距离都是们的距离都是。 在图在图G中删除一个结点，就是将这个结点与它的所有关联中删除一个结点，就是将这个结点与它的所有关联边全部删除。删除一个边，则仅去掉这个边。边全部删除。删除一个边，则仅去掉这个边。 第七章：图论第七章：图论【定义【定义7.2.8】设设G= V,E 是无向连通图，是无向连通图，V1 V且且V1，满，满足：足： 删除删除V1的所有结点，得到的子图是不连通的。的所有结点，得到的子图是不连通的。 删除删除V1的任何真子集，得到的子图是连通的。的任何真子集，得到的子图是连通的。则称则称V1是是G的点割集。如果某一个结点

36、组成了点割集，则称的点割集。如果某一个结点组成了点割集，则称该点为割点。该点为割点。 在图在图7.10中，中， b,d ， c ， e 都是都是点割集，结点点割集，结点c和结点和结点e都是割点。虽然删除都是割点。虽然删除结点结点a和和c图成为不连图成为不连通的，但因通的，但因 c 是是 a,c 的真子集，所以的真子集，所以 a,c 不是点割集。不是点割集。第七章：图论第七章：图论【定义【定义7.2.9】设设G= V,E 是无向连通图，如果是无向连通图，如果G不是完全图，不是完全图，k(G)=min |V1| V1是是G的点割集的点割集 称称为图为图G的点连通度。如果的点连通度。如果G是完全图，

37、规定是完全图，规定n阶无阶无向完全图向完全图Kn的点连通度为的点连通度为n1，即，即k(Kn)=n1。规定不连通图规定不连通图G的点连通度为的点连通度为0。即。即k(G)= 0。 图图7.10是无向连通图，但不是完全图，存在是无向连通图，但不是完全图，存在割点割点c和和e，所以点连通度是，所以点连通度是1。 无向连通图的点连通度的物理意义是：要使无向连通图的点连通度的物理意义是：要使G成为不连通的最少要删除的结点数。图成为不连通的最少要删除的结点数。图7.10的的点连通度是点连通度是1，最少删除一个结点，图成为不连，最少删除一个结点，图成为不连通的，例如删除结点通的，例如删除结点c或结点或结点

38、e。 第七章：图论第七章：图论【定义【定义7.2.10】设设G= V,E 是无向连通图，是无向连通图，E1 E且且E1，满足：，满足： 删除删除E1的所有边，得到的子图是不连通的。的所有边，得到的子图是不连通的。 删除删除E1的任何真子集，得到的子图是连通的的任何真子集，得到的子图是连通的则称则称E1是是G的边割集。如果某一条边组成了边割集，的边割集。如果某一条边组成了边割集，则称该边为割边或桥。则称该边为割边或桥。 在图在图7.10中，集合中，集合 (c,e) 、 (e,f) 、 (a,b),(d,c) 和和 (a,d),(b,c) 都是都是G的边割集，无向边的边割集，无向边(c,e)和和(

39、e,f)为割边。虽然删除边为割边。虽然删除边(a,d)、(a,b)和和(d,c)图成为不连通的，但因集合图成为不连通的，但因集合 (a,b),(d,c) 是集合是集合 (a,d),(a,b),(d,c) 的真子集，所以的真子集，所以 (a,d),(a,b),(d,c) 不是边割集。不是边割集。第七章：图论第七章：图论【定义【定义7.2.11】设设G= V,E 是无向连通图，如果是无向连通图，如果G是是非平凡图，非平凡图， (G)=min |E1| E1是是G的边割集的边割集 称为称为G的的边连通度。如果边连通度。如果G是平凡图，规定是平凡图，规定G的边连通度为的边连通度为0。规定不连通图规定不

40、连通图G的边连通度为的边连通度为0，即，即 (G)=0。 图图7.10是无向连通图，但不是平凡图，存在割边是无向连通图，但不是平凡图，存在割边(c,e)和和(e,f)，所以，它的边连通度是，所以，它的边连通度是1。 无向连通图的边连通度的物理意义是：要使无向连通图的边连通度的物理意义是：要使G成成为不连通的最少要删除的边数。图为不连通的最少要删除的边数。图7.10的边连通度是的边连通度是1，最少删除一条边，最少删除一条边，图就会图就会成为不连通的，例如删成为不连通的，例如删除除割边割边(c,e)或或(e,f)。 无向图无向图G的点连通度的点连通度k(G)、边连通度、边连通度 (G)和最小和最小

41、度度 (G)有下列的关系：有下列的关系： 第七章：图论第七章：图论【定理【定理7.2.3】设设G= V,E 为任意无向图，则为任意无向图，则k(G) (G) (G) 证明：证明：如果如果G是不连通的，由点连通度和边连通是不连通的，由点连通度和边连通度的定义有度的定义有k(G)= (G)=0，所以，所以 k(G) (G) (G) 如果如果G是连通图。是连通图。 先证明先证明 (G) (G) 如果如果G是平凡图，是平凡图， (G)=0 (G)，即，即 (G) (G) 如果如果G是非平凡图，设是非平凡图，设n= (G)=min deg(v)|v V ，则存在则存在G的一个结点的一个结点v，它关联了，

42、它关联了n条边，而其它结点关条边，而其它结点关联的边数大于等于联的边数大于等于n，将，将v关联的这关联的这n条边删除，条边删除，G成为成为不连通的。从而这不连通的。从而这n条边或这条边或这n条边中的几条边组成一条边中的几条边组成一个边割集，即存在一个边割集的基数小于等于个边割集，即存在一个边割集的基数小于等于n，所以，所以第七章：图论第七章：图论 min |E 1| | E 1是是G的边割集的边割集 n=min deg(v) | v V ，即即 (G) (G) 再证再证k(G) (G) 设设 (G)=1，G有一条割边，此边的任一端点是割点，有一条割边，此边的任一端点是割点，k(G)=1。所以。

43、所以k(G) (G)成立。成立。 设设 (G)2，则可删除某，则可删除某 (G)条边，使条边，使G成为不连通的，成为不连通的，而删除其中的而删除其中的 (G)1条边，它仍然是连通的且有一个桥，条边，它仍然是连通的且有一个桥，设该桥为设该桥为e=(u,v)。对这。对这 (G)1条边选取一个不同于条边选取一个不同于u，也也不同于不同于v的端点，把这些端点删除，则必至少删除了这的端点，把这些端点删除，则必至少删除了这 ( G ) 1 条 边 。 若 这 样 产 生 的 图 是 不 连 通 的 ， 则条 边 。 若 这 样 产 生 的 图 是 不 连 通 的 ， 则k(G) (G)1 (G)。若这样产

44、生的图是连通的，则。若这样产生的图是连通的，则e=(u,v)仍是桥。此时再删除仍是桥。此时再删除u或或v，就必产生了一个不连通图，就必产生了一个不连通图，故故k(G) (G) 由由和和得得k(G) (G) (G) 第七章：图论第七章：图论 图图7.11是无向连通图，点连通度是无向连通图，点连通度k(G)=1，边连通度，边连通度 (G)=2，最小度，最小度 (G)=3，此图满足，此图满足k(G) (G) (G)。第七章：图论第七章：图论【定理【定理7.2.4】在无向连通图在无向连通图G中，结点中，结点v是割点的充分必要条是割点的充分必要条件是存在两个结点件是存在两个结点u和和w，使结点，使结点u

45、和和w之间的每一条路都通过之间的每一条路都通过v。 证明：证明：设设v是割点，证明存在两个结点是割点，证明存在两个结点u和和w，使结点，使结点u和和w之间的每一条路都通过之间的每一条路都通过v。 v是割点，删除是割点，删除v得得G，G至少包含两个连通分支，设其至少包含两个连通分支，设其中的两个为中的两个为G1= V1,E1 和和G2= V2,E2 ， u V1， w V2，因为，因为G连通，在连通，在G中中u和和w之间必有路，设之间必有路，设L是它们之间任意一条路。是它们之间任意一条路。在在G中，由于中，由于u和和w属于两个不同连通分支，所以，属于两个不同连通分支，所以，u和和w之间之间必没有

46、路。故必没有路。故L必通过必通过v。 设存在两个结点设存在两个结点u和和w，使结点，使结点u和和w之间的每一条路都通之间的每一条路都通过过v，证明，证明v是割点。是割点。 删除删除v得子图得子图G，因为结点，因为结点u和和w之间的每一条路都通过之间的每一条路都通过v，所以在所以在G中结点中结点u和和w之间必无路，即结点之间必无路，即结点u和和w不连通。由连不连通。由连通图的定义知，通图的定义知，G是不连通的，故是不连通的，故v是是G的割点。的割点。 第七章：图论第七章：图论【定义【定义7.2.12】在有向图在有向图G中，结点中，结点u到结点到结点v存在一条路，存在一条路，则称结点则称结点u到结

47、点到结点v可达。记为可达。记为uv。如果。如果u到到v可达且可达且v到到u也可达，称结点也可达，称结点u和结点和结点v相互可达。记为相互可达。记为uv。 规规定，定，G中任何结点中任何结点v自己到自己可达，即自己到自己可达，即vv。【定义【定义7.2.13】在有向图在有向图G= V,E 中，中，u V，v V，若结，若结点点u到结点到结点v可达，可达，u到到v最短路的长称为结点最短路的长称为结点u到结点到结点v的的距离。记为距离。记为d u,v 。若。若u到到v不可达，规定，不可达，规定，u到到v的距离的距离为为。即。即d u,v =。 对于有向图对于有向图G中的任意结点中的任意结点u,v和和

48、w，结点间的距离，结点间的距离有以下的性质：有以下的性质： d u,v 0 d u,u =0 d u,v d v,w d u,w 第七章：图论第七章：图论【定义【定义7.2.14】在简单有向图在简单有向图G中，对于任意两个结中，对于任意两个结点点u和和v， 如果结点如果结点u到结点到结点v可达或结点可达或结点v到结点到结点u可达，可达，则称则称G为单向为单向(侧侧)连通的。连通的。 如果结点如果结点u和结点和结点v互相可达，则称互相可达，则称G为强连为强连通的。通的。 如果略去方向得到的无向图是连通的，则称如果略去方向得到的无向图是连通的，则称G为弱连通的。为弱连通的。 在图在图7.12中，中

49、，(a)是强连通的、单向是强连通的、单向(侧侧)连通的连通的和弱连通的。和弱连通的。(b)是单向是单向(侧侧)连通的和弱连通的，但连通的和弱连通的，但不是强连通的。不是强连通的。(c)是弱连通的，但不是单向是弱连通的，但不是单向(侧侧)连连通的，也不是强连通的。通的，也不是强连通的。第七章：图论第七章：图论 一般地说，若有向图一般地说，若有向图G是强连通的，则必是单是强连通的，则必是单向向(侧侧)连通的和弱连通的；若有向图连通的和弱连通的；若有向图G是单向是单向(侧侧)连连通的，则必是弱连通的。反之不真。通的，则必是弱连通的。反之不真。第七章：图论第七章：图论【定理定理7.2.5】一个有向图一

50、个有向图G是强连通的充分必要条件是强连通的充分必要条件是是G中有一个回路至少包含中有一个回路至少包含G的每个结点一次。的每个结点一次。 证明：证明：设设G中有一个回路至少包含中有一个回路至少包含G的每个结点的每个结点一次，下证一次，下证G是强连通的。是强连通的。 G中有一个回路至少包含每个结点一次，则中有一个回路至少包含每个结点一次，则G中中的任意两个结点通过回路互相可达。所以的任意两个结点通过回路互相可达。所以G是强连通是强连通的。的。 设设G是强连通的，下证是强连通的，下证G中有一个回路至少包含中有一个回路至少包含G的每个结点一次。的每个结点一次。 若不然，存在结点若不然，存在结点v不在不

51、在G的回路上，且的回路上，且v不与其不与其它所有结点不能互相可达，这与它所有结点不能互相可达，这与G是强连通的矛盾。是强连通的矛盾。故故G中有一个回路至少包含中有一个回路至少包含G的每个结点一次。的每个结点一次。第七章：图论第七章：图论【定理【定理7.2.6】一个有向图一个有向图G是单向连通的充分必是单向连通的充分必要条件是要条件是G中有一个路至少包含每个结点一次。中有一个路至少包含每个结点一次。 证明略证明略。【定义【定义7.2.15】在简单有向图在简单有向图G中，具有强中，具有强(单向，单向，弱弱)连通性质的最大子图叫做强连通性质的最大子图叫做强(单向，弱单向，弱)分图。分图。 在图在图7

52、.13(a)中中，由由 v1,v2,v3,v4 导出的子图是导出的子图是强 分 图 ，强 分 图 ， v5 导 出 的 子 图 也 是 强 分 图 。 由导 出 的 子 图 也 是 强 分 图 。 由 v1,v2,v3,v4,v5 导出的子图是单向分图，也是弱分导出的子图是单向分图，也是弱分图。图。 在图在图7.13 (b) 中，中， v1 ， v2 ， v3 ， v4 导出导出的子图是强分图，的子图是强分图， v1,v2,v3 ，和，和 v1,v3,v4 导出的子导出的子图是单向分图，图是单向分图， v1,v2,v3,v4 导出了弱分图。导出了弱分图。 第七章：图论第七章：图论第七章：图论第

53、七章：图论【定理【定理7.2.7】在有向图在有向图G= V,E 中，每一个结点位中，每一个结点位于且只位于一个强分图中。于且只位于一个强分图中。 证明：证明： v V，令，令V1是是G中所有与中所有与v互相可达互相可达的结点组成的集合，当然的结点组成的集合，当然v V1， V1导出的子图是导出的子图是G的强分图。故的强分图。故G的每一个结点位于一个强分图中。的每一个结点位于一个强分图中。 设设G1= V1,E1 和和G2= V2,E2 是是G的两个强分的两个强分图，设图，设v V1且且v V2，则，则v与与G1中的所有结点相互可中的所有结点相互可达且与达且与G2中的所有结点相互可达。于是中的所

54、有结点相互可达。于是G1中的结点中的结点与与G2中的结点通过中的结点通过v相互可达。这与相互可达。这与G1和和G2是强分是强分图相矛盾。故图相矛盾。故G的每一个结点只位于一个强分图中。的每一个结点只位于一个强分图中。 第七章：图论第七章：图论7.3图的矩阵表示图的矩阵表示【定义【定义7.3.1】设设 G= V,E 是一个简单图，是一个简单图，V= v1,v2,vn A(G)=(aij) nn 其中：其中： i ,j=1,n称称A(G)为为G的邻接矩阵。简记为的邻接矩阵。简记为A。 01jivvvvajijiij无边或到有边到第七章：图论第七章：图论0111101011011010)(GA 例如

55、图例如图7.14的邻接矩阵为的邻接矩阵为： 第七章：图论第七章：图论又如图又如图7.15(a)的邻接矩阵为：的邻接矩阵为： 0001101111000010)(GA第七章：图论第七章：图论 邻接矩阵具有以下性质：邻接矩阵具有以下性质： 邻接矩阵的元素全是邻接矩阵的元素全是0或或1。这样的矩阵叫布尔矩阵。这样的矩阵叫布尔矩阵。邻接矩阵是布尔矩阵。邻接矩阵是布尔矩阵。 无向图的邻接矩阵是对称阵，有向图的邻接矩阵不无向图的邻接矩阵是对称阵，有向图的邻接矩阵不一定是对称阵。一定是对称阵。 邻接矩阵与结点在图中标定次序有关。例如图邻接矩阵与结点在图中标定次序有关。例如图7.15(a)的邻接矩阵是的邻接矩

56、阵是A(G)，若将图，若将图7.15(a)中的接点中的接点v1和和v2的标定次序调换，得到图的标定次序调换，得到图7.15(b)，图，图9.23(b)的邻接矩阵是的邻接矩阵是A(G)。0010101100011100)(GA第七章：图论第七章：图论 考察考察A(G)和和A(G)发现，先将发现，先将A(G)的第一行与第二行对调，的第一行与第二行对调，再将第一列与第二列对调可得到再将第一列与第二列对调可得到A(G)。称。称A(G)与与A(G)是置换是置换等价的。等价的。 一般地说，把一般地说，把n阶方阵阶方阵A的某些行对调，再把相应的列做的某些行对调，再把相应的列做同样的对调，得到一个新的同样的对

57、调，得到一个新的n阶方阵阶方阵A，则称，则称A与与A是置换等是置换等价的。可以证明置换等价是价的。可以证明置换等价是n阶布尔方阵集合上的等价关系。阶布尔方阵集合上的等价关系。 虽然，对于同一个图，由于结点的标定次序不同，而得虽然，对于同一个图，由于结点的标定次序不同，而得到不同的邻接矩阵，但是这些邻接矩阵是置换等价的。今后到不同的邻接矩阵，但是这些邻接矩阵是置换等价的。今后略去结点标定次序的任意性，取任意一个邻接矩阵表示该图。略去结点标定次序的任意性，取任意一个邻接矩阵表示该图。 对有向图来说，邻接矩阵对有向图来说，邻接矩阵A(G)的第的第i行行1的个数是的个数是vi的出的出度，度， 第第j列

58、列1的个数是的个数是vj的入度。的入度。 零图的邻接矩阵的元素全为零，叫做零矩阵。反过来，零图的邻接矩阵的元素全为零，叫做零矩阵。反过来，如果一个图的邻接矩阵是零矩阵，则此图一定是零图。如果一个图的邻接矩阵是零矩阵，则此图一定是零图。第七章：图论第七章：图论【定理定理7.3.1】设设A(G)是图是图G的邻接矩阵，的邻接矩阵，A(G)k=A(G)A(G)k-1，A(G)k的第的第i行，第行，第j列元素列元素 等于从等于从vi到到vj长度为长度为k的路的条数。的路的条数。其中其中 为为vi到自身长度为到自身长度为k的回路数。的回路数。 推论推论 设设G= V,E 是是n阶简单有向图，阶简单有向图，

59、A是有向图是有向图G的邻接的邻接矩阵，矩阵，Bk=AA2Ak，Bk=( )nn，则，则 是是G中由中由vi到到vj长长度小于等于度小于等于k的路的条数。的路的条数。 是是G中长度小于等于中长度小于等于k的路的的路的总条数。总条数。 是是G中长度小于等于中长度小于等于k的回路数。的回路数。【例【例7.3.1】 设设G= V,E 为简单有向图，图形如图为简单有向图，图形如图7.16，写出，写出G的邻接矩阵的邻接矩阵A，算出，算出A2，A3，A4且确定且确定v1到到v2有多少条长度为有多少条长度为3的路的路? v1到到v3有多少条长度为有多少条长度为2的路的路? v2到自身长度为到自身长度为3和长度

60、和长度为为4的回路各多少条的回路各多少条?kijakiiakijb ninjkijb11nikiib1kijb第七章：图论第七章：图论 解：解：邻接矩阵邻接矩阵A和和A2，A3，A4如下：如下：0100010000000100010100010A 10000010000010100020001012A第七章：图论第七章：图论01000100000002000202000203A10000010000020200040002024A =2，所以，所以v1到到v2长度为长度为3的路有的路有2条，它们分别是：条，它们分别是：v1v2v1v2和和v1v2v3v2。 =1，所以，所以v1到到v3长度为长