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

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

ID:59556780

大小:1.24 MB

页数:94页

时间:2020-11-10

离散数学第7章电子教案.ppt_第1页
离散数学第7章电子教案.ppt_第2页
离散数学第7章电子教案.ppt_第3页
离散数学第7章电子教案.ppt_第4页
离散数学第7章电子教案.ppt_第5页
资源描述:

《离散数学第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、连通,可达。无向图中,从到存在通路,称到是连通的(双向)。

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。