离散数学第7章.ppt_第1页
离散数学第7章.ppt_第2页
离散数学第7章.ppt_第3页
离散数学第7章.ppt_第4页
离散数学第7章.ppt_第5页
免费预览已结束,剩余89页可下载查看

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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

2、序积,无向图,有向图,一、图的概念。,1、定义。,无序积,2、图的表示法。,有向图,无向图的顶点都用小圆圈表示。,图形表示如右:,图形表示如右:,3、相关概念。,3、相关概念。,(2),3、相关概念。,(2),孤立点无边关联的点。,3、相关概念。,多重图含有平行边的图。,简单图不含平行边和环的图。,如例1的(1)中,,为孤立点,,为悬挂点,,为悬挂边,,为环,,为平行边,重数2,,为多重图。,4、完全图,例如:,二、顶点的度数,握手定理。,1、顶点的度数 (简称度)。,二、顶点的度数,握手定理。,1、顶点的度数 (简称度)。,最大度,最小度,如例1的(2)中,,,,。,2、握手定理。,定理1:

3、,定理2:,三、子图,补图。,1、子图定义:,三、子图,补图。,导出子图,例3、,上图中,(1)(6)都是(1)的子图,,其中(2)(6)为真子图,,(1)(5)为生成子图。,2、补图定义。,如例3中,,四、图的同构。,定义:,例4、,解:只有如下3个图:,解:只有如下4个图:,第二节 通路,回路,图的连通性,内容:图的通路,回路,连通性。,2、图的连通性的概念,,3、短程线,距离的概念。,一、通路,回路。,1、通路 (回路),一、通路,回路。,2、简单通路,简单回路。,简单通路 (迹),简单回路 (闭迹),复杂通路 (回路),一、通路,回路。,3、初级通路,初级回路。,初级通路 (路径),初

4、级回路 (圈),例1、(1),长度3,长度6,长度6,例1、(1),初级通路,简单通路,复杂通路,例1、(2),长度3,长度4,长度7,例1、(2),初级回路(圈),初级回路(圈),复杂回路,5、图中最短的回路。,如图:,6、性质。,定理:,推论:,6、性质。,定理:,推论:,6、性质。,二、图的连通性。,1、连通,可达。,2、短程线,距离。,距离短程线的长度,,(2),3、无向图的连通。,3、无向图的连通。,4、有向图的连通。,例2、,强连通,单向连通,例2、,单向连通,弱连通,非连通图,第三节 图的矩阵表示,内容:关联矩阵,邻接矩阵,可达矩阵。,重点:1、有向图,无向图的关联矩阵,,2、有

5、向图的邻接矩阵。,了解:有向图的可达矩阵。,一、无向图的关联矩阵。,解:,2、性质。,(1),(2),2、性质。,二、有向图的关联矩阵。,其中,解:,2、性质。,(1),(2),(3),三、有向图的邻接矩阵。,解:,2、性质。,(1),(2),(3),(1) 令,矩阵乘法,其中,其中,(2) 设,,,四、有向图的可达性矩阵。(了解),四、有向图的可达性矩阵。(了解),可达性矩阵,第七章 小结与例题,一、无向图与有向图。,1、基本概念。,一、无向图与有向图。,2、运用。,(1) 灵活运用握手定理及其推论,,(2) 判断两个图是否同构,,(3) 画出满足某些条件的子图,补图等。,二、通路,回路,图

6、的连通性。,1、基本概念。,二、通路,回路,图的连通性。,2、运用。,(1) 判断有向图或无向图中通路(回路)的类型。,(2) 求短程线和距离。,(3) 判断有向图连通的类型。,三、图的矩阵表示。,1、基本概念。,2、运用。,(1) 关联矩阵的行和、顶点度数间的关系。,(1),(2),(3),简单图,多重图,不是,(4),(5),(6),简单图,多重图,不是,(1),可以,(2),不可以,(3),可以,(4),不可以,(5),不可以,解:有7条,,解:,解:,解:有6个:,强连通,单向连通,弱连通,单向连通,强连通,强连通,(1),例7、下列各图中各有多少个顶点。,(1) 16条边,每个顶点的度数均为2。,例7、下列各图中各有多少个顶点。,(3) 24条边,每个顶点的度数均相同。,例7、下列各图中各有多少个顶点。,(3) 24

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论