《离散数学》第6章图的基本概念.ppt
《《离散数学》第6章图的基本概念.ppt》由会员分享,可在线阅读,更多相关《《离散数学》第6章图的基本概念.ppt(79页珍藏版)》请在三一办公上搜索。
1、图论是一个古老的数学分支,它起源于游戏难题的研究。图论的内容十分丰富,应用得相当广泛,许多学科,诸如运筹学、信息论、控制论、网络理论、博弈论、化学、生物学、物理学、社会科学、语言学、计算机科学等,都以图作为工具来解决实际问题和理论问题。随着计算机科学的发展,图论在以上各学科中的作用越来越大,同时图论本身也得到了充分的发展。本课程在第六、七章中介绍与计算机科学关系密切的图论的基础内容。,图论简介,内容:有向图,无向图的基本概念。,重点:1、有向图,无向图的定义,,第六章 图的基本概念,第一节 无向图及有向图,5、图的同构的定义。,一、图的概念。,1、定义。,无序积,无向图,有向图,2、图的表示法
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度
3、顶点,其余顶点的度数均小于等于2,问中至少有几个顶点?,三、子图,补图。,1、子图定义:,导出子图,例3、,上图中,(1)(6)都是(1)的子图,,其中(2)(6)为真子图,,(1)(5)为生成子图。,2、补图定义。,如例3中,,四、图的同构。,定义:,例4、,解:只有如下3个图:,解:只有如下4个图:,内容:图的通路,回路,连通性,点割集,边割集。,2、图的连通性的概念,,3、短程线,距离的概念。,第二节 通路,回路,图的连通性,一、通路,回路。,1、通路(回路),2、简单通路,简单回路。,简单通路(迹),简单回路(闭迹),复杂通路(回路),3、初级通路,初级回路。,初级通路(路径),初级回
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 基本概念

链接地址:https://www.31ppt.com/p-5903348.html