离散数学第七章(25.26.27;28)

1、东南大学远程教育离离 散散 数数 学学第第 五十五五十五 讲讲主讲教师：仲新宇主讲教师：仲新宇第四篇图论图论是近年来发展迅速而又应用广泛的一门新兴学科。它最早起源于一些数学游戏的难题研究，如1736年欧拉（L.Euler)所解决的哥尼斯堡七桥问题。以及在民间广为流传的一些游戏问题：例如迷宫问题、棋盘上马的行走路线问题等等。这些古老的问题当时吸引了许多学者的注意，从而在这些问题研究的基础上，又提出了著名的四色猜想和环游世界各国的问题。 第四篇图论图论不断发展，它在解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，显示出越来越大的效果。对于这样一门应用广泛的学科，其包含

2、的内容是丰富的，本篇我们只准备介绍基本的概念和定理，为今后有关学科及课程的学习和研究提供方便。第四篇图论第七章第七章图论图论1图的基本概念2路与回路3图的矩阵表示4欧拉图和汉密尔顿图5平面图6树与生成树1图的基本概念1.1.基本名词和定义基本名词和定义定义定义一个图G是一个三元组, 其中V(G)为有限非空结点（或叫顶点）集合, E(G)是边的集合， G是从边集E到结点偶对集合上的函数。讨论定义： (1). V(G) =V1，V2，Vn为有限非空集合, Vi称为结点,简称V是点集。 (2). E(G)=e1，em为有限的边集合,ei称为边，每个ei都有V中的结点对与之相对应,称E为边集。 即每条

3、边是连结V中的某两个点的。1图的基本概念(3).若中每一条边e与有序偶对或无序偶对(vi,vj)相关系，则可说边e连接结点vi和vj(4).可用e 或e (vi,vj)，以结点来表示图的边，这样可把图简化成：。 例：有图如下，试写成定义表达式，其中v1,v2,v3,v4,v5 x1,x2,x3,x4,x5,x61图的基本概念例：对有向图可表示为：、，其中a、b、c、d, 下面定义一些专门名词：(1)有向边：有向边：在图中对应有序偶对的边（或者：在图中带有箭头方向的边或弧线） 1图的基本概念(2)无向边：无向边：在图中对应无序偶对的边（或：在图中不带箭头的边）(3)邻接结点：邻接结点：由一条边（

4、有向或无向） 连接起来的结点偶对 (4)（，）图：（，）图：具有个结点（顶点），条边的图(5)有向图：有向图：在中每一条边均为有向边(5)有向完全图：有向完全图：在n个结点的有向图G=中，如果 EVV，则称G为有向完全图。例：东南大学远程教育离离 散散 数数 学学第第 五十六五十六 讲讲主讲教师：仲新宇主讲教师：仲新宇1图的基本概念对有向简单完全图讲 ： n(n-1) （没有自回路） 22nC1图的基本概念(6)无向图：无向图：每一条边均为无向边的图(7)无向完全图：无向完全图：每两个结点之间均有连线的无向图。n个结点的无向完全图的边数为：例：2) 1(2nnCen1图的基本概念(8)混合图：

5、混合图：既有有向边，又有无向边的图(9)互相邻接的边：互相邻接的边： 连接于同一结点的二条（或若干条）边例：1图的基本概念(10)闭路（自回路）：闭路（自回路）：图中起始且终止于同一结点的边(闭路的箭头方向是没有意义的 )例：(11)多重边（平行边）：多重边（平行边）：二个结点之间方向相同的二条（多条）边例：1图的基本概念定义定义：含有多重边的图称为多重图多重图，非多重图称为线图线图。简单图：简单图：无自回路的线图称为简单图。简单图。由定义可见，简单图是没有自回路和多重边的图。例：1图的基本概念定义定义：有权图有权图（赋权图）是一个三元 组、或四元组、，其中为结点集合，为边的集合，f是定义在上

6、的函数，g是定义在边集合上的函数。实际上，有权图可以用一句话概括：每一条边或结点均注上数字的图（数字可以为整数、正实数）例：给出一个有权图、，其图如下：其中 v1,v2,v3 e1,e2 1图的基本概念(12)孤立结点：孤立结点：不与任何结点相连接的结点(13)零图：零图：仅包含孤立结点的图，又称（，）图(14)平凡图：平凡图：只有一个结点的图（1，0）图定义定义：在有向图中，对于任何结点v，以v为始点的边的条数，称为结点v的引出度数， 记作 ；以v点为终点的边的条数称为v的引入度数，记作 结点的v的引入度数和引出度数之和称为v的度数，用deg（v）表示。 由定义可见：度数deg（v）对无向图

7、讲：结点的度数等于和该结点关联的边的条数)(degv)(degv)(degv)(degv1图的基本概念例：(15)正则图：正则图：所有结点均具有同样度数的简单无向图例：1图的基本概念定理定理： 每个图中，结点度数的总和等于边数的两倍。niiev12)deg(1图的基本概念例：若图有n个顶点，（n+1）条边，则中至少有一个结点的度数。证明：设中有n个结点分别为v1,v2,vn，则由握手定理：而结点的平均度数=结点中至少有一个顶点的度数 ) 1(22)deg(1nevnii212) 1(2nnn1图的基本概念推论推论：(1)在图中，所有度数之和必为偶数；(2)在图中，度数为奇数的结点必定有偶数个。

8、1图的基本概念定理定理：在任何有向图中，所有结点的入度之和等于所有结点的出度之和。1图的基本概念子图和图的同构子图和图的同构：定义定义：设，是二个图若，,则称是的子图；若或,则称是的真子图；若，,则称是的生成子图(支撑子图)。例：图如下：的真子图： 支撑子图：1图的基本概念说明：（1）也是的生成子图；（2），也是的生成子图。它们统称为平凡子图。定义定义：设，是的子图，若有另一个图，且满足关系， 为E中边的相关结点的集合，即（ ），则称：为关于的补图（相对补图）。例：1图的基本概念 关于的补图定义定义：给定一个图，由中的所有结点和使成为完全图的边所组成的图，称为的补图（绝对补图），记为: G1图

9、的基本概念 定义定义：设、和，是两个图，若存在一双射函数：，当且仅当eg(vi),g(vj)是中的一条边，才能使evi,vj是中的一条边，则称和同构。 1图的基本概念讨论定义：（1）和是互为同构的；（2）对无向图讲“一一对应”是指保持结点之间的邻接关系；（3）对有向图讲“一一对应”不但是指结点之间的邻接关系，而且还应保持边的方向和边的重数。例1：1图的基本概念例：下面给出二个无向图，试求出同构函数：1,2,3,4,5,6 ,654321aaaaaa1图的基本概念两图同构的必要条件：1.结点数相等。2. 边数相等3.度数相同的结点数相等不是充分条件。东南大学远程教育离离 散散 数数 学学第第 五

10、十七讲五十七讲主讲教师：仲新宇主讲教师：仲新宇1图的基本概念子图和图的同构子图和图的同构：定义定义：设，是二个图若，,则称是的子图；若或,则称是的真子图；若，,则称是的生成子图(支撑子图)。例：图如下：的真子图： 支撑子图：1图的基本概念说明：（1）也是的生成子图；（2），也是的生成子图。它们统称为平凡子图。定义定义：设，是的子图，若有另一个图，且满足关系， 为E中边的相关结点的集合，即（ ），则称：为关于的补图（相对补图）。例：1图的基本概念 关于的补图定义定义：给定一个图，由中的所有结点和使成为完全图的边所组成的图，称为的补图（绝对补图），记为: G1图的基本概念 定义定义：设、和，是两个

11、图，若存在一双射函数：，当且仅当eg(vi),g(vj)是中的一条边，才能使evi,vj是中的一条边，则称和同构。 1图的基本概念讨论定义：（1）和是互为同构的；（2）对无向图讲“一一对应”是指保持结点之间的邻接关系；（3）对有向图讲“一一对应”不但是指结点之间的邻接关系，而且还应保持边的方向和边的重数。例1：1图的基本概念例：下面给出二个无向图，试求出同构函数：1,2,3,4,5,6 ,654321aaaaaa1图的基本概念两图同构的必要条件：1.结点数相等。2. 边数相等3.度数相同的结点数相等不是充分条件。2路与回路1.路径和循环路径和循环定义定义：在一个图中，从某一结点出发经过某些结点

12、到达终点的边的序列称为图的路径，而路径中边的条数称为路径的长度（路长）。讨论定义：（1）从一个结点到某一结点的路径，（若有的话）不一定是唯一的；（2）路径的表示方法： (a)边的序列表示法： 设，为一有向图， ，则路径可以表示成：(,.) Vvi2路与回路(b)结点表示法：（3）路径长度：若二个结点之间有一条路经，则路径|中边的条数。例：给出有向图，求起始于，终止于的路径 ),(21kvvv2路与回路下面介绍一些专有名词：(1)穿程全部结点的路径穿程全部结点的路径：经过图中所有结点的路径。(2)简单路径：简单路径：在有向图中经过边一次且仅一次的路径。(3)基本路径：基本路径：在有向图中，穿程结

13、点均不相同的路径。(4)循环：循环：起始且终结于同一结点的路径。 (5)简单循环：简单循环：每一条边出现一次且仅一次的循环。(6)基本循环：基本循环：通过每个结点一次且仅一次的循环。例：在上例中，列出下列循环，判断为何种循环2路与回路(7)非循环图：非循环图：没有任何循环的简单有向图。讨论：一定不包含自循环 不是基本路径的任何路径都会包含循环，而去掉这些循环就可以得到基本路径 2.可达性：可达性：定义定义：设图为简单有向图，且 ，若从vi到vj存在任何一条路径的话，则称vi到vj是可达的。可达性一定满足： 自反性： 可传递性： Vvvji,东南大学远程教育离离 散散 数数 学学第第 五十八讲五

14、十八讲主讲教师：仲新宇主讲教师：仲新宇1图的基本概念讨论定义：（1）和是互为同构的；（2）对无向图讲“一一对应”是指保持结点之间的邻接关系；（3）对有向图讲“一一对应”不但是指结点之间的邻接关系，而且还应保持边的方向和边的重数。例1：2路与回路定义定义：从vi到vj的最短路径的长度称为距离，并记作： 讨论定义：(1) d=0(2) d0(3) d+ddjivvd,2路与回路(4)规定：若vi到vj是不可达的，则(5)若vi到vj是可达的，且vj 到vi也是可达的，则d不一定等于d 例：jivvd,2路与回路3.连通性连通性 定义定义：对于无向图中的任何结点偶对来讲，若任何二个结点是相互可达的，

15、则称此图是连通的。 对于有向图来讲 定义定义：对于简单有向图的伴随无向图（或称底图），若是连通的，则称此图为弱连通的；若图中任何结点偶对中至少有一点到另一结点是可达的，则称此图是单侧连通的；如果两结点均是互相可达的，则称是强连通的。注：伴随无向图即为去掉箭头方向的图 2路与回路例：判定下列图是何种连通图：2路与回路定理定理：一个有向图是强连通的充要条件是：它包含一个循环，该循环至少包含每个结点一次。证明：2路与回路定义定义：设，为一简单有向图，且是的子图。对于某一性质而言，若没有其他包含的子图具有这种性质，则称子图是相对于该性质的极大子图。具有强连通性质的极大子图称为强分图；具有单侧连通性质的

16、极大子图称为单侧分图；具有弱连通性质的极大子图称为弱分图。2路与回路例： 2路与回路定理定理：在任一简单有向图，中，有向图的每一个结点恰好处于一个强分图之中。证明： 3图的矩阵表示矩阵是研究图的有关性质的最有效的工具，可运用图的矩阵运算求出图的路径、循环和其它一些性质。图的邻接矩阵表示方法图的邻接矩阵表示方法 定义：设，是简单有向图，其中 V=v1,v2,vn定义一个nxn的矩阵A，并把其中各元素aij表示成： EvvEvvajijiij若若,0,1则称矩阵A为图G的邻接矩阵。3图的矩阵表示例：设图，如下图所示 讨论定义：（1）图G的邻接矩阵中的元素为0和1，又称为布尔矩阵；（2）图G的邻接矩

17、阵中的元素的次序是无关紧要的，只要进行行和行、列和列的交换，则可得到相同的矩阵。3图的矩阵表示若有二个简单有向图，则可得到二个对应的邻接矩阵，若对某一矩阵进行行和行、列和列之间的交换后得到和另一矩阵相同的矩阵，则此二图同构。（3）当有向图中的有向边表示关系时，邻接矩阵就是关系矩阵；（4）零图的邻接矩阵称为零矩阵，即矩阵中的所有元素均为0；（5）在图的邻接矩阵中， 行中1的个数就是行中相应结点的引出次数 列中1的个数就是列中相应结点的引入次数东南大学远程教育离离 散散 数数 学学第第 五十九讲五十九讲主讲教师：仲新宇主讲教师：仲新宇3图的矩阵表示矩阵的计算矩阵的计算：ATA3图的矩阵表示主对角线

18、上的数表示结点i（或j）的引出次数。 TAAAAT主对角线上的数表示结点i（或j）的引入次数。 3图的矩阵表示AAA2AAA23AAA342A3A4A表示i和j之间具有长度为2的路径数， 表示i和j之间具有长度为3的路径数， 表示i和j之间具有长度为4的路径数，3图的矩阵表示bij表示从结点vi到vj有长度分别为1，2，3，4的不同路径总数。此时， bij0，表示从vi到vj是可达的。43214AAAAB3图的矩阵表示定义：设，是简单有向图， 其中|V|=（ ），定义一个 矩阵P，它的元素为：则P称为图G的可达性矩阵。 由 矩阵可计算出可达性矩阵，其方法是：若 中（i ,j）是非“0”元素，则

19、对应的 ，否则 。Innn不存在任何路径到若至少存在一条路径到若jijiijvvvvp01nBnB1ijP0ijP3图的矩阵表示定义定义：设无向图， 其中 ，则称B为无向图G的 完全关联矩阵。 32127747554634234324AAAABP,2121mneeeEvvvVmnijbB)(令jijiijevevb不关联若关联若013图的矩阵表示例：讨论定义：（1）完全关联矩阵为布尔矩阵；（2）对应B中行均为0的结点为孤立结点，只有一个“1”的行的结点一定为悬挂的边，且一定不在任一循环中全部为1的行的结点必定联结图中所有的结点。 4欧拉图和汉密尔顿图欧拉路径：穿程图G的每一条边一次且仅一次的路

20、径。欧拉循环：穿程图G的每一条边一次且仅一次的循环。欧拉图：具有欧拉循环的图。定理：无向图G具有一条欧拉路径，当且仅当G是连通的，且有零个或两个奇数度数的结点。推论：无向图G具有一条欧拉循环，当且仅当G是连通的，且所有结点度数全为偶数。4欧拉图和汉密尔顿图例：用定理解决哥尼斯堡桥的问题 4欧拉图和汉密尔顿图定理：设G是一连通有向图，则当且仅当G中每一个结点的 ，G才有欧拉循环；当且仅当除了二个结点（其中一个的引入次数比引出次数大，另一个的引入次数比引出次数小）以外的所有结点的 ，则图G才有欧拉路径。)(degv)(degv)(deg v)(degv4欧拉图和汉密尔顿图汉密尔顿路径：穿程无向图的

21、每一个结点一次且仅一次的路径。汉密尔顿循环：穿程无向图的每一个结点一次且仅一次的循环。汉密尔顿图：具有汉密尔顿循环的图。到目前为止，还没有找到哈密尔顿路径存在的充分必要条件。下面介绍两个定理。4欧拉图和汉密尔顿图定理定理：设，是具有n 个结点的简单无向图，若在G中每对结点次数之和大于或等于(n-1)，则在G中一定存在一条汉密尔顿路径。实际上，此定理只是充分条件，而不是充分必要条件。例：，见图：每对结点次数为，但确有一条汉密尔顿路径。4欧拉图和汉密尔顿图定理定理：若图G=具有汉密尔顿循环，则对于结点集V的每个非空子集S均有W(GS)|S|成立。讨论：(1)W(GS)为从G中删除S后，所得图的连通

22、分支数。(2)该定理给出的条件是哈密尔顿图的必要条件。例：东南大学远程教育离离 散散 数数 学学第第 六十六十 讲讲主讲教师：仲新宇主讲教师：仲新宇5平面图先看一个例子：有六个结点的图如右，试问：能否转变成与其等价的，但没有任何交线的平面上的图？定义定义：设G=是一个无向图，如果能够把G的所有结点和边画在平面上，且使得任何两条边除了端点外没有其它的交点，就称G是一个平面图。5平面图讨论定义：（1）平面上的图，一开始就画成如定义所讲的图；例：（2）原来在平面上的图形似交叉，但经过若干次的改画后，变成符合定义所规定的图；5平面图（3）并非所有的图经过处理之后都可变为平面图。如何判断一个图是否为平面

23、图，介绍以下几种方法：1.观察法：找出基本循环，将交叉的边分别放置在基本循环内或外而避免交叉。5平面图2欧拉定理：定义定义：平面图中四周为边所包围之最小平面块称为平面图的区域亦称面。包围区域的诸边称为此区域的边界。区域面积为有限者称为有限区域，区域面积为无限者称为无限区域。例：5平面图定理定理：(欧拉公式)设图G是一个(n,m)连通平面图，它的区域数为r，则有nmr2。推论推论：设图G是一个(n,m)连通简单平面图，若n3则m3n-6。定理和推论给出了是平面图的必要条件，若不满足这些条件，则一定不是平面图。例：5平面图3库拉托夫斯基（Kuratowski 波兰数学家）定理：给定两个图：我们做以

24、下的工作：(1)在左边图的中间联线上插入一个度数为2的结点，则把一条边分成了二条边；(2)在右边图中去掉一个度数为2的结点，则把二条边变成一条边。此二项工作不会影响图的平面性。2度结点内同构度结点内同构。5平面图定义定义：设G1、G2是二个图，如果它们是同构的，或可以通过反复插入或删除度数为2的结点，使得G1和G2同构，则称G1 、 G2为2度结点内同构。例：下列二对图是度数为2的结点同构5平面图定理定理：（Kuratowski定理）设G是一个图，当且仅当G不包含任何在度数为2的结点内与K3,3和K5图同构的子图时，则G才是平面图。这一定理给出了一个图是平面图的充要条件。6树与生成树1.无向树

25、（树）无向树（树）定义定义：连通的且无循环的无向图称为无向树。例：专用名词：树叶(终点)：树中度数为1的结点。内点(分枝点)：树中度数大于1的结点。森林：每个连通分图均为树的图。6树与生成树树的性质：定理定理1：设T是一棵树，vi,vj为T中两个不同的结点，则：1) vi和vj仅有一条路径相连通。 2)在T中加一条边vi,vj，则由此而形成的图，仅有一个循环。 例：东南大学远程教育离离 散散 数数 学学第第 六十六十 一讲一讲主讲教师：仲新宇主讲教师：仲新宇6树与生成树定理定理2：在一棵(n,e)树中有e=n-1。(n表示结点数， e表示边数)证明：6树与生成树推论推论：设F是由t棵树组成的(

26、n,e)森林，则有e=n-t。定理定理3：在结点大于2的(n,e)树中，所有结点的度数之和为2(n-1)。定理定理4：在任一(n2)的树T中，至少有二片树叶。6树与生成树2.生成树生成树定义定义：一个无向图G的生成子图是树TG，则称TG是G的生成树(支撑树)。讨论定义：1)G的生成树不是唯一的。例：6树与生成树2)如何在连通图G中寻找一棵生成树：若G没有循环，则G本身就是一棵树；若G仅有一条循环，从此循环中删去一条边，仍保持图的连通性，得到一棵生成树。若G有多条循环，则逐个对每条循环重复中操作，直到打断G中所有循环，得到一棵生成树为止。定理定理：任何连通图至少有一棵生成树。6树与生成树给定一个

27、连通图，寻找其生成树的数目是图论中树的计数问题。定理定理：含n(n1)个结点的标记完全图Kn有nn-2棵标记生成树。例：6树与生成树定义定义：生成树T中的边称为树枝，不在生成树T中但属于图G的边，称为树T的弦，弦的集合称为树T的补。例： 定义定义：在一个连通赋权图中，树枝的权之和为最小的生成树称为最小生成树。Kruskal算法：设G有n个结点，m条边，先将G中所有边按权的大小次序进行排列，不妨设：W(e1)W(e2)W(em)，k1，A。6树与生成树若Aek导出的子图中不包含简单循环，则 A Aek若A中已有n-1条边，则算法终止，否则K K+1，转至。例：6树与生成树这一算法假设G中权均不相同，对于边权任意情况也完全适用。这时求得的最小生成树不唯一。例：东南大学远程教育离离 散散 数数 学学第第 六十二六十二 讲讲主讲教师：仲新宇主讲教师：仲新宇7有向树与根树定义定义：若有向图在不考虑边的方向时是一棵树，称之为有向树。定义定义：一棵有向树，如果恰有一个结点的入度为0，其余所有结点的入度都为1，则称为根树。入度为0的结点称为根，出度为0