- 1、本文档共22页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
第三部分 图 论 一、 图的概念 二、 图的类型 三、 结点的度数 四、 握手定理 五、 同构概念 六、 邻接矩阵 引 言 图论研究图的逻辑结构与性质. 引 言 哥尼斯堡七桥问题 (一) 图的定义: 图G = V,E, 其中 (1) V ? ?为顶点集, 其元素称为结点(顶点)--用来表示事物 (2) E为V?V 的多重集。 其元素称为边--表示事物间的二元关系 (二) 结点与边的关系: ① 结点与边(不)相 关联: 有向图与无向图: 注意:完全图是 n-1 正则图 完全图的每个结点都与其它 n-1 个结点相邻接,即与n-1条边相关联,所以是n-1正则图,反之正则图不一定是完全图。 1.完全图: 2.正则图: 是3正则图 完全图, 不是完全图 图G 图G1 图G2 握手定理推论及应用 推论 任何图 (无向或有向) 中,奇度顶点的个数是偶数. 五、图的同构 定义 设G1=V1,E1, G2=V2,E2为两个图(有向或无向图), (1)若存在双射函数f:V1?V2, 对于vi,vj?V1, (vi,vj)?E1 当且仅当 (f(vi),f(vj))?E2 (vi,vj?E1 当且仅当 f(vi),f(vj)?E2 ) (2)(vi,vj)(vi,vj)与 (f(vi),f(vj))(f(vi),f(vj))的重数相同。 则称G1与G2是同构的,记作G1?G2. 图同构的必要条件 图同构的实例 * 第一讲 图论的基本概念与握手定理 主要内容 图论最早起源于一些数字游戏的难题研究.图论的最早论文是1736年瑞士数学家欧拉(Leonhard Euler)所写,从而使欧拉成为图论的创始人。 图论是组合数学的一个分支,研究集合上的二元关系的工具,是建立数学模型的一个重要手段。在物理、化学、信息学、运筹学等各方面都取得了丰硕的成果。计算机的迅速发展,使得图论成为数学领域里发展最快的分支之一。 当时哥尼斯堡(Konigsberg)城(现名加里宁格勒,属俄罗斯)的居民有郊游的习惯,在城郊的普雷格尔(Pregel)河畔,河中有两个小岛,七座桥将两个小岛和河岸连接起来,如图所示,问一个人能否从任一小岛出发不重复地走遍七座小桥? 1852年毕业于伦敦大学的弗南西斯·格思里发现了一种有趣的现象:“看来,每幅地图都可以用四种颜色着色,使得有共同边界的国家都被着上不同的颜色。”这个现象能不能从数学上加以严格证明呢? 四色问题 Hamilton问题 1856年,英国数学家Hamilton设计了一个名为周游世界的游戏:他用一个正十二面体的二十个端点表示世界上的二十座大城市(见图),提出的问题是要求游戏者找一条沿着十二面体的棱通过每个端点恰好一次的行走路线。 此路线称为:哈密尔顿回路, 而此图称为:哈密尔顿图。 一、图的概念 ② 结点与结点,边与边(不)相邻接 一、图的概念 (三) 特殊点 孤立点: 不与任何结点相邻接的结点 悬挂点: 只与一条边相关联的结点 (四) 特殊的边: 环: 一条边若与两个相同的结点相关联则称为环。 多重边(平行边):与两个结点相关联的边若多于一条,则称这些边为多重边。 简单图与多重图: 简单图--不含环与多重边;多重图--含多重边 有权图与无权图: b.按边的种类分类: 有限图与无限图: V与E为有限集合的图叫有限图,否则叫无限图。 (n,m)图:有 n 个结点与 m 条边的图。 零图: 即(n,0)图; 平凡图: 即(1,0)图。 完全图:任意两个结点都相邻接的图。 K-正则图:每个结点都与K条边相关联。 c. 按结点集与边集的“阶”分类 a 按边的方向分类 二、 图的类型 二、 图的类型 子图: 设G=V,E, G`=V`,E`为两个图,满足V`? V且E`? E,则称G`为G的子图, G为G`的母图,记作G`?G。 (1)G`为G的真子图:若G`? G且V` ? V或E`? E。 (2)G`为G的生成子图:若G`? G且V` = V。 (3)V1导出的导出子图:顶点集?≠V1 ? V,边集为两端点均在V1中的全体边构成的子图。 (4) E1导出的导出子图:?≠E1?E,以E1中边关联的顶点的全体为顶点集的G的子图。 二、 图的类型 a b c d a1 b1 a b c d d1 a1 b1 c1 a b c d d1 b1 a b c d d1 a1 b1 c1 母图
您可能关注的文档
最近下载
- 小学作文审题技巧(整理).ppt
- AI技术在汽车保险行业的应用.pptx
- 掩模板光刻工艺研究-电子与通信工程专业论文.docx
- 托盘四向穿梭车式密集库设计规范.docx
- 伤害预防概述和策略答案-2024年全国疾控系统“大学习”活动.docx VIP
- Unit+8+section+B+reading说课课件2023-2024学年人教版英语八年级上册.pptx VIP
- 超星网课尔雅《国学智慧》超星尔雅答案2023章节测验答案.pdf
- AI智能在车险中的应用研究.pptx
- 酒店客房运营管理:客房异常情况处理与应急预案培训ppt课件.pptx
- 宜家 橱柜 FABRIKOR 法布利克 玻璃门柜 402.422.95 安装指南.pdf
文档评论(0)