第8章离散数学.ppt

第三篇 图 论 图论的简介： 图论是数学的一个分支，是研究由线连接的点 集的理论，它以图为研究对象。图论的应用范 围很广，它不但能应用于自然科学，也能应用 于社会科学。它非但广泛应用于电信网络、电 力网络、运输能力、开关理论、编码理论、控 制论、反馈理论、随机过程、可靠性理论、化 学化合物的辨认、计算机的程序设计、故障诊 断、人工智能、印制电路板的设计、图案识 辩、地图着色、情报检索，也应用于诸如语言 学、社会结构、经济学、运筹学、遗传学等方面。 图论作为一个数学分支，有一套完整的体系和广泛的内容，这里主要围绕与计算机科学有关的知识，只介绍图论的一些基本概念、定理和研究内容，同时给出一些相应的算法和应用，目的在于今后对计算机有关学科的学习和研究时，可以以图论的基本知识作为工具。 本章主要内容： 图 图的基本概念 通路、回路和连通图 图的连通性 图的矩阵表示 第八章 图 离散数学研究的图与几何图形、机械图形的区别： 离散数学研究的图是另一种数学结构，不关心图中顶点的位置、边的长短和形状, 只关心顶点与边的联结关系。 图可分为有限图和无限图两类, 本书只研究有限图, 即顶点和边都是有限集合。 8.1 图的基本概念 8.1.1图的定义 定义8.1 一个图是一个有序对（V,E)，记为G=(V,E)，其中 V={v1,v2,…,vn}为有限非空集合，vi 称为结点，简称V是顶点集，图G的顶点集用V(G)表示；E={e1,e2,…,em} 为有限的边集合，ei 称为边，每个ei 都有V中的结点对与之相对应，称E为边集或弧集。即每条边连结中的某两个点，图G的边集用E(G)表示。 如果E中的边对应中ei 的结点对是无序的 {vi, vj}，称ei 是无向边，记作ei ={ vi , vj} ，称vi ， vj 是 ei 的两个端点，顶点vi ， vj 称为是邻接的或相邻的，边ei 和顶点vi 与vj 均称为是关联的，即ei 关联于vi 与vj 。 关联于同一顶点的边称为自回路或自环，关联于同一对顶点的边多于一条时，称这些边是平行边，其条数称为是边的重数；不与任何顶点邻接的顶点称为孤立点；只与一条边关联的顶点称为悬挂点，它所关联的边称为悬挂边。 如果ei 与结点有序对(vi, vj)相对应， 称ei 是有向边，记ei =（vi , vj） ，称vi为ei的始点， vj为ei 的终点。 例8.1 在图8.1中，顶点 是？ ，边 是？，边 是？，边 是？。 例8.1 在图8.1中，顶点 是孤立点，边 是悬挂边，边 是自环，边 是平行边。 定义8.2 如果构成一个图的所有边均为无向边，称这个图为无向图，通常用符号G表示无向图；如果构成一个图的所有边均为有向边，称这个图为有向图，通常用符号D表示有向图；如果构成一个图的边集中，既有无向边，又有有向边，称这个图为混合图。 定义8.3 在图G中，如果 ， 称G为 图，n称为图G的阶。图 称为零图，即零图是全部由孤立点组成的。图 称为平凡图，即平凡图只有1个孤立点，没有边。规定顶点集和边集均为空的图为空图。含有平行边的图称为多重图。不含有自环和平行边的图称为简单图。顶点集和边集均为有限集的图称为有限图，否则称为无限图。 例8.2 判断图8.2中哪些是简单图： 解： 根据定义，只有图（a）和图（e）是简单图。 现在我们已经知道了什么图，那如果给定一个图，我们怎么来表示它呢？归结起来，可以有三种方法来表示一个图： 1. 定义描述法： 即用点的集合和边的集合来表示一个图。这种方法表示一个图比较有点是精确、但是太抽象不易理解。 2. 图形表示法：即用小圆圈表示顶点，用线段或弧线表示边。这种表示方法的优点是形象直观，但当图中的顶点和边的数目较大时，图形表示法是不方便的，甚至是不可能的。 3. 矩阵表示法：即用二进制的数 来表示图形中点与点、点与边的关系，这种方法的优点是计算机处理方便，可充分利用矩阵代数的运算定理，但图的许多性质用矩阵表示时会遇到困难，我们会在后面来详细讨论这个方法。 8.1.2 顶点的度数 定义8.4设无向图G=(V,E)。对于任意的vk?V，关联于顶点vk的边数称为顶点vk的度，用 d(k)表示。称度数为奇数的顶点为奇度顶点，度数为偶数的顶点为偶度顶点。 在有向图D中，以v为终点的边数称为v的入度，记作 di(v) ；以v为起点的边数称为v的出度，记作do(v)。且有