《离散数学》第6章图的基本概念.ppt
图论是一个古老的数学分支，它起源于游戏难题的研究。图论的内容十分丰富，应用得相当广泛，许多学科，诸如运筹学、信息论、控制论、网络理论、博弈论、化学、生物学、物理学、社会科学、语言学、计算机科学等，都以图作为工具来解决实际问题和理论问题。随着计算机科学的发展，图论在以上各学科中的作用越来越大，同时图论本身也得到了充分的发展。本课程在第六、七章中介绍与计算机科学关系密切的图论的基础内容。,图论简介,内容：有向图，无向图的基本概念。,重点：1、有向图，无向图的定义，,第六章 图的基本概念,第一节 无向图及有向图,5、图的同构的定义。,一、图的概念。,1、定义。,无序积,无向图,有向图,2、图的表示法。,有向图，无向图的顶点都用小圆圈表示。,图形表示如右：,图形表示如右：,3、相关概念。,孤立点无边关联的点。,多重图含有平行边的图。,简单图不含平行边和环的图。,如例1的(1)中，,为孤立点，,为悬挂点，,为悬挂边，,为环，,为平行边，重数2，,为多重图。,4、完全图,例如：,二、顶点的度数，握手定理。,1、顶点的度数(简称度)。,如例1的(2)中，,2、握手定理。,定理1：,定理2：,推论：,任何图中，度为奇数的顶点个数为偶数。,例2（1）（2，3，4，5，6，7），（1，2，2，3，4）能否构成无向图的度数序列？为什么？如能则画出图解,（2）已知图 中有11条边，有1个4度顶点，4个3度顶点，其余顶点的度数均小于等于2，问中至少有几个顶点？,三、子图，补图。,1、子图定义：,导出子图,例3、,上图中，(1)(6)都是(1)的子图，,其中(2)(6)为真子图，,(1)(5)为生成子图。,2、补图定义。,如例3中，,四、图的同构。,定义：,例4、,解：只有如下3个图：,解：只有如下4个图：,内容：图的通路，回路，连通性，点割集，边割集。,2、图的连通性的概念，,3、短程线，距离的概念。,第二节 通路，回路，图的连通性,一、通路，回路。,1、通路(回路),2、简单通路，简单回路。,简单通路(迹),简单回路(闭迹),复杂通路(回路),3、初级通路，初级回路。,初级通路(路径),初级回路(圈),例1、(1),长度3,长度6,长度6,初级通路,简单通路,复杂通路,(2),长度3,长度4,长度7,初级回路(圈),初级回路(圈),复杂回路,5、图中最短的回路。,如图：,6、性质。,定理3：,推论：,定理4：,推论：,二、图的连通性。,1、连通，可达。,2、短程线，距离。,距离短程线的长度，,(2),3、无向图的连通。,4、有向图的连通。,例2、,强连通,单向连通,单向连通,弱连通,非连通图,三、点割集，边割集。,1、设无向图 是连通图，若有顶点集，使 删除（将 中顶点及其关联的边都删除）后，所得子图 是不连通的或是平凡图；而删除 中的任何真子集 后，所得子图是连通的，则称 是 的点割集若点割集中只有一个顶点，则称该点为割点,2、设无向图 是连通图，若有边集，使 删除（将 中的边从 中全部删除）后，所得子图 是不连通的或是平凡图；而删除 中的任何真子集 后，所得子图 是连通的，则称 是 的边割集若边割集中只有一条边，则称该边为割边或桥,内容：关联矩阵，邻接矩阵，可达矩阵。,重点：1、有向图，无向图的关联矩阵，,2、有向图的邻接矩阵。,了解：有向图的可达矩阵。,第三节 图的矩阵表示,一、无向图的关联矩阵。,解：,2、性质。,(1),(2),二、有向图的关联矩阵。,其中,解：,2、性质。,(1),(2),(3),三、有向图的邻接矩阵。,解：,2、性质。,(1),(2),(3),(1)令,矩阵乘法,其中,其中,(2)设,，,四、有向图的可达性矩阵。(了解),可达性矩阵,第四节 最短路径及关键路径,内容：带权图，最短路径，Dijkstra算法，,PERT图，关键路径,重点：Dijkstra算法,了解：关键路径问题,1、对于无向图或有向图 的每条边附加一个实数，则称 为边 上的权连同附加在各边上的实数称为带权图常记带权图为,一、最短路径问题,2、在一个带权图 中，任给两点 和，从 到 可能有好几条通路在这些通路中，求出所带权的总和最小的那条通路称为最短路径）,3、Dijkstra标号法,开始，给出始点 的 标号：，,，,的 标号,第 步 求下一个 标号顶点,设，将 标在相应顶点 处，表明 获得 标号,修改通过集 和未通过集,查：若，则算法结束，否则转第2步,第 步 修改 中各顶点的 标号：,是刚刚获得 标号顶点的 标号,令，转第 步,二、关键路径问题,1、PERT图,2、最早完成时间,3、最晚完成时间,4、缓冲时间,一、无向图与有向图。,1、基本概念。,第六章 小结与例题,2、运用。,(1)灵活运用握手定理及其推论，,(2)判断两个图是否同构，,(3)画出满足某些条件的子图，补图等。,二、通路，回路，图的连通性。,1、基本概念。,2、运用。,(1)判断有向图或无向图中通路(回路)的类型。,(2)求短程线和距离。,(3)判断有向图连通的类型。,三、图的矩阵表示。,1、基本概念。,2、运用。,(1)关联矩阵的行和、顶点度数间的关系。,四、最短路径和关键路径,1、基本概念。,权，带权图，最短路径，标号法,PERT图，最早完成时间，后继元集，先驱元集,最晚完成时间，缓冲时间,2、运用。,（1）标号法求解最短路径问题,（2）求解关键路径问题,(1),(2),(3),简单图,多重图,不是,(4),(5),(6),简单图,多重图,不是,(1),可以,(2),不可以,(3),可以,(4),不可以,解：,解：有6个：,强连通,单向连通,弱连通,单向连通,强连通,强连通,(1),
