离散数学第7章电子教案.ppt

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

1、离散数学第7章第七章图的基本概念第一节无向图及有向图内容：有向图，无向图的基本概念。重点：1、有向图，无向图的定义，2、图中顶点，边，关联与相邻，顶点度数等基本概念，3、各顶点度数与边数的关系及推论，内容：有向图，无向图的基本概念。5、图的同构的定义。重点：4、简单图，完全图，子图，补图的概念，一、图的概念。1、定义。无序积无向图中元素为无向边，简称边。，有向图中元素为有向边，简称边。，一、图的概念。1、定义。无序积2、图的表示法。有向图，无向图的顶点都用小圆圈表示。无向边——连接顶点的线段。有向边——以为

2、始点，以为终点的有向线段。例1、(1)无向图，图形表示如右：图形表示如右：例1、(2)有向图，3、相关概念。(1)有限图——都是有限集的图。阶图——的图。零图——的图。特别，若又有，称平凡图。(2)关联(边与点关系)——设边(或)，则称与(或)关联。3、相关概念。(2)3、相关概念。(2)孤立点——无边关联的点。环——一条边关联的两个顶点重合，称此边为环(即两顶点重合的边)。3、相关概念。(2)悬挂点——只有一条边与其关联的点，所对应的边叫悬挂边。(3)平行边——关联于同一对顶点的若干条边称为平行边。平行边

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

4、度)。最大度最小度对有向图相应地还有，，，。如例1的(2)中，，。设为图的顶点集，称为的度数序列。2、握手定理。定理1：设图为无向图或有向图，为边数)，，(则定理2：设为有向图，，则，。2、握手定理推论：任何图中，度为奇数的顶点个数为偶数。例2、(1)能成为图的度数，序列吗？为什么？(2)已知图中有10条边，4个3度顶点，其余顶点的度数均小于3，问中至少有多少个顶点？为什么？三、子图，补图。1、子图定义：设是两个图，若，，且，则称是的子图，是的母图，记作。真子图——且(即或)。生成子图——且。三、子图，补图

5、。导出子图——非空，以为顶点集，以两端均在中的边的全体为边集的的子图，称的导出子图。——非空，以为边集，以中边关联的顶点的全体为顶点集的的子图，称的导出子图。例3、上图中，(1)－(6)都是(1)的子图，其中(2)－(6)为真子图，(1)－(5)为生成子图。2、补图定义。设为无向完全图，，为无向简单图，其中，，则称，相对于互为补图，记，。如例3中，四、图的同构。定义：设两个无向图，，若存在双射函数，使得对于任意的，当且仅当并且与重数相同，则称与同构，记作。例4、例5、(1)画出4个顶点，3条边的所有非同构的

6、无向简单图。解：只有如下3个图：例5、(2)画出3个顶点，2条边的所有非同构的有向简单图。解：只有如下4个图：第二节通路，回路，图的连通性内容：图的通路，回路，连通性。重点：1、通路，回路，简单通路，回路，初级通路，回路的定义，2、图的连通性的概念，3、短程线，距离的概念。一、通路，回路。1、通路(回路)中顶点和边的交替序列——，其中(无向图)，或(有向图)，——始点，——终点，称为到的通路。当时，为回路。一、通路，回路。2、简单通路，简单回路。简单通路(迹)简单回路(闭迹)复杂通路(回路)一、通路，回路。

7、3、初级通路，初级回路。初级通路(路径)初级回路(圈)初级通路(回路)简单通路(回路)，但反之不真。4、通路，回路的长度——中边的数目。例1、(1)图(1)中，从的通路有：到…………长度3长度6长度6例1、(1)图(1)中，从的通路有：到…………初级通路简单通路复杂通路例1、(2)…………长度3长度4长度7图(2)中过)有：的回路(从到例1、(2)…………初级回路(圈)初级回路(圈)复杂回路图(2)中过)有：的回路(从到5、图中最短的回路。如图：6、性质。定理：阶图中，若从顶点到存在通路，则从到存在长度小于

8、等于在一个的通路。推论：阶图中，若从顶点到存在通路，则从到存在长度小于等于在一个的初级通路。6、性质。定理：阶图中，若到自身存在回路，则从到自身存在长度小于等于的回路。在一个推论：阶图中，若到自身存在一个简单回路，则从到自身存在长度小于等于的初级回路。在一个6、性质。由以上定理可知，在阶图中，任何一条初级通路的长度任何一条初级回路的长度二、图的连通性。1、连通，可达。无向图中，从到存在通路，称到是连通的(双向)。