离散数学第3章图的基本概念.ppt
《离散数学第3章图的基本概念.ppt》由会员分享,可在线阅读,更多相关《离散数学第3章图的基本概念.ppt(31页珍藏版)》请在三一文库上搜索。
1、计算机数学基础(上) 第2编 图 论,第三章 图的基本概念,3.1 图的概念与性质,一、图的定义与表示 1。图 由结点的集合V和边的集合E组成的有序对 称为图G。 2。有向图、无向图 每条边都是有向边的图称为有向图,每条边都是 无向边的图称为无向图,否则称为混合图。 3。孤立点、零图 不与其它结点相关联的结点称为孤立点,全部由 孤立点构成的图叫做零图。,4。边的重数 具有相同始点和终点的边称为平行边,平行边的 条数称为边的重数。 5。n 阶图 具有n个结点的图称为n阶图,具有n个结点和m 条边的图称为(n,m)图 6。结点的度数 图中与某结点v相关联的边数(自回路算两条边), 称为该结点的度数
2、,记作deg(v)。其中以v为始点的边 数称为出度deg+(v),以v为终点的边数成为入度deg-(v) 因此有 图G中结点的最大、最小度数记做(G)、(G),二、图的基本概念与握手定理 1。握手定理 图G中所有结点的度数之和等于边数的二倍。 推论1 在任何图中,度数为奇数的结点数必为偶数。 推论2 在有向图中,所有结点的入度之和等于所有结点的出度之和。 例题1: 已知图G中有1个1度结点,2个2度结点,3个3度结 点,4个4度结点,则G的边数是 。 解:,例题2: 设图G=,则下列结论成立的是 。 A) B) C) D) 例题3: 设简单连通无向图G有12条边,G中有2个1度结点, 2个2度
3、结点,3个4度结点,其余结点度数为3,求G中 有多少个结点。试作一个满足该条件的简单无向图。 解:设G中有x个结点,则3度的结点有x-7。 根据握手定理有,,解得 ,故G中有9个结点。 满足条件的图如下: 2。简单图 不含平行边和环(自回路)的图称为简单图。 在简单图中,任何结点的度数都小于等于n-1。这 是判断一个度数序列能否构成简单图的主要依据。 3。二部图 若将无向图G的结点集分为两部分,而每一部分中 任何两个结点之间都没有边相连,则G称为二部图。,4。完全图 每一对结点之间都有边相连的无向简单图称为无 向完全图,每一对结点之间都有方向相反的两条边相 连的有向简单图称为有向完全图。 具有
4、n个结点的无向完全图Kn的边数为: 例题4: 设图G是有n个结点的无向完全图,则G的边数为 。 A) n(n-1) B) n(n+1) C) D),C,5。正则图 若无向简单图G中每个结点的度数都为k,则G称 为k-正则图。 6。赋权图 若图G中的每一条边都有一个表示长度的实数, 则图G称为赋权图或网络。图G为无向图称为无向赋权 图,图G为有向图称为有向赋权图。 7。补图 由图G中的所有结点和构成完全图需添加的边所组成的图称为G的补图,记作 。,例题5: 已知图的结点集 以及图G和图D的 边集合分别为: 试作图G和图D,写出各结点的度数,回答图G、图D 是简单图还是多重图? 解:a d a d
5、 b c b c 图G 图D,图G: 图D: 图G不是简单无向图,图D是简单有向图。 8、子图 1。已知图G=,如果 则G=称为G的子图。 2。如果 ,则称G为G的真子图。 3。如果 ,则称G为G的生成子图。,三、图的同构 如果图G中的结点集V与图G中的结点集V具有 一一对应的关系,并且对应的边都具有相同的重数, 则称G与G同构,记作 。 因此,两图同构必须满足下列条件: 结点数相同, 边数相同, 度数相同的结点数相同。 上述条件是两图同构的必要条件,但不是充分条 件,也就是说,两个图即使满足上述条件也不一定同 构。如果把其中一个图中的结点重新排列,边跟着结 点移动,并且可以任意弯曲,能够与另
6、一图完全 重合,那么这两个图是同构的。,四、通路与回路 1。通路、回路 在G=中,如果从结点v0依次经过边和结 点可以到达vn,则称v0与vn间存在通路,或v0与vn连 通,记作v0vn ,如v0vn则称为回路。通路经过 的边数称为通路的的长度。 2。简单通路、简单回路 没有重复边的通路称为简单通路,没有重复边 的回路称为简单回路。 3。基本通路、基本回路 没有重复结点的通路称为基本通路,没有重复 结点的回路称为基本回路。,例题6: 设G如图,已知通路 试回答它们各是简单通路、简单回路、基本通路 和基本回路。 解:是简单通路,基本通路,是简单回路,但不 是基本回路,是简单回路,基本回路,是简单
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 基本概念
链接地址:https://www.31doc.com/p-2252423.html