离散数学课件(第7章)

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

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】 设设G为图，

8、如果为图，如果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 中，度数为奇数的中，度数