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(G),G其中： V(
4、G)=a,b,c,dE(G)=e1,e2,e3,e4G： 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)是混合图。 第七章：图论在一个图中，若两个结点由一条边 (有向边或无向边 )关联，则称其中的一个结点是另一个结点的邻接点。并称这两个结点相互邻接。在一个图中不与任何结点相邻接的结点，称为孤立点。在一个图中，如果两条边关联于同一个结点，则称其中的一个边是另一个边的邻接边。并称这两个边相互邻接。关联于同一个结点的一条边叫做环或自回路。在有向图中环的方向可以是顺时针，也可以是逆时针，它们是等效的。【 定义 7.1.4】 由孤立点组成的图叫做零图。由一个孤立点组成的图叫做平凡图。根据 定义 7.1.4， 平凡图一定是零图。
