免费注册 登录
»教育专区»高等教育»图论.ppt
收起/展开

图论

文档类型:ppt 上传时间:2018-06-30 文档页数:157页 文档大小:416.50 K 文档浏览:8167次 文档下载:0次 所需积分:0 学币 文档评分:3.0星

图论内容摘要: 离 散 数 学图 论李 舟 军 2001.12 2图 论主要内容1. 图论的基本概念2. 子图和图的运算3. 路径、回路和连通图4. 欧拉图和哈密顿图5. 图的矩阵表示6. 树、有向树和有序树 2001.12 3图 论图论已有二百多年历史 ( 以 Euler 研究歌尼斯堡七桥问题为发端 )。近四十年来发展十分迅速,成为一个新兴的数学分支。1 、计算机科学中许多概念、算法需要图论支持 ( 如二叉树 ) 。2 、为计算机应用建模提供数学工具总而言之,“ 图论之为用 大矣哉!” 2001.12 4图 论§7.1 图论的基本概念 2001.12 5图 论图论的基本概念目的:了解图论的基本概念;重点:图论的基本概念;难点:度、图同构。 2001.12 6图 论无向图、有向图设 V 和 E 是有限集合,且 V ≠i) 如果 Ψ : E → {{ v1, v2}| v1∈ V且且 v2V∈ },则称 G = 〈V且,E, Ψ 〈为 无向图。i) 如果 Ψ : E → V×V ,则称 G =〈V且,E, Ψ 〈为 有向图。注意: E 可为空 零图 一个 E 中元素可对应二个相同的 V 中元素 自圈 多个 E 中的元素可对应 V 中相同的二元素 平行边无向图和有向图 统称为图,其中 V 的元素称为图 G 的结点 ( 顶点 ) ,E 的元素称为图 G 的边,图 G 的结点数目称为它的 阶。 2001.12 7图 论无向图 有向图 混合图* 混合图中无向边可用一对方向相反的有向边代替本章仅讨论无向图和有向图 2001.12 8图 论图的最本质内容:结点和边的对应关系。用几何图形表示图:小圆圈表示结点无向图:若 Ψ(e) = {ve) = {v) = {vv1, v2} ,就用一条连接结点 v1和 v2的无向线段 表示边 e) = {v有向图:若 Ψ(e) = {ve) = {v) =〈 v1, v2〈,就用一条由 v1指向 v2的有向线段 表示边 e) = {v 2001.12 9图 论关联、邻接 结点和边的关系——设无向图 G = 〈V且,E, Ψ 〈, e) = {v , e) = {v1, e) = {v2E∈ 且 v1, v2V∈• 如果 Ψ(e) = {ve) = {v) = { v1, v2},则称 e) = {v 与 v1(e) = {v 或 v2) 互相关联, e) = {v 连接 v1和 v2, v1和 v2既是 e) = {v 的起点,也是 e) = {v 的终点,也称 v1和 v2邻接。• 如果两条不同边 e) = {v1和 e) = {v2与同一个结点关联, 2001.12 10图 论关联、邻接 结点和边的关系——设有向图 G = 〈V且,E, Ψ 〈, e) = {v ∈E 且 v1, v2∈V 。若 Ψ(e) = {ve) = {v) = 〈 v1, v2〈,则称 e) = {v 连接 v1和 v2, e) = {v 与 v1(e) = {v 或 v2) 互相关联,分别称 v1和 v2是 e) = {v 的起点和终点,也称 v1和 v2邻接。 2001.12 11图 论自圈、平行边、简单图设图 G = 〈V且,E, Ψ 〈, e) = {v1和 e) = {v2是 G 的两条不同边。i) 如果与 e) = {v1关联的两个结点相同,则称 e) = {v1为自圈;ii) 如果 Ψ(e) = {ve) = {v1) = Ψ(e) = {ve) = {v2) ,则称 e) = {v1与 e) = {v2平行;iii) 如果图 G 没有自圈,也没有平行边,则称 G 为简单图我们一般只讨论有限图。 2001.12 12图 论有多少条边与某一个结点相关联? 结点的—— 度 2001.12 13图 论度设 v 是图 G 的结点。i) 如果 G 是无向图, G 中与 v 关联的边和与 v 关联的自圈的数目之和称为 v 的度,记为 dG(e) = {vv) 。ii) 如果 G 是有向图, G 中以 v 为起点的边的数目称为v 的出度,记为 d G+(v) ;G 中以 v 为终点的边的数目称为 v 的入度 , 记为 d G-(v) ;v 的出度与入度之和称为 v 的度,记为 dG(e) = {vv) 。注意: 在计算无向图中结点的度时,自圈要考虑两遍,因为自圈也是边。(例) 2001.12 14图 论定理 7.1.1 、定理 7.1.2定理 7.1.1 设无向图 G = 〈V且,E , Ψ 〈有 m 条边,则  v V∈dG(e) = {vv) = 2m定理 7.1.2 设有向图 G =〈V且,E , Ψ 〈有 m 条边,则  v V∈dG+(e) = {vv) = v V∈dG-(e) = {vv) = m ,且v V∈dG(e) = {vv) = 2m 。 2001.12 15图 论奇结点、偶结点度为奇数的结点称为奇结点;度为偶数的结点称为偶结点。 2001.12 16图 论任何图中都有偶数个 奇结点。定理 7.1.3 2001.12 17图 论孤立点、端点度为 0 的结点 称为 孤立点;度为 1 的结点 称为 端点。 2001.12 18图 论定义以下特殊图:i) 结点都是孤立点的图称为零图。ii) 一阶零图称为平凡图。iii) 所有结点的度均为自然数 d 的无向图称为 d 度正则图。iv) 设 n ∈I+,如果 n 阶简单无向图 G 是 n-1 度正则图,则称 G 为 完全无向图,记为 Kn。v) 设 n ∈I+,每个结点的出度和入度均为 n-1 的 n 阶简单有向图称为 完全有向图。零图、平凡图、 d 度正则图、完全图注意: 完全图必是正则图,但正则图不一定是完全图。 2001.12 19图 论思考题证明:在任意六个人中,若没有三个人彼此都认识,则必有三个人彼此都不认识。 2001.12 20图 论图的最本质内容:结点和边的关联关系。 2001.12 21图 论同 构设图 G =〈V且,E, Ψ 〈和 G′ =〈V且 ,E ,′,E′, ′,E′, Ψ′ 〈。如果存在 双射 f : V→ V且 和′,E′, 双射 g : E→ E ,使得′,E′,对于任意 e) = {v∈ E 及 v1, v2∈ V且 都有:{ f (e) = {vv1) , f (e) = {vv2) } , 若 Ψ(e) = {ve) = {v) = { v1, v2}Ψ' (e) = {v g (e) = {v e) = {v ) ) =〈 f (e) = {vv1) , f (e) = {vv2) 〈 , 若 Ψ(e) = {ve) = {v) = 〈 v1, v2〈则称 G 与 G′ 同构,记做 G  G ,并称′,E′, f 和 g 为 G 与 G′ 之 2001.12 22图 论难题:判断两个图同构的简单而充分的条件 ?可以给出一些两个图同构的必要条件!两个同构的图必有相同的结点个数和边数,并且:1 )双射 f 保持结点之间的邻接关系,2 )双射 g 保持边之间的邻接关系。 2001.12 23图 论同 构 的 无 向 图例 2001.12 24图 论wx vuvuxw' '''同构的有向图 2001.12 25图 论判断下图是否同构?121′65432′ 6′4′3′5′1″2″5″6″4″3″ 2001.12 26图 论作业习题 7.15, 6, 7, 8, 9, 10, 11 。 2001.12 27图 论§7.2 子图和图的运算 2001.12 28图 论子图和图的运算目的:了解子图和图的基本概念;重点:子图、可运算、图的运算;难点:图的运算、子图。 2001.12 29图 论子图、真子图、生成子图设图 G =〈V且,E, Ψ 〈, G′ =〈V且 ,E ,′,E′, ′,E′, Ψ′ 〈。i) 如果 V′ V , E′ E , Ψ′ Ψ ,则称 G′ 是 G 的子图, 记为 G′ G ,并称 G 是 G′ 的母图。ii) 如果 V′ V , E′ E , Ψ′ Ψ ,则称 G′ 是 G 的真子图,记为 G′ G 。iii) 如果 V′ = V , E′ E , Ψ′Ψ ,则称 G′ 是 G 的生成子图。 2001.12 30图 论由结点集导出的子图设图 G =〈V且,E, Ψ 〈, V′ V 且 V′≠  。以 V′ 为结点集合,以起点和终点均在 V′ 中的边的 全体为边集合的 G 的子图,称为由 V′ 导出的 G 的子图,记为 G [ V′ ]。若 V′ V ,导出子图 G [ V – V′ ]记为 G – V′ 。* G – V′ 是从 G 中去掉 V′ 中的结点以及与这些结点关联的边 而得到的 G 的子图 。 2001.12 31图 论设图 G =〈V且,E, Ψ 〈, E′,E′, E 且 E′≠  , V′={ v | v∈ V且且存在 e) = {v∈ E 使′,E′, v 与 e) = {v 关联}。 以V′ 为结点集合 ,以 E′ 为边集合的 G 的子图 称为 由E′ 导出的子图,记为 G [E ]。′,E′,由边集导出的子图 2001.12 32图 论从图示看,图 G 的子图是 G 的一部分,G 的真子图的边比 G 的边少,G 的生成子图与 G

离散数学图论李 舟 军图论
2001.122图 论主要内容1.图论的基本概念2.子图和图的运算3.路径
2001.123图 论图论已有二百多年历史(以Euler研究歌尼斯堡七桥问
2001.124图 论§7.1图论的基本概念图论
还剩 153页未读,点此继续全文在线阅读

免费下载图论到电脑,使用更方便!

本文推荐: 图论.ppt全文阅读下载  关键词: 图论  
温馨提示:图论.ppt由用户自行上传分享,文档预览可能有差异,下载后仅供学习交流,未经上传用户书面授权,请勿作他用。
< / 157>

QQ|小黑屋|网站声明|网站地图|学文库 ( 冀ICP备06006432号 )

GMT+8, 2020-5-26 11:34 , Processed in 0.244486 second(s), 4 queries , Gzip On, Redis On.

Powered by 学文库 1.0

Copyright © 2019-2020, 学文库

返回顶部