离散数学6——8章ppt

《离散数学6——8章ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论简介图论是一个古老的数学分支，它起源于游戏难题的研究。图论的内容十分丰富，应用得相当广泛，许多学科，诸如运筹学、信息论、控制论、网络理论、博弈论、化学、生物学、物理学、社会科学、语言学、计算机科学等，都以图作为工具来解决实际问题和理论问题。随着计算机科学的发展，图论在以上各学科中的作用越来越大，同时图论本身也得到了充分的发展。第八章图论第一节图的基本概念内容：有向图，无向图的基本概念。重点：1、有向图，无向图的定义，2、图中顶点，边，关联与相邻，顶点度数等基本概念，3、各顶点度数与边数的关系及推论，内容：有向图，无向图的基本概念。5、图的同构的定

2、义。重点：4、简单图，完全图，子图，补图的概念，2、图的表示法。有向图，无向图的顶点都用小圆圈表示。无向边——连接顶点的线段。有向边——以为始点，以为终点的有向线段。例1、(1)无向图，图形表示如右：图形表示如右：例1、(2)有向图，3、相关概念。(1)有限图——都是有限集的图。阶图——的图。零图——的图。特别，若又有，称平凡图。(2)关联(边与点关系)——设边(或)，则称与(或)关联。3、相关概念。(2)3、相关概念。(2)孤立点——无边关联的点。环——一条边关联的两个顶点重合，称此边为环(即两顶点重合的边)。3、相关概念。(2)悬挂点——只有一条

3、边与其关联的点，所对应的边叫悬挂边。(3)平行边——关联于同一对顶点的若干条边称为平行边。平行边的条数称为重数。多重图——含有平行边的图。简单图——不含平行边和环的图。如例1的(1)中，与关联的次数均为1，与关联的次数为2，边都是相邻的，为孤立点，为悬挂点，为悬挂边，为环，为平行边，重数2，为多重图。4、完全图设为阶无向简单图，若中每个顶点都与其余个顶点相邻，则称为阶无向完全图，记作。若有向图的任一对顶点，既有有向边又有有向边，则称为有向完全图。例如：二、顶点的度数，握手定理。1、顶点的度数(简称度)。无向图的度数记，指与，相关联的边的条数。有向图的

4、度数，二、顶点的度数，握手定理。1、顶点的度数(简称度)。最大度最小度对有向图相应地还有，，，。如例1的(2)中，，。设为图的顶点集，称为的度数序列。2、握手定理。定理1：设图为无向图或有向图，为边数)，，(则定理2：设为有向图，，则，。2、握手定理推论：任何图中，度为奇数的顶点个数为偶数。三、子图，补图。1、子图定义：设是两个图，若，，且，则称是的子图，是的母图，记作。真子图——且(即或)。生成子图——且。三、子图，补图。导出子图——非空，以为顶点集，以两端均在中的边的全体为边集的的子图，称的导出子图。——非空，以为边集，以中边关联的顶点的全体为顶

5、点集的的子图，称的导出子图。例3、上图中，(1)－(6)都是(1)的子图，其中(2)－(6)为真子图，(1)－(5)为生成子图。2、补图定义。设为无向完全图，，为无向简单图，其中，，则称，相对于互为补图，记，。如例3中，四、图的同构。定义：设两个无向图，，若存在双射函数，使得对于任意的，当且仅当并且与重数相同，则称与同构，记作。例4、例5、(1)画出4个顶点，3条边的所有非同构的无向简单图。解：只有如下3个图：例5、(2)画出3个顶点，2条边的所有非同构的有向简单图。解：只有如下4个图：第二节路径和回路（1）内容：图的通路，回路，连通性。重点：1、通

6、路，回路，简单通路，回路，初级通路，回路的定义，2、图的连通性的概念，3、短程线，距离的概念。一、路径，回路。1、路径(回路)中顶点和边的交替序列——，其中(无向图)，或(有向图)，——始点，——终点，称为到的通路。当时，为回路。一、路径，回路。2、简单路径，简单回路。简单路径(迹)：同一条边不出现两次基本路径（链）：同一顶点不出现两次简单回路(闭迹)：没有相同边的回路基本回路：通过各顶点不超过一次的回路一、路径，回路。基本路径(回路)简单路径(回路)，但反之不真。3、路径，回路的长度——中边的数目。例1、(1)图(1)中，从的路径有：到…………长度

7、3长度6长度6例1、(1)图(1)中，从的路径有：到…………基本路径简单路径复杂通路例1、(2)…………长度3长度4长度7图(2)中过)有：的回路(从到例1、(2)…………基本回路(圈)基本回路(圈)复杂回路图(2)中过)有：的回路(从到4、性质。定理1：阶图中，若从顶点到存在路径，则从到存在长度小于等于在一个的基本路径。（定理8.2-1）4、性质。定理2：阶图中，若到自身存在一个简单回路，则从到自身存在长度小于等于的基本回路。（定理8.2-2）在一个二、图的连通度。1、连通，可达。无向图中，从到存在通路，称到是连通的(双向)。有向图中，从到存在通路

8、，称可达(注意方向)。2、短程线，距离。短程线——连通或可达的两点间长度最短的通路。距离——短程线的长度，记