离散数学课件(第7章)

《离散数学课件(第7章)》由会员分享，可在线阅读，更多相关《离散数学课件(第7章)（141页珍藏版）》请在金锄头文库上搜索。

1、离散数学教案计算机科学与技术学院课程学时：64主 讲：宋 成河南理工大学电子教案图论是最近几年发展迅速而又应用广泛的 一门新兴科学。图论是一个重要的数学分支。它 最早起源一些数学游戏的难题研究，数学家欧拉 1736年发表了关于图论的第一篇论文，解决了 著名的哥尼斯堡七桥问题。克希霍夫对电路网络 的研究、凯来在有机化学的计算中都应用了树和 生成树的概念。以及在民间广为流传的一些游戏 问题：例如迷宫问题、棋盘上马的行走路线问题 等等。这些古老的问题当时吸引了许多学者的注 意，从而在这些问题研究的基础上，又提出了著 名的四色猜想和环游世界各国的问题第四篇：图论第四篇篇：图论图论的不断发展，他在解决运

2、筹学、网络理 论、信息论、控制论、博弈论以及计算机科学 等各个领域的问题时，显示出越来越大的效果对于这样一门应用广泛的学科，其包含的内 容是丰富的，本篇首先给出图、简单图、完全 图、子图、路和图的同构等概念，接着研究了 连通图性质和规律，给出了邻接矩阵、可达性 矩阵、连通矩阵和完全关联矩阵的定义。最后 介绍了欧拉图与哈密尔顿图、平面图、对偶图 与着色、树与生成树。为今后有关学科及课程 的学习和研究提供方便第七章：图论7.1 图的基本概念 7.2 路与回路 7.3 图的矩阵表示 7.4 欧拉图与哈密尔顿图 7.5 平面图 7.6 对偶图和着色 7.7 树与生成树第七章：图论教学目的及要求：深刻理

3、解和掌握图的有关概念和表示 教学类容：图的基本概念、路与回路、图的矩阵表示、欧拉 图与汉密尔顿图、平面图、对偶图与着色、树与 生成树。 教学重点：图、路、图的矩阵表示、平面图、对偶图与着色 、树与生成树 教学难点：树与生成树。第七章：图论7.1 图的基本概念7.1.1图 两个个体x，y的无序序列称为无序对，记为 (x,y)。在无序对(x,y)中，x，y是无序的，它们的 顺序可以颠倒，即(x,y)=(y,x)。 【定义7.1.1】 图G是一个三重组V(G),E(G),G其中：V(G)是非空结点集。E(G)是边集。G是边集到结点的有序对或无序对集合的函数。第七章：图论【例7.1】G=V(G),E(

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

5、.1.3】 设G为图，如果G的所有边都是有向边，则 称G为有向图。如果G的所有边都是无向边，则称G为无向 图。如果G中既有有向边，又有无向边，则称G为混合图。图7.2的(a)是无向图，(b)是有向图，(c)是混合图。 第七章：图论在一个图中，若两个结点由一条边(有向边或无向边) 关联，则称其中的一个结点是另一个结点的邻接点。并称 这两个结点相互邻接。在一个图中不与任何结点相邻接的结点，称为孤立点 。在一个图中，如果两条边关联于同一个结点，则称其 中的一个边是另一个边的邻接边。并称这两个边相互邻接 。关联于同一个结点的一条边叫做环或自回路。在有向图 中环的方向可以是顺时针，也可以是逆时针，它们是

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

7、度 数的和等于边数的2倍。即： = 2|E|证明：图的每一条边都和两个结点相关联， 为每个相关联的结点增加一度, 给图增加两度。 所以所有结点度数的和等于边数的2倍。推论 在任何图G=V,E中，度数为奇数的 结点必为偶数个。第七章：图论【定义7.1.6】设G=V,E是有向图，vV，射入( 出)结点v的边数称为结点v的入(出)度。记为deg (v) (deg(v)。显然，任何结点的入度与出度的和等于该结 点的度数，即deg(v)=deg(v)+deg(v)。 【定理7.1.2】在有向图中，所有结点入度的和等 于所有结点出度的和。证明：在有向图中每一条边对应一个入度和 一个出度，为图的入度和出度各

8、增加1。所以， 所有结点入度的和等于边数，所有结点出度的和 也等于边数。 第七章：图论7.1.3多重图、简单图、完全图和正则图 【定义7.1.7 】 在图G中，连接同一对结点的多条相 同边称为平行边。平行边的条数称为该平行边的重数 。含平行边的图叫多重图。不含平行边和环的图叫简 单图。例如，在图7.3(a)中结点a和b之间有两条平行边 ，结点b和c之间有三条平行边，结点b上有两条平行 边，这两条平行边都是环。图7.3(a)不是简单图。又如，在图7.3(b)中结点v1和v2之间有两条平行 边。v2和v3之间的两条边，因为方向不同，所以不是 平行边。图7.3(b)不是简单图。简单图不含平行边和环。

9、 第七章：图论第七章：图论【定理7.1.3 】 设G为n阶简单无向图，则(G)n1。证明：因为G有n个结点，G的任何结点v最多只能 与其余的n1结点相邻接；又因为G为简单图，既无平 行边，又无环。所以deg(v)n1。由v的任意性，就有(G) =maxdeg(v) | vVn1。 【定义7.1.8 】 设G为n阶简单无向图，若G中的每个结 点都与其余的n1个结点相邻接，则称G为n阶无向完全 图。记为Kn。在n阶无向完全图中，给每一条边任意确 定一个方向，所得到的图称为n阶有向完全图。也记为 Kn。今后，将n阶无向完全图和n阶有向完全图统称为n 阶完全图。 第七章：图论【定理7.1.4】 n阶完

10、全图Kn的边数为证明：在Kn中，每个结点都与其余的n1结点 相邻接，即任何一对结点之间都有一条边，故边数 应为 【定义7.1.9 】设G为n阶简单无向图，若G中每个结 点都是k度的，则称G为k次正则图。 第七章：图论7.1.4图的同构在图论中只关心结点间是否有连线，而不关心结 点的位置和连线的形状。因此，对于给定的图而言， 如果将图的各结点安排在不同的位置上，并且用不同 形状的弧线或直线表示各边，则可以得到各种不同图 形。所以，同一图的图形并不惟一。由于这种图形表 示的任意性，可能出现这样的情况：看起来完全不同 的两种图形，却表示着同一个图。例如，在图7.4中，(a)和(b)两个图的图形不同，

11、 但它们的结构完全相同，是同一个图。为了描述看起来不同，而其结构完全相同的图， 引入了同构的概念。 第七章：图论第七章：图论【定义7.1.10】 设G1=V1,E1与G2=V2,E2是两 个无向图(有向图)，若存在双射函数f：V1V2，v1V1，v2V1(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的同构函数。 第七章：图论两个图同构必须满足下列条件：结点数相同。边数相同。

12、度数相同的结点数相同。这三个条件是两个图同构的必要条件，不是充分条 件。一般的，用上述三个必要条件判断两个图是不同构 的。两个图同构，它们的同构函数必须实现同度结点对 应同度结点。 第七章：图论7.1.5补图、子图和生成子图 【定义7.1.11】设G=V,E是n阶简单无向图，G中 的所有结点和所有能使G成为完全图的添加边组成 的图称为图G的相对于完全图的补图，简称为G的 补图。记 为 。若G ， 则称G为自补图。在图7.5中， (b)是(a)的补图， (a)与(b)同构，所 以(a)是自补图。 第七章：图论【定义7.1.12】设G=V,E与G1=V1,E1是两个图 。如果V1V且E1E，则称G

13、1是G的子图，G是G1 的母图；如果V1V且E1E，则称G1是G的真子图 ；如果V1V且E1E则称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：v5e8v4e5v2e6v5e7v3 是从v5到v3的路，v5是始点，v3是终点，长度为4。L2：v1e1v2e3v3 是从v1到v3的

14、路，v1是始点，v3是终点，长度为2。在简单图中没有平行边和环，路L：v0e1v1e2v2envn完全由 它的结点序列v0v1v2 vn确定。所以，在简单图中的路可以用结 点序列表示。 第七章：图论【定义7.2.2】 设G=V,E是图， L是从 v0到vn的路。若v0=vn，则称 L为回路。若L中所有边各异，则 称L为简单路。若此时又有v0=vn， 则称L为简单回路。若L中所有结 点各异，则称L为基本路。若此时 又有v0=vn，则称L为基本回路。若 L既是简单路，又是基本路，则称 L为初级路。若此时又有v0=vn，则 称L为初级回路。在图7.7中，L1是一条简单路 。L2是一条简单路、基本路、

15、初级 路。 第七章：图论【 定理7.2.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相同。 于是，此路两次通过同一个结点vk(vs)，所以在L上存在vs到自 身的回路Cks。在L上删除Cks上的一切边和除vs以外的一切结 点，得路L1：vie1v1ekvsejvj。L1仍为从结点vi到vj的路，且 长度至少比L

16、减少1。若路L1的长度小于等于n-1，则定理已 证。否则，重复上述过程。由于G有n个结点，经过有限步后 ，必得到从vi到vj长度小于等于n-1的路。第七章：图论推论 在n阶图G中，若从结点vi到vj(vivj)存在路，则必存在长度小于等于n-1的初级路。由定理7.2.1的证明过程知，本推论成立。类似的可证明下列定理和推论。【定理7.2.2】 在n阶图G中，若存在结点vi到自身的回路，则必存在vi到自身长度小于等于n的回路。推论 在n阶图G中，若存在结点vi到自身的简单回路，则必存在vi到自身长度小于等于n的初级回路。 【定义7.2.3】 在无向图G中，如果结点u和结点v之间存在 一条路，则称结点u和