第七章 图论第一节. 图的基本概念定义7-1.1 一个图是一个三元组 .

1、第七章第七章 图论图论第一节第一节. 图的基本概念图的基本概念定义定义7-1.1 一个图是一个三元组一个图是一个三元组 ,其中其中V(G)V(G)是一个是一个非空的非空的结点集合结点集合, ,E(G)E(G)是边集合是边集合, , G是从边集合到结点无序偶是从边集合到结点无序偶( (有序偶有序偶) )集合上的映集合上的映射射. .注注:1):1)图也可简记为图也可简记为G=,G=,这里这里V V是结点集是结点集,E,E是是 边集边集. . 2) 2)图可以用一个具体的图形来表示图可以用一个具体的图形来表示, ,也可以用也可以用 一个抽象的三元组来表示一个抽象的三元组来表示. . 例例.用三元组

2、给出图用三元组给出图G=如下如下: : V(G)=a,b,c,d, V(G)=a,b,c,d, E(G)= E(G)=e1, ,e2, ,e3, ,e4, ,e5, ,e6 G( (e1)=(a,b),)=(a,b),G( (e2)=(a,c),)=(a,c),G( (e3)=(b,d),)=(b,d),G( (e4)=(b,c),)=(b,c),G( (e5)=(d,c),)=(d,c),G( (e6)=(a,d).)=(a,d). 它的图形如下图它的图形如下图( (a)a)或或( (b)b)所示所示: : a a a a b d b d b d b d c c c c (a) (b) (a

3、) (b) 定义定义: 1)无序偶和有序偶无序偶和有序偶;无向边和有向边无向边和有向边; 2)有向图有向图;无向图无向图;混合图混合图. 注注:今后我们不讨论混合图今后我们不讨论混合图,而只讨论有向图和无而只讨论有向图和无 向图向图. 下图中的下图中的(a)和和(b)分别是有向图和混合图的例子分别是有向图和混合图的例子: (a) (b) 定义定义: 邻接点邻接点:由一条有向或无向边连接的两个结点由一条有向或无向边连接的两个结点. 邻接边邻接边:连接同一结点的两条边连接同一结点的两条边. 孤立结点孤立结点:不与任何结点相邻接的结点不与任何结点相邻接的结点. 自回路自回路(环环):连接同一结点的边

4、连接同一结点的边. 零图零图:仅有若干个孤立结点而没有边的图仅有若干个孤立结点而没有边的图. 平凡图平凡图:仅有一个孤立结点的图仅有一个孤立结点的图. 注注:环既可以看作是有向边环既可以看作是有向边,也可以看作是无向边也可以看作是无向边. 定义定义7-1.2(结点的度数结点的度数deg(v v) 与结点与结点 v v 关联的边数称为该结点的度数关联的边数称为该结点的度数,记记 为为deg(v v). 定义定义:图的最大度图的最大度(G)和和最小度最小度(G). 定理定理7-1.1每个图中每个图中,所有结点的度数之和恰好等所有结点的度数之和恰好等 于该图的边数的两倍于该图的边数的两倍,即有即有

5、deg(v v)=2|E|. 利用这一定理以及奇数和偶数的基本性质利用这一定理以及奇数和偶数的基本性质,不难不难证明下面有用的结果证明下面有用的结果: 定理定理7-1.2在任何图中在任何图中,度数为奇数的结点个数必度数为奇数的结点个数必 为偶数为偶数. 定义定义7-1.3(有向图中结点的出度有向图中结点的出度deg+(v v)和入度和入度 deg-(v v) 显然显然,在任何有向图中在任何有向图中,对任一结点对任一结点v v都有都有 deg+(v v)+ deg-(v v)= deg(v v). 定理定理7-1.3 在任何有向图中在任何有向图中,所有结点的入度之和所有结点的入度之和 必等于它们

6、的出度之和必等于它们的出度之和. 证明证明:因为有向图中的每一条有向边都恰好对应因为有向图中的每一条有向边都恰好对应 一个出度和一个入度一个出度和一个入度.故所有结点的出度之故所有结点的出度之 和恰好等于有向边的总数和恰好等于有向边的总数.同样地同样地, 所有结所有结 点的入度之和恰好也等于有向边的总数点的入度之和恰好也等于有向边的总数.因因 此它们相等此它们相等. 定义定义7-1.4(平行边平行边,多重图多重图,简单图简单图) 平行边平行边:连接同一对结点如有多于一条边连接同一对结点如有多于一条边,则称该则称该 图有平行边图有平行边. 多重图多重图:有平行边的图有平行边的图. 简单图简单图:

7、没有平行边没有平行边,也没有环的图也没有环的图. 定义定义7-1.5(完全图完全图)每对结点间都恰有一条边相连每对结点间都恰有一条边相连 的图称为完全图的图称为完全图. 有有n个结点的完全图记为个结点的完全图记为 Kn. 定理定理7-1.4 n个结点的无向完全图个结点的无向完全图 Kn的边数为的边数为 |E|=(1/2)n(n-1). 证明证明:根据完全图的定义根据完全图的定义,它的任意两个结点间都它的任意两个结点间都 恰好有一条边相连恰好有一条边相连,而从个结点中任取两点而从个结点中任取两点 的所有组合数等于的所有组合数等于 = (1/2)n(n-1). 这正是我们所要证明的这正是我们所要证

8、明的. 定义定义7-1.6(相对完全图的补图相对完全图的补图)给定简单图给定简单图G,由由G 中所有结点和所有能使中所有结点和所有能使G成为完全图的添加边组成为完全图的添加边组成的图称为成的图称为G的相对于完全图的补图的相对于完全图的补图,或简称为或简称为G的补图的补图,记为记为 .例如下面两图互为补图例如下面两图互为补图.2nCG 定义定义7-1.7(子图子图,生成子图生成子图)给定图给定图G=,如果如果有图有图G=,使得使得E E, V V,则称则称G是是G的的子图子图. 如果子图如果子图G还包含还包含G的所有结点的所有结点,则子图则子图G称为称为G的生成子图的生成子图. 定义定义(相对于

9、一个图的补图相对于一个图的补图)设图设图G=是图是图G=,的子图的子图. 若对另外一个图若对另外一个图G=有有E= E-E,且且V中仅包含中仅包含E的边所关联的结点的边所关联的结点.则称则称G是的子图是的子图G关于图关于图G的补图的补图. 例如例如:下图中下图中(b)和和(c)都是都是(a)的子图的子图;(c)是是(b)相对于相对于(a)的补图的补图,但但(b)不是不是(c)相对于相对于(a)的补图的补图. (a) (b) (c) 例例:下图中下图中,(b)和和(c)都是都是(a)的子图的子图,且它们都是且它们都是(a)的生成子图的生成子图;又又(b)是是(c)的相对于的相对于(a)的补图的补

10、图,且且(c)也是也是(b)的相对于的相对于(a)的补图的补图.此外此外,(b)还和还和(c)互为互为关于完全图关于完全图(这里的完全图指的是这里的完全图指的是K4)的补图的补图. (a) K4 (b) (c) 定义定义7-1.9(图的同构图的同构)假设给定两个图假设给定两个图G=和和 G=,如果存在它们的结点集如果存在它们的结点集V与与V之之 间的一个一一映射间的一个一一映射g g: 使得使得 (或者或者 )是是G的一条边的一条边,当且仅当当且仅当 (或者或者 )是是G的一条边的一条边,则称图则称图G与与 图图G是两个同构的图是两个同构的图,记为记为G G. 容易看出，同构的图有如下一些性质

11、：容易看出，同构的图有如下一些性质： 1）结点数目相同；）结点数目相同； 2）边数相等；）边数相等； 3）度数相同的结点个数相等。）度数相同的结点个数相等。 但要注意的是：以上三个条件仅仅是两个图同构但要注意的是：以上三个条件仅仅是两个图同构的必要条件，而非充分条件。的必要条件，而非充分条件。iivv ),(jivve jivve,)(),(jivgvge )(),(jivgvge 例子：例子： 1）下面两个无向图是同构的。）下面两个无向图是同构的。 2）下面两个有向图也是同构的。）下面两个有向图也是同构的。 3)下面两个图中虽然结点个数下面两个图中虽然结点个数、边数以及度数相、边数以及度数相

12、同的结点个数都相同同的结点个数都相同, ,但是它们并不是同构的图但是它们并不是同构的图. . 第二节第二节. 路路, 回路与连通性回路与连通性 定义定义7-2.1(路路,迹迹,通路和圈通路和圈) 给定图给定图G=,设设v v0,v v1,v vn V, e e1, e e2, e en E,其中其中e ei是关联于结点是关联于结点v vi-1和和v vi的边的边,我们把由结我们把由结点和边组成的交替序列点和边组成的交替序列 v v0 e e1v v1e e2 e env vn 称为是从点称为是从点v v0到点到点v vn的一条的一条路路. 这条路中边的条这条路中边的条 数称为这条数称为这条路的

13、长度路的长度.当当v v0=v vn时时,称这条路为一条称这条路为一条 回路回路. 若一条路中所有的边均不相同若一条路中所有的边均不相同,称之为称之为迹迹.若若 这条路中所有的结点均不相同这条路中所有的结点均不相同,称之为称之为通路通路. 当当v v0=v vn而其余结点均不相同时而其余结点均不相同时,称之为称之为圈圈. 例子例子. 在下面的图中找出一条路在下面的图中找出一条路,一条迹一条迹,一条通一条通 路和一个圈来路和一个圈来. v v1 e e1 e e2 e e3 v v2 v v3 e e4 e e5 e e6 e e7 v v4 e e8 v v5 定理定理7-2.1在一个有在一个

14、有n个结点的图中个结点的图中, 如果从结点如果从结点v vj j到结点到结点v vk k存在一条路存在一条路,那么从结点那么从结点v vj j到结点到结点v vk k 必存在一条边数至多为必存在一条边数至多为n-1的路的路. 推论推论.在一个有在一个有n个结点的图中个结点的图中, 如果从结点如果从结点v vj j到到 结点结点v vk k存在一条路存在一条路,那么从结点那么从结点v vj j到结点到结点v vk k必存必存 在一条边数至多为在一条边数至多为n-1的通路的通路. 定义定义7-2.2(点的连通性点的连通性)设设G为无向图为无向图,若在结点若在结点v vj j 与结点与结点v vk

15、k之间存在一条之间存在一条,路则称结点路则称结点v vj j与结点与结点v vk k 是连通的是连通的. 注：不难证明，结点之间的连通性是结点集合注：不难证明，结点之间的连通性是结点集合V 上的一个等价关系，即它满足自反性，对称性和上的一个等价关系，即它满足自反性，对称性和 传递性。由此可以根据结点之间有无连通性来将传递性。由此可以根据结点之间有无连通性来将 结点集合进行分类：把凡是连通的结点放在同一结点集合进行分类：把凡是连通的结点放在同一 个类中。这样得到的每个类中的所有结点和相应个类中。这样得到的每个类中的所有结点和相应的边作成的子图称为是原图的一个的边作成的子图称为是原图的一个连通分支

16、连通分支。图。图G的连通分支的个数记为的连通分支的个数记为W(G)。例如，下面的例如，下面的图有三个连通分支，即图有三个连通分支，即W(G)=3。 定义定义7-2.3(连通图连通图)若图若图G只有一个连通分支只有一个连通分支,即有即有 W(G)=1,则称它是一个连通图则称它是一个连通图. 定义定义7-2.4(点割集点割集,割点割点)设无向图设无向图G=为一连为一连 通图通图,若有点集若有点集V1 V,使得在图中删去了点集使得在图中删去了点集V1中中 所有的结点后所有的结点后,所得子图是不连通的图所得子图是不连通的图.而从图中而从图中删删 去点集去点集V1的任一真子集后的任一真子集后,得到的子图

17、仍是连通图得到的子图仍是连通图. 则称点集则称点集V1是图是图G的一个点割集的一个点割集.若点割集中恰只若点割集中恰只有一个结点有一个结点,则称它是该图的一个割点则称它是该图的一个割点. 定义定义7-2.5(边割集边割集,割边割边)设无向图设无向图G=为一为一 连通图连通图,若有边集若有边集E1 E,使得在图中删去了边集使得在图中删去了边集 E1中所有的边后中所有的边后,所得子图是不连通的图所得子图是不连通的图.而从图而从图 中删去边集中删去边集E1的任一真子集后的任一真子集后,得到的子图仍是得到的子图仍是连通图连通图.则称边集则称边集E1是图是图G的一个的一个边割集边割集.若边割若边割集中恰

18、只有一条边集中恰只有一条边,则称它是该图的一个则称它是该图的一个割边割边,也也称为一个称为一个桥桥. 定义定义(点连通度点连通度)设设G是一个图，则定义是一个图，则定义 k k(G)=min|V1|:V1是是G的点割集的点割集 为图的为图的点连通度点连通度(或或连通度连通度). 例例.对完全图对完全图Kp来说来说,显然有显然有 k k(Kp)=p-1. 定义定义(边连通度边连通度)设设G是一个图，则定义是一个图，则定义 (G)=min|E1|:E1是是G的边割集的边割集 为图的为图的边连通度边连通度.对于对于平凡图平凡图，也即仅由一个孤，也即仅由一个孤立结点作成的图立结点作成的图G,可以规定有

19、可以规定有(G)=0.此外此外,对于对于任何不连通的图任何不连通的图G,也有也有(G)=0. 定理定理7-2.2 对任何一个图对任何一个图G有有 k k(G) (G) (G), 这里这里k k(G)是点连通度是点连通度,(G)是边连通度是边连通度,而而(G)是是图的最小度图的最小度. 证明证明 1）根据图的最小度以及边连通度的定义易见）根据图的最小度以及边连通度的定义易见,不不 等式等式(G) (G)总是成立的总是成立的. 2)下面来证明不等式下面来证明不等式k k(G) (G). 情形一情形一.若若(G)=1,也即图也即图G有一条割边有一条割边,此时显然也有此时显然也有k k(G)=1(因为

20、只要把这条割边的任一个端点删去因为只要把这条割边的任一个端点删去,该图就该图就一定成为不连通图了一定成为不连通图了),故结论已成立故结论已成立. 情形二情形二.若若(G)2,则可从图中删去某则可从图中删去某(G)条边条边,使之不连使之不连通通;然而若从那然而若从那(G)条边中删去条边中删去(G)-1条边条边,得到的图仍得到的图仍是连通的是连通的,且在这样得到的子图中恰有一个桥且在这样得到的子图中恰有一个桥e e=(u u,v v).对对于那于那(G)-1条边中的每一条边条边中的每一条边,都选取一个不同于都选取一个不同于u u和和v v的的结点结点,把这些结点全部删去把这些结点全部删去,就至少删

21、掉了图中的就至少删掉了图中的(G)-1条边条边.如果这样得到的图是不连通图如果这样得到的图是不连通图,就有就有k k(G) (G)-1 (G);如果这样得到的图仍是连通图如果这样得到的图仍是连通图,则则e e仍然是桥仍然是桥,这时这时再删去结点再删去结点u u或者或者v v,就必然得到一个不连通的图就必然得到一个不连通的图,故有故有k k(G) (G).这就完成了我们的证明这就完成了我们的证明. (注注)下面的图中容易看出有下面的图中容易看出有 k k(G)=2， (G)=3， (G)=4， 这对定理这对定理7-2.2的结论也给出一个例证的结论也给出一个例证. 定理定理7-2.3一个无向连通图

22、一个无向连通图G中的结点中的结点v v是图是图G的割点的的割点的 充分必要条件是充分必要条件是:存在两个结点存在两个结点u u和和w w,使得连接结点使得连接结点u u 和和w w的每一条路都通过结点的每一条路都通过结点v v. 证明证明:1)必要性必要性.设结点设结点v v是图是图G的割点的割点.那么在图那么在图G中删去中删去 该点就得到一个不连通的图该点就得到一个不连通的图F,于是于是F至少有两个连通分至少有两个连通分支支F1和和F2,分别从分别从F1和和F2中各任取一点中各任取一点u u和和w w,由于原图由于原图G 是连通的是连通的,而在去掉割点而在去掉割点v v后得到的图后得到的图F

23、中它们不再连通中它们不再连通, 这就表明在图这就表明在图G中连接这两个结点的任一条路必定都经中连接这两个结点的任一条路必定都经 过结点过结点v v. 2)充分性充分性.设图设图G中存在两个结点中存在两个结点u u和和w w,使得连接使得连接 结点结点u u和和w w的每一条路都通过结点的每一条路都通过结点v v.那么显然那么显然,只要去掉只要去掉 结点结点v v,u u和和w w这两个结点就会变成不连通的这两个结点就会变成不连通的,从而图从而图G也也 就变成不连通的图就变成不连通的图.这就证明了结点这就证明了结点v v必为图的割点必为图的割点. 注意注意: 1)无向图的连通性不能直接推广到有向

24、图无向图的连通性不能直接推广到有向图. 2)在有向图中可以定义在有向图中可以定义可达性可达性如下如下: 如果从结点如果从结点u u到结点到结点v v有一条有一条(有向的有向的)路相通路相通, 则称从点则称从点u u到点到点v v可达可达. 注意注意,结点间的可达性是自反的和传递的结点间的可达性是自反的和传递的,但一但一 般不是对称的般不是对称的. 3)如果在一个有向图中从点如果在一个有向图中从点u u到点到点v v可达可达,则称从则称从 点点u u到点到点v v的所有的所有(有向的有向的)路中最短的那条路的路中最短的那条路的 长度为结点长度为结点u u到到v v的距离的距离,记为记为d d.

25、如果从结点如果从结点u u到到v v不可达不可达,则记则记d d=. 注意注意,当从点当从点u u到点到点v v可达时可达时,从点从点v v到点到点u u不一定不一定 也可达也可达;即使从点即使从点v v到点到点u u也可达也可达,一般也不一定一般也不一定 有有d d=d d. 定义定义(无向图的直径无向图的直径)设设G=是一个无向图是一个无向图,称称 D=maxd d,u u,v v V 为图为图G的直径的直径. 第三节第三节. 图的矩阵表示图的矩阵表示 定义定义7-3.1(图的邻接矩阵图的邻接矩阵)设设G=是一个简单是一个简单 图图(即没有平行边和环的图即没有平行边和环的图),它有它有n个

26、结点个结点 V=v v1,v v2,.,v vn, 我们称我们称n阶方阵阶方阵A(G)=(aij)为为G的邻接矩阵的邻接矩阵,这里这里 aij=1(当当v vi邻接邻接v vj时时), aij=0(当当v vi不邻接不邻接v vj时时). 例子例子.下图下图(a)的邻接矩阵如的邻接矩阵如(b)所示所示. v v1 v v2 v v5 A(G)= v v3 v v4 (a) (b)0110010011010110010111110 注注:1)无向图无向图的邻接矩阵必为的邻接矩阵必为对称阵对称阵;而而有向图有向图的邻接矩的邻接矩 阵一般不一定是对称阵阵一般不一定是对称阵;显然显然,一个图为一个图为

27、零图零图(全由全由 孤立结点构成的图孤立结点构成的图)的充分必要条件是它的邻接矩的充分必要条件是它的邻接矩 阵必为阵必为零阵零阵. 2)有向图有向图(无向图无向图)中中邻接矩阵中第邻接矩阵中第i i行元素之和恰为行元素之和恰为 结点结点v vi i的的出度出度(度度). 3)图的邻接矩阵一般说来与结点的书写次序有关图的邻接矩阵一般说来与结点的书写次序有关. 4)给定两个同阶矩阵给定两个同阶矩阵,如果能通过对其中任一矩阵的如果能通过对其中任一矩阵的 某些行作次序调换某些行作次序调换,同时对相应的列作同样的调换同时对相应的列作同样的调换, 就可将它变成另一个矩阵就可将它变成另一个矩阵,就称这两个矩

28、阵是彼此就称这两个矩阵是彼此 置换等价的矩阵置换等价的矩阵.显然显然,从同一个图作出的任意两个从同一个图作出的任意两个 邻接矩阵一定是置换等价的矩阵邻接矩阵一定是置换等价的矩阵. 问题问题:怎样计算图中从一个结点怎样计算图中从一个结点v vi i到另一个结点到另一个结点 v vj j的长度为的长度为k k的路的条数的路的条数? 定理定理7-3.1设给定图设给定图G和它的邻接矩阵和它的邻接矩阵A(G),用矩阵乘法用矩阵乘法 计算出邻接矩阵计算出邻接矩阵A(G)的的k k次幂次幂Ak k(G),则矩阵则矩阵Ak k(G)中第中第I I 行第行第j j列元素列元素bij ij的值即为图的值即为图G中

29、中从结点从结点v vi i到结点到结点v vj j的长的长 度为度为k k的路的条数的路的条数. 例例1.给出图给出图G(见下图见下图(a),要求其中要求其中(1)从结点从结点v v1到结点到结点v v2的的长度为长度为3的路的条数的路的条数;(2)从结点从结点v v2到结点到结点v v2的长度为的长度为3以及以及长度为长度为4的回路的条数的回路的条数. 解解:容易算出此图的邻接矩阵容易算出此图的邻接矩阵A如如(b)所示所示. v v5 v v1 v v2 A= v v4 (a) v v3 (b)0110000000000100010100010 计算给出计算给出 A2= A3= A4 = 结

30、论结论:(1)从结点从结点v v1到结点到结点v v2有有2条长度为条长度为3的路的路. (2)从结点从结点v v2到结点到结点v v2没有长度为没有长度为3的回路的回路. (3)从结点从结点v v2到结点到结点v v2有有4条长度为条长度为4的回路的回路.100100000000101000200010110010000000020200040002020110000000000200020200020 定义定义7-3.2(有向图的可达性矩阵有向图的可达性矩阵)令令G是一个简单是一个简单 有向图有向图,其结点数为其结点数为|V|=n,并设已将图的所有结点并设已将图的所有结点 进行了编序进行了

31、编序: V=v v1,v v2,.,v vn.则称如下定义的则称如下定义的n阶阶 方阵方阵P=(p pij)为图为图G的可达性矩阵的可达性矩阵,这里这里 p pij=1 (如果从到至少有一条路如果从到至少有一条路)或者或者 p pij=0 (如果从到不存在路如果从到不存在路). 注注:可达性矩阵的概念也容易推广到无向图中可达性矩阵的概念也容易推广到无向图中,只只 要在无向图中将每条无向边改成两条有向边要在无向图中将每条无向边改成两条有向边 就行了就行了. 问题问题:怎样从图的邻接矩阵求出其可达矩阵呢怎样从图的邻接矩阵求出其可达矩阵呢? 解答解答:设设n阶矩阵阶矩阵A是图是图G的邻接矩阵的邻接矩

32、阵,用矩阵乘法用矩阵乘法 依次算出依次算出A2,A3,.,An,然后计算出矩阵然后计算出矩阵 B=A+A2 +A3+.+An, 再在矩阵再在矩阵B中将所有的非零元素都换成数中将所有的非零元素都换成数1;而而B中为零的元素中为零的元素仍仍保持数零不动保持数零不动,这样得到的矩阵这样得到的矩阵K就是图就是图G的可达性矩阵的可达性矩阵. 例子例子.设图设图G的邻接矩阵是的邻接矩阵是 A= 求出它的可达性矩阵来求出它的可达性矩阵来.0001101111000010 解解:计算给出计算给出 A2= A3= A4= B= + + + = 0010111110121100110021221121101210

33、12323332221121001011111012110011002122112110121012323332221121000110111100001021237477645532431111111111111111 第四节第四节. 欧拉图与哈密尔顿图欧拉图与哈密尔顿图 欧拉欧拉(L. Euler)与哥尼斯堡与哥尼斯堡(Knigberg)七桥问题七桥问题 C A B D C A B D 定义定义7-4.1(欧拉路与欧拉回路欧拉路与欧拉回路)设图设图G无孤立结点无孤立结点, 若若G中存在一条路中存在一条路,它经过图它经过图G中每条边一次且只中每条边一次且只 经过一次经过一次,则称这条路为一条

34、欧拉路则称这条路为一条欧拉路;如果它还是如果它还是 一条回路一条回路,则称它为一条欧拉回路则称它为一条欧拉回路.我们称有欧拉我们称有欧拉回路存在的图是一个欧拉图回路存在的图是一个欧拉图. (注注)我们不讨论有孤立点的图中有无欧拉路或欧我们不讨论有孤立点的图中有无欧拉路或欧 拉回路存在的问题拉回路存在的问题. 定理定理7-4.1 设设G是一个无孤立结点的无向图是一个无孤立结点的无向图,那么那么 G中存在一条欧拉路中存在一条欧拉路,当且仅当当且仅当G是连通的是连通的,且恰有且恰有 零个或两个奇数度结点零个或两个奇数度结点. 例子例子(哥尼斯堡七桥问题哥尼斯堡七桥问题).由于由于该图中有该图中有4个

35、奇结个奇结 点点,从而该图中必不存在欧拉路或欧拉回路从而该图中必不存在欧拉路或欧拉回路. 有关一笔画与多笔画问题的结论有关一笔画与多笔画问题的结论: (1)无孤立结点的无向图无孤立结点的无向图G是一个一笔画的充分必是一个一笔画的充分必 要条件是要条件是:它是一个连通图它是一个连通图,且奇结点的个为且奇结点的个为0 或为或为2. (2)设设G是一个连通无向图是一个连通无向图,它有它有2n个个(n1)奇结点奇结点. 那么图那么图G必是一个必是一个n笔画笔画,且最少是一个且最少是一个n笔画笔画. 欧拉路及欧拉回路的概念在有向图中的推广欧拉路及欧拉回路的概念在有向图中的推广: 定义定义7-4.2(单向

36、欧拉路与单向欧拉回路单向欧拉路与单向欧拉回路)设设G是一是一 个有向图个有向图,如果如果G中存在一条有向路中存在一条有向路(有向回路有向回路),它它 经过图中每条有向边恰好一次经过图中每条有向边恰好一次,则称它为一条单则称它为一条单 向欧拉路向欧拉路(单向欧拉回路单向欧拉回路). 定理定理7-4.2设设G是一个有向图是一个有向图. (1)G中存在一条单向欧拉路的充分必要条件是中存在一条单向欧拉路的充分必要条件是: G是连通图是连通图,且除去两个结点外且除去两个结点外,其余每个结点其余每个结点 的入度等于出度的入度等于出度;在剩下的两个结点中在剩下的两个结点中,一个结一个结 点的入度比出度大点的

37、入度比出度大1,另一个结点的入度则比出另一个结点的入度则比出 度小度小1. (2) G中存在一条单向欧拉回路的充分必要条件中存在一条单向欧拉回路的充分必要条件 是是: G是连通图是连通图,且每个结点的入度等于出度且每个结点的入度等于出度. 定义定义7-4.3(哈密尔顿路与哈密尔顿回路哈密尔顿路与哈密尔顿回路)设设G是一是一 个图个图,若若G中存在一条路中存在一条路(回路回路),它经过图中每个结它经过图中每个结 点恰好一次点恰好一次(在回路的情形在回路的情形,起始点允许重复起始点允许重复),则则 称它是一条哈密尔顿路称它是一条哈密尔顿路(回路回路).我们称有哈密尔顿我们称有哈密尔顿回路存在的图是

38、一个哈密尔顿图回路存在的图是一个哈密尔顿图. 定理定理7-4.3(一个图有哈密尔顿回路的必要条件一个图有哈密尔顿回路的必要条件) 若图若图G=有哈密尔顿回路有哈密尔顿回路,则对结点集则对结点集V的每个非空子集的每个非空子集S均有不等式均有不等式 W(G-S)|S| 成立成立,其中其中W(G-S)表示子图表示子图G-S中的连通分支的中的连通分支的 个数个数.(证明略证明略) 例子例子. (1)用定理用定理7-4.3可证下图不是一个哈密尔顿图可证下图不是一个哈密尔顿图. (2)但定理但定理7-4.3仅仅是个仅仅是个 必要条件必要条件,而非充分条而非充分条 件件.右图右图(Petersen图图)就就

39、 是一个满足定理是一个满足定理7-4.3 但并非哈密尔顿图的例子但并非哈密尔顿图的例子. 定理定理7-4.4(一个图有哈密尔顿路的充分条件一个图有哈密尔顿路的充分条件) 设设G是一个有是一个有n个结点的简单图个结点的简单图.如果如果G中每中每 一对结点的度数之和都大于或等于一对结点的度数之和都大于或等于n-1,则则G中存中存 在一条哈密尔顿路在一条哈密尔顿路. (证明略证明略) 注意注意:此定理仅是充分条件此定理仅是充分条件 而非必要条件而非必要条件,例如右图显例如右图显 然是一个哈密尔顿图然是一个哈密尔顿图,当然当然 其中存在哈密尔顿路其中存在哈密尔顿路.然而然而 它的任一对结点度数之和它的

40、任一对结点度数之和 都小于该图的结点总数都小于该图的结点总数. 例子例子. 证明下图中不存在哈密尔顿路证明下图中不存在哈密尔顿路. A B B B A A A A B B A B A A A B 定理定理7-4.5(一个图有哈密尔顿路的充分条件一个图有哈密尔顿路的充分条件) 设设G是一个有是一个有n个结点的简单图个结点的简单图.如果如果G中每中每 一对结点的度数之和都大于或等于一对结点的度数之和都大于或等于n,则则G中存在中存在一条哈密尔顿回路一条哈密尔顿回路.(证明略证明略) 附附:哈密尔顿的周游世界问题哈密尔顿的周游世界问题(1859年年) 2 15 1 16 14 3 20 4 17 1

41、3 19 18 12 5 11 9 6 10 8 7 第五节第五节. 平面图平面图 定义定义7-5.1(平面图平面图)设设G是一个无向图是一个无向图,如果能够把如果能够把 G的所有结点和边画在平面上的所有结点和边画在平面上,使得任何两条边除使得任何两条边除 了可能在结点处相交外了可能在结点处相交外,没有其它的交点没有其它的交点.则称它则称它 是一个平面图是一个平面图.以下我们仅研究连通的平面图以下我们仅研究连通的平面图. 例子例子.下图下图(a)可以重新画成可以重新画成(b)的样子的样子,所以图所以图(a)仍仍 是平面图是平面图. (a) (b) 定义定义7-5.2(连通平面图的面连通平面图的

42、面,面的边界面的边界)设设G是一个是一个 连通平面图连通平面图.由图由图G中的边所包围的区域称为图中的边所包围的区域称为图G 的一个的一个面面(每个图也包含一个无限的每个图也包含一个无限的、位于图的位于图的外部的面外部的面),而包围该面的各个边就构成这个而包围该面的各个边就构成这个面的面的边界边界. r5 例子例子.右图有右图有6个结点个结点,9条边条边.它把平面它把平面 划分成划分成5个面个面:r1,r2,r3,r4和一个无限的和一个无限的 C 面面r5.其中的三个面其中的三个面r1,r2和和r4的边界均的边界均 A r4 由一条回路组成由一条回路组成,面面r3的边界虽然并不的边界虽然并不

43、Br2 F E 是一条回路是一条回路,但如果按照下面的方式但如果按照下面的方式 r1 r3 走完它的边界走完它的边界:CDEFEC(或顺时针走或顺时针走 D 也可也可),那么它的边界也作成一条回路那么它的边界也作成一条回路. 今后我们对面的边界就规定为用这样今后我们对面的边界就规定为用这样 的方式定义的一条回路的方式定义的一条回路. 定义定义(平面图中面的次数平面图中面的次数)设设G是一个连通的平面是一个连通的平面 图图,按照上述约定按照上述约定,它把整个平面分成的每个面它把整个平面分成的每个面ri i 的边界都是一条回路的边界都是一条回路.称该回路的长度为这个面称该回路的长度为这个面的次数的

44、次数,记为记为deg(ri i). 例如例如,在上面那个平面图中有在上面那个平面图中有 deg(r1)=3, deg(r2)=3, deg(r3)=5, deg(r4)=4, deg(r5)=3. 定理定理7-5.1 设设G是一个有限平面图是一个有限平面图,则它的所有面则它的所有面 的次数之和等于边数的两倍的次数之和等于边数的两倍. 定理定理7-5.2 设设G是一个非平凡的有限是一个非平凡的有限连通平面图连通平面图, 它有它有v v个结点个结点,e e条边和条边和r r个面个面,则有下述欧拉公式则有下述欧拉公式 成立成立: v v - e e + r r =2. 证明证明(对图的边数用归纳法对

45、图的边数用归纳法): (1)若若G只有一条边只有一条边,则则v v=2,e e=1,r r=1,结论显然成立结论显然成立. (2)(归纳假设归纳假设)设当设当G有有k k条边时结论成立条边时结论成立: v vk k - e ek k + r rk k =2. (1) (3)现在设现在设G有有k k+1条边条边.即在原来有即在原来有k k条边的连通图条边的连通图G1中中 添加一条边添加一条边,使之仍为连通图使之仍为连通图(G1中的结点数中的结点数、边数与面边数与面 数满足数满足(1)式式).这只能有以下两种情况这只能有以下两种情况: 1)在在G1中增加一个新结点中增加一个新结点 ,使之与使之与G

46、1中某个结点中某个结点 相连相连. 此时有此时有v vk k+1= v vk k+1,e ek k+1= e ek k+1,r rk k+1=r rk k,于是欧拉公式于是欧拉公式 v vk k+1 - e ek k+1 + r rk k+1 =2仍然成立仍然成立. 2)将将G1中某两个结点中某两个结点 与与 之间添加一条新的边之间添加一条新的边.此时有此时有 v vk k+1=v vk k, e ek k+1=e ek k+1, r rk k+1=r rk k(此处证明细节略去此处证明细节略去),于于 是此时欧拉公式是此时欧拉公式v vk k+1 - e ek k+1 + r rk k+1

47、=2仍然成立仍然成立. 定理定理7-5.3 设设G是一个有是一个有v v个结点和个结点和e e条边的简单条边的简单 连通平面图连通平面图.若若v v3,则有则有e e3v v-6. 证明证明:设设G有有r r个面个面. (1)若若v v3,e e3,则结论显然成立则结论显然成立. (2)若若v v3,e e4,一方面一方面由定理由定理7-5.1知知:G的所有面的所有面 的次数之和等于的次数之和等于2e e,另一方面另一方面,由于它是简单图由于它是简单图,故故 每个面的次数至少为每个面的次数至少为3,从而又有从而又有2e e3r r,即即r r(2/3)e e.将此不等式代入欧拉公式即得将此不等

48、式代入欧拉公式即得 2=v v-e e+r rv v-e e+(2/3)e e 2v v-(1/3)e e 63v v-e e e e3v v-6. 例子例子. (1)证明证明K5不是平面图不是平面图. 解解:在在K5中有中有v v=5个结点个结点, e e=10条边条边,因而对它有因而对它有 e e=109=3v v-6, 根据定理根据定理7-5.3,它不是平面图它不是平面图. K5 (2)证明证明K3,3不是平面图不是平面图. 解解:在在K3,3中有中有v v=6个结点个结点,e e=9条边条边,因而对它有因而对它有 e e=98=2v v-4, 故它不是平面图故它不是平面图. K3,3

49、定义定义7-5.3(在二度结点内同构的图在二度结点内同构的图)设设G1和和G2是是 两个图两个图,如果它们同构如果它们同构,或者通过反复或者通过反复(有限次有限次)插插 入或除去度数为入或除去度数为2的结点后的结点后,能成为同构的图能成为同构的图,则称则称 它们是在二度结点内同构的图它们是在二度结点内同构的图. 插入和除去二度结点的简单例子插入和除去二度结点的简单例子: (a) (b) 定理定理7-5.4(Kuratowski定理定理) 一个图是平面图一个图是平面图,当当 且仅当它不包含与且仅当它不包含与K3,3或或K5在在2度结点内同构的度结点内同构的子图子图.(证明略证明略) 第六节第六节

50、. 对偶图与着色对偶图与着色 定义定义7-6.1(对偶图对偶图)给定平面图给定平面图G=,设它有设它有n 个面个面F1,F2,Fn,若有另外一个图若有另外一个图G*=满足满足 如下三条件如下三条件,则称图则称图G*是图是图G的对偶图的对偶图: (a)对图对图G的每个面的每个面,G的内部有且仅有一个结点的内部有且仅有一个结点 v v*i i G*. (b)对于图对于图G中任意两个面中任意两个面Fi i和和Fj j之间的每一条公之间的每一条公 共边界共边界e ek k,都存在一条边都存在一条边e e*k k G*,使得使得e e*k k =(v v*i i, v v*j j),且且e e*k k和

51、和e ek k相交相交. (c)当且仅当单独一条边当且仅当单独一条边e ek k构成图构成图G的某一个面的某一个面Fi i 的边界时的边界时,(b)中与中与e ek k对应的边对应的边e e*k k =(v v*i i,v v*i i)是是 一个环一个环,且且e e*k k和和e ek k相交相交. (注注)显然显然,若图若图G*是图是图G的对偶图的对偶图,那么图那么图G也是图也是图 G*的对偶图的对偶图,从而它们必是互为对偶的图从而它们必是互为对偶的图. 对偶图的简单例子对偶图的简单例子:下图中实线和虚线作成的两下图中实线和虚线作成的两个图是互为对偶的图个图是互为对偶的图. (注注)若图若图

52、G*与图与图G是互为对偶的图是互为对偶的图,那么那么,只要两个只要两个 图中有一个图是连通的平面图图中有一个图是连通的平面图,另一个图必也是另一个图必也是连通的平面图连通的平面图. 定义定义(自对偶图自对偶图)若图若图G的对偶图恰与的对偶图恰与G同构同构,则称则称 图图G是一个自对偶图是一个自对偶图. 例子例子.由右图容易看出由右图容易看出, 完全图完全图K4就是一就是一 个自对偶图个自对偶图. (1)四色定理的历史简介四色定理的历史简介: 1)Francis Guthrie(1899,后成为位于开普顿的南非大学后成为位于开普顿的南非大学 数学教授数学教授):1850年前后提出四色猜想年前后提

53、出四色猜想. 2)Augustus de Morgan 1852年年10月月23日给日给William R. Hamilton爵士的信提出四色猜想爵士的信提出四色猜想. 3)A. Cayley先后于先后于1878年年6月月13日和日和1879年在伦敦数学年在伦敦数学 会的会议上以及英国皇家地理协会会报上两次重新提会的会议上以及英国皇家地理协会会报上两次重新提 出这一问题出这一问题. 4)A. B. Kempe和和G. Tait于于1879年给出第一个证明年给出第一个证明. 5)P. J. Heawood于于1890年指出了他们证明中的错误年指出了他们证明中的错误. 6)K. Appel, W.

54、 Haken和和J. Koch 于于1976年用计算机给年用计算机给 出完全的证明出完全的证明(发表的两篇论文长达发表的两篇论文长达139页页, 在在Illinois 大学的计算机上共花去大学的计算机上共花去1200小时的计算机时间小时的计算机时间). 地图的着色问题与对偶图的着色问题之间的联系地图的着色问题与对偶图的着色问题之间的联系: (1)将将地图的着色问题转化成对偶图的着色问题地图的着色问题转化成对偶图的着色问题. (2)对偶图的正常着色问题对偶图的正常着色问题. 定义定义(图的正常着色图的正常着色)设设G是一个图是一个图,对它的每个结点指定对它的每个结点指定 一种颜色一种颜色,使得没

55、有两个邻接的结点能有相同的颜色使得没有两个邻接的结点能有相同的颜色,这这 样的着色就称为是图样的着色就称为是图G的一种正常的着色的一种正常的着色. 定义定义(n色图和图的着色数色图和图的着色数)如果图如果图G在正常着色时用到在正常着色时用到n 种不同的颜色种不同的颜色,则称该图是一个则称该图是一个n-色的图色的图;对图对图G进行正进行正常着色所需的最少的颜色数称为图常着色所需的最少的颜色数称为图G的着色数的着色数,记为记为 (G). 定理定理7-6.1 对有对有n个结点的完全图个结点的完全图Kn,有有 (Kn)=n. 定理定理7-6.3( 五色定理五色定理) 对任何平面图对任何平面图G, 有有

56、 (G)5. (证明略证明略) 第七节第七节. 树与生成树树与生成树 定义定义7-7.1(树与森林树与森林) (1)一个连通且无回路的无向图称为树一个连通且无回路的无向图称为树. (2)树中度数树中度数1为的结点称为树叶为的结点称为树叶. (3)树中度数大于的结点称为分枝点或内点树中度数大于的结点称为分枝点或内点. (4)一个无回路的无向图称为森林一个无回路的无向图称为森林.显然显然,森林的每森林的每 个连通分支都是一棵树个连通分支都是一棵树. 森林和树的例子森林和树的例子: 定理定理7-7.1 给定图给定图T,则以下关于树的定义等价则以下关于树的定义等价: (1)T无回路且为连通图无回路且为

57、连通图; (2)T无回路且无回路且e e=v v-1,其中其中e e是边数是边数,v v是结点数是结点数; (3)T连通且连通且e e=v v-1; (4)T无回路无回路,但如果任意增加一条新的边但如果任意增加一条新的边,便得到便得到 一条且恰只得到一条回路一条且恰只得到一条回路; (5)T连通连通,但删去任何一条边后便不连通但删去任何一条边后便不连通; (6)T的每一对结点之间有唯一一条路的每一对结点之间有唯一一条路. 证明证明:(1)(2)(对结点数对结点数v v2用归纳法用归纳法.) 设设T无回路且为连通图无回路且为连通图,要证明要证明T无回路且无回路且e e=v v-1. 1)如果如果

58、v v=2,由于由于T无回路且连通无回路且连通,故必有故必有e e=1 e e=v v-1. 2)设结论对有设结论对有k k-1个结点的无回路连通图已经成立个结点的无回路连通图已经成立. 3)设图设图T有有v v=k k个结点个结点, ,它连通且无回路它连通且无回路.故它至少有一条故它至少有一条 边边e e1=(u,wu,w)的一个端点的一个端点u u度数为度数为1(否则图否则图T中就存在中就存在 一个结点度数均为偶数的子图一个结点度数均为偶数的子图T1, T1中必存在一条欧拉中必存在一条欧拉 回路回路,即图即图T中存在一条回路中存在一条回路,这是不可能的这是不可能的).从图从图T中去中去 掉

59、结点掉结点u u(边边e e1=(u,wu,w)也就同时被去掉也就同时被去掉,但但其它的边不其它的边不 受影响受影响),就得到一个有就得到一个有v v*=k k-1个结点的无回路的连通个结点的无回路的连通 图图T*.由归纳假设由归纳假设,在图在图T*中有中有e e*=v v*-1=k k-2.最后再将结最后再将结 点点u u和它关联的边和它关联的边e e1=(u,wu,w)添加到图添加到图T*中去就得到图中去就得到图 T,于是在图于是在图T中有中有v v= v v*+1=k k和和e e=e e*+1=k k-1=v v-1,从而从而 结论对有结论对有k k个结点的树依然成立个结点的树依然成立

60、. w w u u 证明证明:(2)(3) 设设T无回路且无回路且e e=v v-1,要证明要证明T连通且连通且e e=v v-1. 用反证法用反证法.若若T不连通不连通,设它有设它有k k2个分支个分支 T1,T2,Tk k, 因为每个分支都是无回路的连通图因为每个分支都是无回路的连通图,若设若设Ti i有有v vi i个结点个结点 和和e ei i条边条边,则由上证知则由上证知e ei i=v vi i-1,从而对图从而对图T有有 e e= e e1+e e2+.+e ek k=(v v1-1)+(v v2-1)+(v vk k-1) =(v v1+v v2+v vk k)-k k=v v