离散数学图论基本概念.pptx

  1. 1、本文档共50页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
会计学 1 离散数学图论基本概念 2 14.1 图 定义14.1 无向图G = V,E, 其中 (1) V  为顶点集,元素称为顶点 (2) E为VV 的多重集,其元素称为无向边,简称边 实例 设 V = {v1, v2, …,v5}, E = {(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)} 则 G = V,E为一无向图 第1页/共50页 3 有向图 定义14.2 有向图D=V,E, 只需注意E是VV 的多重子集 图2表示的是一个有向图,试写出它的V 和 E 注意:图的数学定义与图形表示,在同构(待叙)的意义下 是一一对应的 第2页/共50页 4 相关概念 1. 图 ① 可用G泛指图(无向的或有向的) ② V(G), E(G), V(D), E(D) ③ n阶图 2. 有限图 3. n 阶零图与平凡图 4. 空图—— 5. 用 ek 表示无向边或有向边 6. 顶点与边的关联关系 ① 关联、关联次数 ② 环 ③ 孤立点 7. 顶点之间的相邻与邻接关系 第3页/共50页 5 8. 邻域与关联集 ① vV(G) (G为无向图) v 的关联集 ② vV(D) (D为有向图) 9. 标定图与非标定图 10. 基图 相关概念 第4页/共50页 6 多重图与简单图 定义14.3 (1) 无向图中的平行边及重数 (2) 有向图中的平行边及重数(注意方向性) (3) 多重图 (4) 简单图 在定义14.3中定义的简单图是极其重要的概念 第5页/共50页 7 顶点的度数 定义14.4 (1) 设G=V,E为无向图, vV, d(v)——v的度数, 简称度 (2) 设D=V,E为有向图, vV, d+(v)——v的出度 d(v)——v的入度 d(v)——v的度或度数 (3) (G), (G) (4) +(D), +(D), (D), (D), (D), (D) (5) 奇顶点度与偶度顶点 第6页/共50页 8 定理14.1 设G=V,E为任意无向图,V={v1,v2,…,vn}, |E|=m, 则 证 G中每条边 (包括环) 均有两个端点,所以在计算G中各顶点度数之和时,每条边均提供2度,m 条边共提供 2m 度. 本定理的证明类似于定理14.1 握手定理 定理14.2 设D=V,E为任意有向图,V={v1,v2,…,vn}, |E|=m, 则 第7页/共50页 9 握手定理推论 推论 任何图 (无向或有向) 中,奇度顶点的个数是偶数. 证 设G=V,E为任意图,令 V1={v | vV d(v)为奇数} V2={v | vV d(v)为偶数} 则V1V2=V, V1V2=,由握手定理可知 由于2m, 均为偶数,所以 为偶数,但因为V1中 顶点度数为奇数,所以|V1|必为偶数. 第8页/共50页 10 例1 无向图G有16条边,3个4度顶点,4个3度顶点,其余顶点度数均小于3,问G的阶数n为几? 解 本题的关键是应用握手定理. 设除3度与4度顶点外,还有x个顶点v1, v2, …, vx, 则 d(vi)  2,i =1, 2, …, x, 于是得不等式 32  24+2x 得 x  4, 阶数 n  4+4+3=11. 握手定理应用 第9页/共50页 11 图的度数列 1 . V={v1, v2, …, vn}为无向图G的顶点集,称d(v1), d(v2), …, d(vn)为G的度数列 2. V={v1, v2, …, vn}为有向图D的顶点集, D的度数列:d(v1), d(v2), …, d(vn) D的出度列:d+(v1), d+(v2), …, d+(vn) D的入度列:d(v1), d(v2), …, d(vn) 3. 非负整数列d=(d1, d2, …, dn)是可图化的,是可简单图化的. 易知:(2, 4, 6, 8, 10),(1, 3, 3, 3, 4) 是可图化的,后者又是可 简单图化的,而(2, 2, 3, 4, 5),(3, 3, 3, 4) 都不是可简单图化 的,特别是后者也不是可图化的

文档评论(0)

kuailelaifenxian + 关注
官方认证
内容提供者

该用户很懒,什么也没介绍

认证主体太仓市沙溪镇牛文库商务信息咨询服务部
IP属地上海
统一社会信用代码/组织机构代码
92320585MA1WRHUU8N

1亿VIP精品文档

相关文档