离散数学及其应用-第2版 课件汇 第7-12章 高级计数技术-格和布尔代数

第7章

高级计数技术第7章高级计数技术7.1递推方程7.2生成函数7.1递推方程定义7.1.1设序列

简记为

。序列

的递推方程是一个把

an用序列中在an

前面的一项或多项

ai(i<n)来表示的等式称作关于序列{an}的递推方程。例题例7.2.113世纪意大利数学家斐波那契（Fibonacci）提出了一个有趣的兔子繁殖问题：在一个岛上放了一对刚出生的兔子，其中一只公兔，一只母兔。经过两个月长成，长成后即可生育，假定每对兔子每个月都可以生出一对小兔，且新生的小兔也是一只公兔和一只母兔。如果兔子不会死去，也不会被运走，问12个月时岛上有多少对兔子?例题（续）解用

表示第

个月初的兔子对数，n是正整数。那么

f1=1（最初的兔子对数，第1个月的兔子对数）

f2=1（第2个月的兔子对数）f3=1+1=2（最初的一对加上它们的后代）

f4=2+1=3（第3个月的2对加上最初的一对的后代）f5=3+2=5（第4个月的3对加上第3个月2对的后代）

f6=5+3=8（第5个月的5对加上第4个月3对的后代）

f12=89+55=144（第11个月的89对加上第10个月55对的后代）12个月时岛上共有兔子144对。一般的，斐波那契数列满足下列递推方程数列

称作斐波那契数列，其中的每一个数也称作斐波那契数。例题在股票投资中，复合利息的作用是强大的。“股神”沃伦·巴菲特(Warren

Buffett)据说就是以年平均30%的复利战胜市场，从而成为举世瞩目的价值投资大师。假设他的初始投资为10000美元，年投资收益的复利是30%，那么在30年后账上的总资产有多少钱？解

令Pn表示n年后的总资产钱数。因为n年后账上的资产总额等于n-1年账上的资产加上第n年的投资收益，容易知道序列{Pn}满足递推关系例题（续）初始条件是P0=10000，我们可以知道代入初始条件，得将n=30代入，

26199956.44美元。常系数线性齐次递推方程的求解定义7.2.1设递推方程满足其中

为常数,,这个方程称为k阶常系数线性递推方程。

为k个初值。当

时，即称这个递推方程为齐次方程。

常系数线性齐次递推方程的求解定义7.2.2给定常系数线性齐次递推方程如下：（7.2）,求解该方程的基本方法是找到形如G(n)=rn的解，其中r是常数，即

等式两边同时除以rn-k，得

因此我们将形如方程

称为该递推方程的特征方程，特征方程的根r称为递推方程的特征根。定理定理7.2.1设g1(n)和g2(n)是递推方程(7.2)的两个解，c1,c2为任意常数，则c1g1(n)+c2

g2(n)也是这个递推方程的解。证明

将

g1(n)和g2(n)代入到方程(7.2)得，因此c1g1(n)+c2

g2(n)也是这个递推方程的解。

推论

若

是递推方程(7.2)的特征根，则

也是该递推方程的解，其中

是任意常数。以上推论说明

是递推方程的解。那么，除了这种形式的解以外，是否存在其他形式的解?为了解决这个问题，先定义通解。定义7.2.3能够表示递推方程（7.2）的每个解

的表达式称为该递推方程的通解。定理定理7.2.2设

是递推方程(7.2)不等的特征根，则

为该递推方程的通解，其中

是任意常数。证明

此定理是推广了定理7.2.1，证明类似。例题例7.2.1求下面递推方程的解：其中

，

。解递推方程的特征方程是

，它的根是2和-1。因此，递推方程的通解为c1,c2是常数。将初值

代入得解得,从而得到递推方程的解为，

定理定理7.2.3设

是递推方程（7.2）的不相等的特征根，且

ri的重数为ei，其中

那么该递推方程的通解是其中

为常数。

例题例7.2.4求解以下递推方程解

特征方程

为即

特征根是2，其重数是3，根据定理7.2.3

通解为代入初始条件，则有以下方程组解得

原方程的解为例题（续）解得

原方程的解为常系数线性非齐次递推方程的求解常系数线性非齐次递推方程的标准形是

（7.3）其中

f(n)是只依赖于n的函数。将

称作相伴的线性齐次递推方程。定理7.2.4设

是对应的相伴的线性齐次递推方程的通解，

是方程（7.3）的一个特解，则是递推方程（7.3）的通解。例题例7.2.5找出下述递推方程的通解：解

该方程对应相伴的线性齐次递推方程是

它的通解是c3n，其中c是常数。设特解

，其中c1,c2

是常数。代入递推方程得例题（续）整理得从而得线性方程组解得

因此

是一个特解，根据定理7.2.4，原方程的通解为初始条件

带入通解得,因此得原方程的通解为7.2生成函数生成函数是研究组合计数中的一个重要工具，其基本思想是把要计数或研究的离散数列同多项式或幂级数的系数一一对应起来，从而可以用数学分析的方法去研究这一数列，给出数列的一个显示解或渐近解。牛顿二项式系数与牛顿二项式定理定义7.3.1设r为实数，n为整数，引入形式符号称为牛顿二项式系数．定理定理7.3.1牛顿二项式定理．

设r为实数，则对一切实数

，有其中

生成函数的定义及其性质定义7.3.2设序列

，构造形式幂级数

称f(x)为序列

的生成函数。

定义7.3.2给出的生成函数有时叫做

的普通生成函数，以和这个序列的其他类型的生成函数相区别，序列

叫做f(x)的生成序列。例题例7.3.1设m是正整数，令ak=C(m,k)k=0,1,…m，

。那么序列{ak}的生成函数是什么？解这个序列的生成函数是由二项式定理可得

生成函数的性质设

是已知序列，它们的生成函数分别为若

为常数，则

若

，则

若

，则

若

生成函数的性质(续）(5)若

，则

(6)若

，则(7)若

，且

收敛，则

(8)若

为常数，则

(9)若

，则

，其中

为A(x)的导数。(10)若

，则

例题生成函数与序列是一一对应的。例7.3.2求序列{an}的生成函数

解

例题已知{an}的生成函数为

，求an.

解

因此我们可以得到

生成函数的应用例7.3.4求解递推方程

且初始条件

解

设序列

的生成函数为首先注意到例题（续）因为n>=1时有

且

所以有即得所以

指数型生成函数定义7.3.3

设{an}为序列，构造形式幂级数称

为{an}的指数型生成函数。例题设{an}是序列，求下列数列的指数生成函数

。（1）

，m为正整数；（2）an=1；（3）an=bn

；解（1）

（2）

（3）定理定理7.3.2

设

为多重集，则S的r-排列数由指数生成函数的展开式中

的系数给出。例题例7.3.10由1，2，3，4组成的5位数中，要求1出现不超过2次，但不能不出现，2出现不超过1次，3出现至多2次，4出现偶数次，求这样的5位数个数。解展开后

的

的系数为185，所以这样的5位数有185个。例题例7.3.11用3个1,2个2,5个3这十个数字能构成多少个偶的4位数？

解问题是求多重集

的4-排列数，且要求排列的末尾为2。因为根据已知条件，只能有2为末尾才为偶数，所以可把问题转换为求多重集

的3-排列数。其指数生成函数为展开后的

的系数为20，所以能组成20个四位数的偶数。第8章

图论图论研究图的点和线的关系及特点，是研究离散结构及其特性的重要数学分支。现实世界中，许多事务都可以抽象成点及它们之间的联系，都可以用图来描述。如哥尼斯堡七桥问题、Internet网、社会关系网络、交通运输网、电路网络等。第8章图8.1图的基本概念8.2通路与回路、连通的概念8.3图的表示8.4独立集、覆盖和支配集39ABCD图论起源公元十八世纪有这样一个问题：在东普鲁士有个哥尼斯堡城（

konigsberg，现名为加里宁格勒；现属于俄罗斯联邦）。哥尼斯堡城位于pregel河畔，河中有两个岛，城市中的各个部分由七座桥相连。

最早引入图论处理的问题就是哥尼斯堡七桥问题。

1736年，瑞士数学家L.Eluer（欧拉）在他发表的“哥尼斯堡七座桥”的著名文章中阐述了解决这个问题的观点，从而被誉为图论之父。

当时，城中的居民热衷于这样一个问题，从四块陆地的任一块出发，怎样才能做到经过每座桥一次且仅一次，然后回到出发点。问题看来并不复杂，但当地的居民和游人做了不少的尝试，却都没有取得成功。

Euler将四块陆地表示成四个结点，凡陆地间有桥相连的，便在两点间连一条边。ABCDDCAB

此时，哥尼斯堡七桥问题归结为：从A,B,C,D任一点出发，通过每条边一次且仅一次而返回出发点的回通路是否存在？

欧拉断言这样的回通路是不存在的。

理由是：从图中的任一点出发，为了要回到原来的出发点，要求与每个点相关联的边数均为偶数。这样才能保证从一条边进入某点后，再从另一条边出去，从一个点的不同的两条边一进一出才能回到出发点。而图中的A,B,C,D全是与奇数条边相连，由此可知所要求的回通路是不可能存在的。8.1图的基本概念8.1.1无向图和有向图8.1.2度的概念8.1.3握手定理8.1.4图的分类8.1.5子图与补图8.1.6

图的同构44无向图和有向图定义一个无向图可以表示为G=（V，E），其中V是非空有限结点集，称V中的元素为结点或顶点；E是边集，其中的元素是由V中的元素组成的无序对，称E中的元素为边。若（v，w）是无序对，则（v，w）=（w，v）。例如,G=<V,E>如图所示,其中V={v1,v2,…,v5}E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}45e1e2e3e4e5e6e7v5v1v2v3v4有向图定义

一个有向图可以表示为D=（V，E），其中V是非空有限结点集，称V中的元素为结点或顶点；E是有向边集，E中的元素是由V中的元素组成的有序对，称E中的元素为有向边。有向图D=（V，E）。结点集V={v1，v2，v3，v4}，有向边集E={<v1，v1>，<v1，v2>，<v1，v2>，<v1，v3>，<v2，v3>，<v3，v4>，<v4，v3>}。在有向图中，<b，a>

<a，b>46图的术语定义

在无向图中，如果关联一对结点的边多于一条，则称这些边为平行边。如果有边关联于一对结点，则称这对结点是邻接的。一条边的两个端点如果关联于同一个结点，则称为环，和任何边都不关联的点称为孤立点。边e2和e3是平行边，边e1关联结点v1和v3，则称v1和v3是邻接的，边e5=（v3，v3）是环，v4是孤立点。图的术语在有向图中，如果关联一对结点的方向相同的有向边多于一条，则称这些有向边为多重有向边或平行边。如关联于结点v1和v2的两条有向边是平行边，而关联于结点v3和v4的两条有向边方向相反，不是平行边。（v1，v1）称为环。对于有向边（v2，v3），称v2为起点，v3为终点，v2和v3是邻接的。图的术语n阶图:n个顶点的图零图:E=

的图平凡图:1阶零图在图的定义中规定结点集合V为非空集，但在运算中可能产生结点集为空集的运算结果，因此规定结点集为空集的图为空图，记为

度的概念

定义

设G=<V,E>为无向图,v

V,v所关联的边数称为v的度数，简称度，记作d(v)。悬挂顶点:度数为1的顶点悬挂边:与悬挂顶点关联的边G的最大度(G)=max{d(v)|v

V}G的最小度(G)=min{d(v)|v

V}例如d(v5)=3,d(v2)=4,d(v1)=4,

(G)=4,

(G)=1,v4是悬挂顶点,e7是悬挂边,e1是环50e1e2e3e4e5e6e7v5v1v2v3v4顶点的度数(续)定义

设D=<V,E>为有向图,v

V,以v为起点所关联的边数称为v的出度，记作d+(v)；以v为终点所关联的边数称为v的入度，记作d

(v)。v的总度数(度)d(v)是v的出度和入度之和：

d(v)=d+(v)+d-(v)

+(D),

+(D),

(D),

(D),

(D),

(D)悬挂顶点,悬挂边例如d+(a)=4,d-(a)=1,d(a)=5,d+(b)=0,d-(b)=3,d(b)=3,

+=4,

+=0,

=3,

=1,

=5,

=351e1e2e3e4e5e6e7dabc握手定理定理

设图G=(V,E)为无向图或有向图，G有n个结点v1,v2,…,vn，e条边(无向或有向),则图G中所有结点的度数之和为边数的两倍，即证图中每条边(包括环)均有两个端点,所以在计算各顶点度数之和时,每条边均提供2度,m条边共提供2m度.推论任何图(无向图和有向图)中，度数为奇数的结点的个数为偶数。52定理7.1.2定理

在有向图中，所有结点的入度之和与所有结点的出度之和相等，都等于图中的有向边数。证在有向图中，每条有向边均有一个起点和一个终点。于是在计算图中各结点的出度之和与各结点的入度之和时，每条有向边各提供一个出度和一个入度。当然e条有向边共提供e个出度和e个入度。因此所有结点的入度之和与所有结点的出度之和相等，都等于图中的有向边数e。图的度数列设V={v1,v2,…,vn}为图G的结点集，称(d(v1),d(v2),…,d(vn))为G的度数序列。一个由非负整数构成的序列d=（d1,d2,…,dn）,如d恰好是一个图的所有结点度数序列，称这个整数序列是可图化的，根据握手定理，此序列的各个数之和必为偶数。图的度数列设无向图G的顶点集V={v1，v2，……，vn}G的度数列:d(v1),d(v2),…,d(vn)如右图度数列:4,4,2,1,3设有向图D的顶点集V={v1，v2，……，vn}D的度数列d(v1),d(v2),…,d(vn)D的出度列:d+(v1),d+(v2),…,d+(vn)D的入度列:d

(v1),d

(v2),…,d

(vn)如右图度数列:5,3,3,3出度列:4,0,2,1入度列:1,3,1,255e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc例题例

自然数序列(3，3，2，2，1)，(4，2，2，1，1)能作为图的结点的度数序列吗？为什么？

解

在(3，3，2，2，1)中各个数之和为奇数，由握手定理可知，(3，3，2，2，1)不能作为图的结点的度数序列。(4，2，2，1，1)能作为图的结点的度数序列，下图中的两个图都是以（4,2,2,1,1）为结点度数序列。实例57例2已知图G有10条边,4个3度顶点,其余顶点的度数均小于等于2,问G至少有多少个顶点?解设G有n个顶点.由握手定理,43+2(n-4)210解得n8例3已知5阶有向图的度数列和出度列分别为3,3,2,3,3和1,2,1,2,1,求它的入度列解2,1,1,1,2实例例4证明不存在具有奇数个面且每个面都具有奇数条棱的多面体.58证用反证法.假设存在这样的多面体,作无向图G=<V,E>,其中V={v|v为多面体的面},

E={(u,v)|u,v

V

u与v有公共的棱u

v}.根据假设,|V|为奇数且v

V,d(v)为奇数.这与握手定理的推论矛盾.

图的分类定义

设图G=（V，E）为无向图或有向图，如果G中不含平行边，也不含环，则称为简单图。定义

设图G=（V，E）为无向图或有向图，如果G中含有平行边，则称为多重图。简单图多重图多重图简单图图的应用1、航班路线图有向多重图2、微博关注图有向简单图3、合作关系图无向简单图或多重图完全图(1)定义

设G=（V，E）是n阶无向简单图，若G中任何结点都与其余的n-1个结点相邻，则称G为n阶无向完全图，记作Kn。

完全图顶点数n,边数m=n(n-1)/2,(G)=(G)=n-1K3K5完全图(2)设G=（V，E）为n阶有向简单图，若对于V中任意的两个结点u和v，既有有向边(u，v)，又有有向边(v，u)，则称G是n阶有向完全图。

顶点数n,边数m=n(n-1),

+(D)=

+(D)=

-(D)=

-(D)=n-1,

(D)=

(D)=2(n-1)无特别说明时，完全图均指无向完全图。定理

例题例5判断下列各非负整数列是否是简单图的结点度数序列？（1）（5,5,4,4,2,1）（2）（5,4,3,2,2）（3）（3,3,2,2,1,1）（4）（4，4，3，2，1）（5）

解

（1）根据握手定理的推论可知，不是图的结点度数序列，因为有3个奇数。

（2）中有5个数，最大数是5，根据定理7.1.3，它不是简单图的结点序列。

（3）是简单图的结点序列。下图的两个无向简单图都是（3,3,2,2,1,1）为结点度数序列。

例题（续）（4）不是简单图的度数序列。根据定理8.1.4，把序列(4,4,3,2,1)的最大元素4删去，剩下4个元素都减1，得到序列（3，2，1，0），此序列不可简单图化，因此以(4,4,3,2,1)为结点度数序列的图不是简单图的度数序列。（5）中的最大值d1>=n,根据定理8.1.3，不是简单图的结点序列。正则图定义

设G为n阶无向简单图，若

v

V（G），均有d(v)=k,则称G为k-正则图。

K52正则图4正则图

3正则图彼得松图正则图根据握手定理，n阶k-正则图的边数

。当k为奇数时，n为偶数。当k=0时，0-正则图就是n阶零图。n阶无向完全图是(n-1)-正则图。环图和轮图定义

如果图G=（V，E）的结点集V={v1，v2，

vn}（n

3），边集E={（v1，v2），（v2，v3），

（vn-1，vn），（vn，v1）}，则称G为环图，记为Cn。下图是C3,C4,C5,C6。定义

当给环图Cn-1（n

4）添加一个结点，并把这个结点和Cn-1里的每个结点逐个连接后得到的图成为轮图，记作Wn。下图是轮图W4，W5，W6，W7。方体图定义

如果图G=（V，E）有2n个结点，每个结点表示一个长度为n的位串，任何两个相邻的结点表示的位串只有一位不同，则称G称为n方体图，记作Qn。690110110001010101100000111011001Q1Q2Q3方体图对任意n

N

，Qn

是将两个Qn-1

图的对应结点连接起来的简单图.Q0

有1个结点.Q0Q1Q2Q3Q4结点数:2n.边数：n2n-1二分图定义

如果图G=（V，E）的结点集V能划分为两个子集：V1和V2，使每条边有一个端点在V1中,另一个端点在V2中，则称该图为二分图（或二部图）。定义

二分图G=（V，E）的结点集V能划分为两个子集：V1和V2，若V1中的每个结点和V2中的每个结点均有边相连，则称G为完全二分图。若|V1|=m，|V2|=n,则可记为Km,n。下图所示的是K2,3和K3,3。

带权图定义7.1.17每个结点或每条边都带有数值的图称为带权图。

边带权图结点带权图可以用有序三元组或有序四元组表示带权图。如G=(V,E,f)，G=(V,E,g)或G=(V,E,f,g)，其中V是结点集，E是边集，f是结点所带的权的集合，g是边所带的权的集合。346218.1.5子图与补图定义

设图G=（V，E）设e

E，从G图中删去边e得到的图表示为G-e,称为删除边运算；设E1

E，从G图中删去E1的所有边得到的图表示为G-E1,称为删除边集运算。设v

V，从G图中删去结点v及v关联的所有边得到的图表示为G−v,称为删除结点运算；设V1

V，从G图中删去V1中所有结点及它们关联的所有边得到的图表示为G−V1,称为删除结点集运算。设e=(u,v)

E，从G图中删去边e,将e的两个端点u、v用一个新的结点w代替，将u,v关联的所有边都关联结点w，称为边e的收缩，记为G\e。设u,v

V，在u,v之间加一条边（u,v），称为加新边，表示为G

(u,v)(或G+(u,v))。例题在下图中，(1)为图G，(2)为G-e1,(3)为G-{e1,e4}，(4)为G-v3,(5)为G-{v1,v3},(6)为G\e1。子图定义

设G=（V，E）和G1=(V1，E1)是两个图。若V1

V，且E1

E，则称G1是G的子图，G是G1的母图，记作G1

G。若G1

G且G1

G(即V1

V,或E1

E)，则称G1是G的真子图。若G1

G且V1=V，则称G1是G的生成子图。对图G=（V，E），设V1

V且V1

，以V1为结点集，以两端点均在V1中的全体边为边集的G的子图，称G1为G的由结点集V1导出的子图，记为G（V1）。对图G=（V，E），设E1

E且E1

，以E1为边集，以E1中边关联的结点的全体为结点集的G的子图，称G1为G的由边集E1导出的子图，记为G（E1）。例题(1),(2),(3)是(1)的子图,(2),(3)是真子图,(1)是母图.(1),(3)是(1)的生成子图.(2)是{d,e,f}的导出子图,也是{e5,e6,e7}导出子图.(3)是{e1,

e3,

e5,e7}的导出子图76aabbccdddeeefffe1e1e2e3e3e4e5e5e5e6e6e7e7e7(1)(2)(3)若V1

V，且E1

E，则称G1是G的子图，G是G1的母图，记作G1

G。若G1

G且G1

G(即V1

V,或E1

E)，则称G1是G的真子图。若G1

G且V1=V，则称G1是G的生成子图。对图G=（V，E），设V1

V且V1

，以V1为结点集，以两端点均在V1中的全体边为边集的G的子图，称G1为G的由结点集V1导出的子图，记为G（V1）。对图G=（V，E），设E1

E且E1

，以E1为边集，以E1中边关联的结点的全体为结点集的G的子图，称G1为G的由边集E1导出的子图，记为G（E1）。补图定义

设G=(V，E)是n阶无向简单图或有向简单图。以V为结点，以所有能使G成为完全图需添加的边组成的集合为边集的图，称为G相对于完全图的补图，简称G的补图，记作~G。

补图定义

设G=(V，E)是n阶无向简单图或有向简单图。以V为结点，以所有能使G成为完全图需添加的边组成的集合为边集的图，称为G相对于完全图的补图，简称G的补图，记作~G。

补图定义

设G=(V，E)是n阶无向简单图或有向简单图。以V为结点，以所有能使G成为完全图需添加的边组成的集合为边集的图，称为G相对于完全图的补图，简称G的补图，记作~G。

G1~G1

G2~G2例题证明：在任意6个人的集会上，总会有3个人以前互相认识或有3个人以前互相不认识（假设认识是相互的）。即证明6个结点的无向图G或其补图~G中至少有一个完全子图K3。证明：考虑完全图K6,结点v1与其余5个结点各有一条边相连，这5条边一定有3条边在G或~G中。假设有3条边在G图中，这3条边为（v1,v2）、（v1,v3）、（v1,v4）。对于结点v2、v3、v4，若在G中v2、v3、v4间无边连接，则v2、v3、v4相互不认识，如果至少存在一条边，如v2、v3间存在一条边，则在v1、v2、v3三个结点都有边连接，构成一个K3子图，即有三个人相互认识。因此，总会有三个人相互认识或不认识。8.1.6图的同构定义

设两个图G=（V，E）和G'=（V'，E'），如果从V到V'存在双射函数f，使得对于任意的u，v

V，(u，v)

E,当且仅当(f(u)，f(v))

E'；如果在u，v间存在平行边，则关联于结点u，v的平行边数与关联于结点f(u)，f(v)的平行边数相同，则称G与G'是同构的，记作G

G'。a

v1，b

v5，c

v3，d

v2，e

v4判断两个图同构的必要条件1)必须具有相同的顶点数；2)必须具有相同的边数；3)度数相同的结点数相等。（对应顶点的度数相同.）4)相同长度的回路数相同。

判断两个图同构的必要条件不同构的图例题例6画出4阶3条边的所有非同构的无向简单图解总度数为6,分配给4个顶点,最大度为3,且奇度顶点数为偶数,有下述3个度数列:(1)1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.841,1,1,31,1,2,20,2,2,2例题例7画出3个以1,1,1,2,2,3为度数列的非同构的无向简单图85自互补图定义

如果一个图同构于它的补图,则称此图为自互补图。例8

试证明：一个图为自互补图，其对应的完全图的边数必为偶数。证明

设G为自互补图，G有e条边，并设G对应的完全图的边数为m，则G的补图的边数为m−e。对于自互补图G，有G

~G，所以e=m−e，m=2e

是偶数。

8.2通路与回路、连通的概念8.2.1通路与回路8.2.2连通的概念87定义7.2.1给定图G=（V，E）中，以v0为起点，vn为终点的由结点和边交替出现的序列v0e1v1e2v2…vn-1envn称为从结点v0到vn的长度为n的通路。G是无向图时，其中的边ei的端点是vi-1和vi（i=1，2，

n）；G是有向图时，其中的有向边ei的起点是vi-1，终点是vi（i=1，2，

n）。

887.2.1通路与回路通路与回路若一条通路的起点和终点是同一点，称它是一条回路。若通路中的所有边互不相同，则称它为简单通路或迹。若回路中的所有边互不相同，则称它为简单回路或闭迹。若通路中的所有结点互不相同，所有边互不相同，则称它为基本通路或初级通路、路径。若回路中的所有结点互不相同，所有边互不相同，则称它为基本回路或初级回路、圈。一条通路或回路包含的边的数目称为通路或回路的长度。如果一条回路的长度为奇(偶)数，则称为奇(偶)回路。例题v1e1v2e9v6e9v2e8v6e7v5是从结点v1到v5的长度为5的通路，v2e4v4e5v5e6

v2e1v1e10v6是简单通路，v2e4v4e5v5e6

v2e1v1e10v6e9v2是简单回路，v3e3v4e5v5e6v2e1v1e10v6是基本通路，v2e1v1e10v6e7v5e6

v2

是基本回路或圈。例题v1e2v2e5v4e4v3是从结点v1到v3的长度为3的通路，v1e2v2e5v4e6v2是简单通路，v1e2v2e5v4e4v3

是基本通路。在有向图中要注意边的方向，通路上一条边的终点是这条通路下一条边的起点说明(1)表示方法①按定义用顶点和边的交替序列,

=v0e1v1e2…elvl②用边序列,

=e1e2…el③简单图中,用顶点序列,

=v0v1…vl(2)在无向图中,长度为1的圈由环构成.长度为2的圈由两条平行边构成.在无向简单图中,所有圈的长度

3.在有向图中,长度为1的圈由环构成.在有向简单图中,所有圈的长度

2.92说明(续)(3)初级通路(回路)是简单通路(回路),但反之不真93初级通路非初级的简单通路初级回路非初级的简单回路定理定理

在n阶图G中，若从结点u到v（u

v）存在通路，则从u到v存在长度小于或等于n-1的通路。证明

设ue1v1e2v2…ekv为G中从u到v的长度为k的通路，通路上有k+1个结点。若通路长度k

n-1，则定理成立。若k>n-1，该通路上的结点数大于G的结点数n，根据鸽巢原理，必有一个结点在通路上出现两次，即存在t，s，0

t

s

k，使得vs=vt，因此通路上存在回路。删去回路，至少要删去一条边，得通路ue1v1e2v2…vtes+1…ekv仍是从u到v的通路，长度至少减小1。重复上述过程，经过有限步后，一定得到从u到v的长度小于或等于n−1的通路。推论推论

在n阶图G中，若从结点u到v（u

v）存在通路，则从u到v存在长度小于或等于n−1的基本通路。证明：若通路中没有相同的顶点(即基本通路),长度必

n

1.若有相同的顶点,删去这两个顶点之间的这一段,仍是u到v的通路.重复进行,直到没有相同的顶点为止.定理定理

在n阶图G中，若从结点u到自身存在回路，则回路的长度小于或等于n。推论

在n阶图G中，若从结点u到自身存在回路，则一定存在从结点u到自身的长度小于或等于n的基本回路。短程线与距离设u,v为图G中任意两个结点，u与v之间的短程线:u与v之间长度最短的通路(设u与v连通)u与v之间的距离d(u,v):u与v之间短程线的长度若u与v不连通,规定d(u,v)=∞.性质：(1)

d(u,v)

0,且d(u,v)=0

u=v(2)d(u,v)=d(v,u)(3)d(u,v)+d(v,w)

d(u,w)

97例如a与e之间的短程线:ace,afe.d(a,e)=2,d(a,h)=

abcdefghi通路的应用六度分割理论电影演员合作图中的贝肯数（bacon

number）论文合作关系图中的埃德斯数(Erdös

number)8.2.2连通的概念定义

若无向图G中任意两结点间都有一条通路(长度

1)，则称G是连通图；否则，称G是非连通图。连通关系R={<u,v>|u,v

V且u与v连通}.R是等价关系连通分支:V关于R的等价类的导出子图设V/R={V1,V2,…,Vk},G的连通分支为G[V1],G[V2],…,G[Vk]连通分支数W(G)=kG是连通图

W(G)=1

定理定理

设简单图G=（V，E）有n个结点，e条边，w个连通分支，则n-w

e。证明(用归纳法来证明)（1）当e=0时，也就是对于n个结点的零图，w=n，则n-w

e成立。（2）假定边数为e-1的简单图结论成立。对于边数为e的简单图G，从G中删去一条边，得到边数为e-1的简单图G'。分两种情况分析：(a)删去一条边的图G'的连通分支数没有增加，即G'有n个结点，w个分支，e-1条边，由归纳假设有n-w

e-1，所以n-w

e成立。(b)删去一条边的图G'的连通分支数增加，即G'有n个结点，w+1个分支，e-1条边，由归纳假设有n-(w+1)

e-1,所以n-w

e成立。点割集和边割集定义

设无向图G=(V,E),V

V,若W(G

V

)>W(G)且

V

V,W(G

V

)=W(G),则称V

为G的点割集.若{v}为点割集,则称v为割点.设E

E,若W(G

E

)>W(G)且

E

E,W(G

E

)=W(G),则称E

为G的边割集.若{e}为边割集,则称e为割边或桥.abcdefge1e2e3e4e5e6e7e8e9e,f点割集:{e},{f},割点:{c,d}

桥:e8,e9边割集:{e8},{e9},{e1,e2},{e1,e3,e6},{e1,e3,e4,e7}说明102Kn无点割集n阶零图既无点割集，也无边割集.若G连通，E

为边割集，则W(G

E

)=2若G连通，V

为点割集，则W(G

V

)

2例题例

试证明2n个城市，如果每个城市至少可以和另外n个城市可以相互直航，那么这2n个城市中任何两个之间可互相通航(有些可能要通过另外的城市中转)（即证明:2n个结点，每个结点的度数

n的简单图是连通的。）证明

设有2n个结点的图G不连通，则G中至少包含两个连通分支,而且必有一个分支的结点数

n，即使这个分支是完全图，其每个结点的度数d(v)

n-1，和d(v)

n矛盾。所以图G只有一个连通分支，G是连通的。有向图的连通性及其分类定义

设G=（V，E）是一个有向图，对G中任意两个结点u和v，若从u到v存在通路，则称由u到v是可达的，否则称由u到v是不可达的。若从u到v存在通路，且从v到u存在通路，则称u和v是相互可达的。规定一个结点到自己总是可达的。有向图的结点之间的可达关系具有自反性和传递性，不具有对称性。104有向连通图定义

设G=（V，E）是有向图。如果图G的任意两个结点间至少从一个结点到另一个结点是可达的，则称G是单向连通的。如果图G的任意两个结点间是互相可达的，则称G是强连通的。如果图G在略去有向边的方向后得到的无向图是连通的，则称G是弱连通的。具有三种连通性中的任何一种的有向图都称为有向连通图。实例106

强连通单连通弱连通顶点集上的互相可达关系对于u，v

V，u与v有关系，当且仅当从u可达v，并且从v可达u。顶点集上的互相可达关系是等价关系。利用互相可达关系可将顶点集V划分为V1，V2，…,Vw,每个Vi的任两个顶点都是互相可达的.所以每个Vi导出的子图Gi是强连通的,称为G的一个强分图.顶点集上的互相可达关系有向图的强连通分支.GG(V1)G(V2)G(V3)V1={v1,v7}V2={v2,v3,v5,v6}V3={v4}注意:有向图中不一定每条边都一定属于一个强连通分支.而无向图中每条边必属于一个连通分支.有向图中每个顶点必属于一个强连通分支.定理7.2.4：有向图G是强连通的当且仅当G中存在经过每个结点的回路。有向图的应用资源分配图是有向图：G=（V，E）,其中V是顶点的集合，E是边的集合。顶点集合分为两部分：（1）P={P1,P2,…Pn},它由进程集合的所有活动进程组成。（2）

R={r1,r2,…rm},它由进程集合所涉及的全部资源类型组成。边集合分为以下两种：（1）申请边(Pi，rj),表示进程Pi申请一个单位的rj资源，但当前Pi在等待该资源。（2）赋给边(rj，Pi),表示有一个单位的rj资源已分配给进程Pi。资源分配图（1）G1(2)G2图G1中有一个回路，所以是死锁状态。图G2也有一个回路：P1r1P3r2P1，然而没有出现死锁。因为进程P2和P4能释放占有的资源r1和r2,然后就可以将r1和r2分给P1和P3,这样环路就打开了。资源分配图中存在回路是死锁存在的必要条件，但不是充分条件。P1P3．．r2r1r1P1P2P3P4．．．．r28.3图的表示8.3.1邻接表8.3.2邻接矩阵8.3.3可达矩阵8.3.4关联矩阵111定义

列出图的每一个结点和它的所有邻接结点的表称为邻接表。例1

用邻接表表示无向简单图。例2

用邻接表表示有向简单图。1128.3.1邻接表无向简单图的邻接表结点邻接结点ab,cba,c,dca,b,d,edb,cec有向图的邻接表起点终点abbc,dca,b,d,edeb,c8.3.2邻接矩阵定义

设图G=（V，E）是有向图，V={v1，v2，

，vn}，G的邻接矩阵为，其中例题114A=1100001010001020v1v2v3v4有向图中的通路数与回路数定理

设A是有向图G=（V，E）的邻接矩阵，V={v1，v2，

，vn}，

，则

表示G中从vi到vj的长度为k的所有有向路的数目，其中

是从vi到自身的长度为k的所有回路的数目。证明

用归纳法证明，对k作归纳。当k=1时，由邻接矩阵的定义知结论成立。设k=m时，结论成立。当k=m+1时，有

，从而

。显然

等于从vi出发经vp到vj的长度为m+1的有向路的数目。由于p的任意性

等于G中从vi到vj的长度为m+1的所有有向路的数目。115有向图中的通路数与回路数(续)推论设矩阵

则Bl中的元素表示图G中从结点vi到vj的长度小于等于l的所有通路的总数。其中bii(l)是从vi到自身的长度小于等于l的所有回路的总数目。116实例(续)

117A=1100001010001020A2=1110100011003100A3=2110110011003310A4=3210110021104310v1到v2长为3的通路有1条v1到v3长为3的通路有1条v1到自身长为4的回路有3条D中长为3的通路共有15条,其中回路3条v1v2v3v4无向图的邻接矩阵定义

设图G=（V，E）是无向图，V={v1，v2，

，vn}，G的邻接矩阵为，其中例3

写出如下图所示的无向图G的邻接矩阵。解

邻接矩阵为例题例4

画出给定的邻接矩阵所表示的图。（1）（2）

（a）（b）abcabc(c)v1v2v4v3解

（1）邻接矩阵（1）所表示的图可以是无向图（a）或有向图（b）。

（2）邻接矩阵（2）所表示的图见图（c)。例题例5判定下面的邻接矩阵A所表示的图G是否强连通图？解因为B3中存在为0的元素，所以图G不是强连通图。v1v2v3例题例6

判断下面的两个图是否同构？解两个图的邻接矩阵为：

将矩阵A2的第2行元素和第3行元素交换，得到矩阵

，然后将矩阵

的第2列元素和第3列元素交换，得到矩阵

。

矩阵

和矩阵

相同，所以两个图同构。8.3.3可达矩阵定义

设图G=（V，E）是有向图，V={v1，v2，

，vn}，A是G的邻接矩阵，

G的可达矩阵为

，

i，j=1,2，…，n,其中例题

写出右图的可达矩阵。解

所以可达矩阵为由可达矩阵求强连通分支对可达矩阵P求转置PT，PT中的(i,j)的元素为

，定义一个矩阵P∧PT，使得它的(i,j)的元素为

，于是矩阵P∧PT的第i行的“1”对应的结点组成一个含有结点vi的强连通分支。矩阵P∧PT的第2行的两个“1”表明结点v2和v3是一个强连通分支。125则称(mij)n

m为G的关联矩阵,记为M(G).定义

设图G=(V,E)是无环的有向图,V={v1,v2,…,vn},E={e1,e2,…,em}.令8.3.4关联矩阵例题126ej与ek是平行边

第j列与第k列相同孤立点对应的行全为0(2)第i行1的个数等于d+(v),第i行-1的个数等于d-(v)性质:(1)每列恰好有一个1和一个-1定义

设图G=(V,E)是无向图，V={v1,v2,…,vn},E={e1,e2,…,em}.

令mij为vi与ej的关联次数,称(mij)n

m为G的关联矩阵,记为M(G).mij的可能取值为:0,1,2127例如e1e2e3e4e5e6v5v1v2v3v4M(G)=2110000101110000110000000011008.3.4关联矩阵同一个图当结点或边的边序不同时,其对应的A(G)有行序、列序的差别。性质128(6)ej是环

第j列的一个元素为2,其余为0(5)vi是孤立点

第i行全为0例题

画出下面的关联矩阵M(G)表示的图G。解

关联矩阵M(G)表示的图G如下图。例题判断下面两个关联矩阵表示的图是否同构？答案：是e1e2e3v1v2v3e1e2e3v3v1v2例题三枚钱币处于反、正、反面，每次只许翻动一枚钱币，问连续翻动三次后，能否出现全正面或全反面。例题（续）解

引入一个三元组(q0,q1,q2)来描述钱币的状态，钱币正面为0，反面为1，全部可能的状态为：Q0=(0,0,0)；Q1=(0,0,1)；Q2=(0,1,0)；Q3=(0,1,1)；Q4=(1,0,0)；Q5=(1,0,1)；Q6=(1,1,0)；Q7=(1,1,1)。三枚钱币的初始状态是Q5，目标状态是Q0和Q7。是否可以翻动3次后从Q5到Q0或Q7的问题转化为在下图中是否存在从结点Q5到Q0或Q7的长度为3的通路。例题（续）用邻接矩阵表示图

：例题（续）求A的3次幂从矩阵A3可知a61=0,a68=7,即Q5到Q0没有长度为3的通路，Q5到Q7有7条长度为3的通路。所以，连续翻动钱币三次，不能出现全正面，可以出现全反面，有7种翻动方法可以出现全反面。a:把钱币q0翻转一次

b:把钱币q1翻转一次

c:把钱币q2翻转一次aabababaabbbbcccbcccb

图的运算定义7.4.1设G1=（V1，E1）和G2=(V2，E2)是两个简单图，G1和G2的并图是以E1

E2为边集的图，以E1

E2中的边关联的结点的集合为结点集的图，可表示成G1

G2。G1和G2的交图是以E1

E2为边集，以E1

E2中的边关联的结点的集合为结点集的图，可表示成G1

G2。G1和G2的差图是以E1

E2为边集，以E1

E2中的边关联的结点的集合为结点集的图，可表示成G1

G2。G1和G2的环和图是以E1

E2为边集，以E1

E2中的边关联的结点的集合为结点集的图，可表示成G1

G2。

两个图的环和可以用并、交、差给出：G1

G2=(G1

G2)

(G1

G2)。定义

设G1=（V1，E1）和G2=(V2，E2)是两个图，若V1

V2=

，则称G1和G2是不交的；若E1

E2=

，则称G1和G2是边不交的，或边不重的。

当G1和G2是边不交时，G1

G2=

，G1

G2=

G1，G2

G1=

G2，G1

G2=(G1

G2)。8.4独立集、覆盖和支配集独立集定义：设G=（V，E）是无向图简单图，V的一个子集U中，任两个结点不相邻，则称U为G的一个点独立集，简称独立集。若图G的一个独立集，再加入任何结点都不是独立集，则称为极大独立集；结点数最多的独立集称为最大独立集；最大独立集的结点数称为图G的独立数，记为α(G)。例题{a,e}和{b,d,f}是独立集，也是极大独立集，{b,d,f}是最大独立集。可以看出，独立集是导出子图是零图（没有边）的结点集。空集是任意图的独立集。覆盖和覆盖集定义

设G=（V，E）是无孤立点的无向图简单图，V的一个子集S，图中每一条边至少有一个结点在S中，称S为G的一个点覆盖。若G的一个点覆盖中去掉任一个结点后不再是点覆盖，则称此点覆盖为G的一个极小点覆盖。结点数最少的点覆盖，称为G的最小点覆盖。最小点覆盖S的元素个数称作图G的点覆盖数，记作

(G)。例题{b,c,d,f,g}和{a,c,e,g}是极小点覆盖，{a,c,e,g}是最小点覆盖在任一简单图G=（V，E）中，V是点覆盖。定理定理：

设图G=（V，E）是无孤立点的无向简单图，S是G的点覆盖，当且仅当U=V-S是G的点独立集。证明：

当S是G的点覆盖，假设U中有两个结点u,v相邻,则有边(u,v)不被S所覆盖，和S是点覆盖矛盾，所以U中任两个结点u,v不相邻，U为点独立集。当U为点独立集，假设图G中存在边e不关联S中的结点,则边e的两端点都在U中，即U中有两个相邻结点，和U为点独立集矛盾，所以图G中任一边e关联S中的结点，S是G的点覆盖。例题{b,c,d,f,g}是点覆盖，{a,e}是点独立集。推论1推论1：设图G=（V，E）中无孤立点的无向简单图，S是G的极小点覆盖，当且仅当U=V-S是G的极大点独立集。证明：如果S是G的极小点覆盖，但U=V–S不是G的极大点独立集，则存在另一个点独立集U，UU，由定理7.4.1知V–U是点覆盖，而且S=V–UV–U，与S的极小性矛盾。类似地可以证明，如果U=V-S是G的极大点独立集，S是G的极小点覆盖。推论2设图G=（V，E）中无孤立点的简单图，S是G的最小点覆盖，当且仅当U=V-S是G的最大点独立集，因而有

(G)+

(G)=|V|。证明：如果S是G的最小点覆盖，而U=V–S不是G的最大点独立集，则存在另一个最大点独立集U

，U

U

，由定理8.4.1知V–U

是点覆盖，而且|V–U

|=|V|–|U

|<