当前位置：文档之家 › 离散数学图

离散数学图

  • 格式：ppt
  • 大小：2.31 MB
  • 文档页数：237

下载文档原格式

  / 237

合集下载

《离散数学》图论 (上)

《离散数学》图论 (上)
12
无向图与有向图
v2
e1
e2
e3
v3
e4
v1
e5 (e1)={( v42, v24 )}
v4
(e2)={( v32, v23 )} (e3)={( v3, v4 )}
(e4)=({ v43, v34 )}
(e5)=({ v4,}v4 )
13
无向图与有向图
A B C
D E F
14
无向图与有向图
第八章 图论
第八章 图论
§8.1 基本概念
§8.1.1 无向图、有向图和握手定理 §8.1.2 图的同构与子图 §8.1.3 道路、回路与连通性 §8.1.4 图的矩阵表示
§8.2 欧拉图 §8.3 哈密尔顿图 §8.4 平面图 §8.5 顶点支配、独立与覆盖
2
无向图与有向图
3
无向图与有向图
一个无向图（undirected graph, 或graph） G 指一个三元组 (V, E, )，其中
vV
vV
24
特殊的图
假设 G=(V, E, ) 为无向图，若 G 中所有 顶点都是孤立顶点，则称 G 为零图（null graph）或离散图（discrete graph）；若 |V|=n，|E|=0，则称 G 为 n 阶零图 所有顶点的度数均相等的无向图称为正 则图（regular graph），所有顶点的度数 均为 k 的正则图称为k度正则图，也记作 k-正则图 注：零图是零度正则图
19
握手定理
定理（图论基本定理/握手定理）
假设 G=(V, E, ) 为无向图，则deg(v) 2 E ， vV
即所有顶点度数之和等于边数的两倍。
推论
在任何无向图中，奇数度的顶点数必是偶 数。

离散数学课件15欧拉图与哈密顿图

离散数学课件15欧拉图与哈密顿图

04
欧拉图与哈密顿图的应用 场景
欧拉图的应用场景
路径规划
欧拉图可以用于表示从一 个点到另一个点的路径， 常用于物流、交通和旅行 等领域。
网络流问题
欧拉图可以用于解决最大 流和最小割等问题，在网 络优化、资源分配和计划 制定等方面有广泛应用。
组合优化
欧拉图可以用于表示组合 优化问题，如旅行商问题、 排班问题等，是求解这些 问题的常用工具。
一个图存在哈密顿回路当且仅当其所有顶点的度都大于等于2 。
哈密顿图的性质
哈密顿图中的所有顶点的度都 大于等于2。
一个图存在哈密顿回路当且仅 当其所有顶点的度都大于等于2。回 路。
哈密顿图的构造方法
添加边法
在所有顶点的度都大于等于2的图 中，不断添加边，直到所有顶点的 度都大于等于2，最后得到的图就 是哈密顿图。
哈密顿图的应用场景
社交网络分析
哈密顿图可以用于表示社交网络 中的路径，分析人际关系和信息
传播路径。
生物信息学
哈密顿图可以用于表示基因组、蛋 白质组等生物信息数据，进行基因 序列比对、蛋白质相互作用分析等。
推荐系统
哈密顿图可以用于表示用户和物品 之间的关系，进行个性化推荐和智 能推荐。
欧拉图与哈密顿图在计算机科学中的应用
欧拉图的构造方法
欧拉图的构造方法1
总结词
通过添加一条边将所有顶点连接起来， 从而形成一个欧拉图。
详细描述了两种构造欧拉图的方法， 为实际应用中构造欧拉图提供了思路。
欧拉图的构造方法2
通过将两个欧拉图合并，并连接它们 的所有顶点，从而形成一个新的欧拉 图。
02
哈密顿图
哈密顿图的定义
哈密顿图（Hamiltonian Graph）是指一个图存在一个遍历其 所有边且每条边只遍历一次的路径，这个路径称为哈密顿路径， 如果该路径的起点和终点是同一点，则称这个路径为哈密顿回 路。

离散数学平面图

离散数学平面图
12
同胚与收缩
消去2度顶点v 如上图从(1)到(2) 插入2度顶点v 如上图从(2)到(1) G1与G2同胚: G1与G2同构, 或 经过反复插入、或消去2度顶 点后同构 收缩边e 如下图从(1)到(2)
13
库拉图斯基定理
定理 G是平面图G中不含与K5同胚的子图, 也不 含与K3,3同胚的子图.
例如 下图中(1)~(4)是平面图, (2)是(1)的平面嵌入， (4)是(3)的平面嵌入. (5)是非平面图.
2
平面图和平面嵌入(续)
• 今后称一个图是平面图, 可以是指定义中的平面图, 又可以
是指平面嵌入, 视当时的情况而定. 当讨论的问题与图的画
法有关时, 是指平面嵌入.
• K5和K3,3是非平面图 • 设G G, 若G为平面图, 则G 也是
8.4 平面图
平面图与平面嵌入 平面图的面、有限面、无限面 面的次数 极大平面图 极小非平面图 欧拉公式 平面图的对偶图
1
平面图和平面嵌入
定义 如果能将图G除顶点外边不相交地画在平面上, 则称G是平面图. 这个画出的无边相交的图称作G 的平面嵌入. 没有平面嵌入的图称作非平面图.
18
平面图的对偶图(续)
平面图与对偶图的阶数、边数与面数之间的关系: 设G*是平面图G的对偶图，n*, m*, r*和n, m, r分别 为G*和G的顶点数、边数和面数，则 (1) n*= r (2) m*=m (3) r*=n-p+1, 其中p是G的连通分支数 (4) 设G*的顶点vi*位于G的面Ri中, 则d(vi*)=deg(Ri)
例 黑色实线为原平面图, 红色虚线为其对偶图
17
平面图的对偶图(续)
性质：
• G*是平面图，而且是平面嵌入. • G*是连通图 • 若边e为G中的环，则G*与e对应的边e*为桥; 若e

离散数学离散数学第8章 一些特殊的图 PPT课件

离散数学离散数学第8章 一些特殊的图 PPT课件

在23岁时，他发表了他还是一个17岁的孩子时作出的“奇怪的发 现”，…即《光线系统理论》第一部分，这是一篇伟大的杰作，它对于 光学，就象拉格朗日的《分析力学》之于力学。
哈密尔顿最深刻的悲剧既不是酒精，也不是他的婚姻，而是他顽固地
相信，四元数是解决物质宇宙的数学关键。…从来没有一个伟大的数学
家这样毫无希望地错误过。
2
1
3
4
(2) 有限面与无限面：面积有限的区域称为有 限面(或内部面)，否则为无限面(或外部面) 。 上图中，面4是无限面。
7/1/2020 9:05 PM
第四部分：图论（授课教师：向胜军）
24
(3) 面的次数等于面边界的边数(注意：悬挂边算2 次)，记为deg(R).
(4) 平面图中面的次数之和等于边数m的两倍，即
d(u)+d(v)≥n-1 则G是半哈密尔顿图。
注意:
此定理条件显然不是必要条件，如n≥6的n边形，对于 任意不相邻的顶点u, v, d(u)+d(v)=4，4<n-1，而n边形显 然有哈密尔顿通路。
7/1/2020 9:05 PM
第四部分：图论（授课教师：向胜军）
18
哈密尔顿图的充分条件
❖ 设G是n(n≥3)阶无向简单图，若G中 任意不相邻的顶点对u,v均满足： d(u)+d(v)≥n 则G是哈密尔顿图。
a
bc
d
e
f g
h
i j
k
l
ba
d
g
e j
f
l
b
a
c
d
g
j
i
e
h
f
k
7/1/2020 9:05 PM

《离散数学》课件第14章图的基本概念

《离散数学》课件第14章图的基本概念
像这种形状不同，但本质上是同一个图的现象称 为图同构。
定义14.5（图同构）设两个无向图G1=<V1，E1>， G2=<V2，E2>，如果存在双射函数f：V1→V2，使得对 于 任 意 的 e=（vi，vj）∈E1 当 且 仅 当 e’=（f(vi)， f(vj)）∈E2，并且e与e’的重数相同，则称G1和G2是 同构的，记作G1≌G2。
若vi=vj，则称ek与vi的关联次 数为2；
若vi不是ek的端点，则称ek与vi 的关联次数为0。
无边关联的顶点称为孤立点 （isolated vertex） 。
19
定义(相邻) 设无向图G=<V，E>， 若∃et∈E且et=（vi,vj），则称vi和vj是相邻的 若ek,el∈E且有公共端点，则称ek与el是相邻的。
素称为有向边，简称边。 由定义，有向图的边ek是有序对<vi，vj>，称vi，
vj是ek的端点，其中vi为ek的始点（origin），vj为ek 的终点（terminus）。
当vi=vj时，称ek为环，它是vi到自身的有向边。
11
每条边都是无向边的图称为无向图（undirected graph）。
定义(邻接与相邻) 设有向图D=<V，E>， 若∃et∈E且et=<vi,vj>，则称vi邻接到vj，vj邻接 于vi。 若ek,el∈E且ek的终点为el的始点，则称ek与el是相 邻的。
20
定义14.4（度） 设G=<V，E>为一无向图，∀v∈V，称 v作为边的端点的次数之和为v的度数，简称为度 （degree），记为d(v)。
定理14.2 （有向图握手定理）设D=<V，E>为任 意的有向图，V={v1,v2,…,vn}，|E|=m，则

离散数学——图论 ppt课件

离散数学——图论 ppt课件

ppt课件
11
哥尼斯堡七桥问题
把四块陆地用点来表示，桥用点与点连线表 示。
ppt课件
12
欧拉将问题转化为：任何一点出发，是否存在通过 每条边一次且仅一次又回到出发点的路？欧拉的结 论是不存在这样的路。显然，问题的结果并不重要， 最为重要的是欧拉解决这个问题的中间步骤，即抽 象为图的形式来分析这个问题 。
因此，尽管本教材介绍的是较为基础的图论内容， 但阅读理解与完成习题是学习图论必不可少的步骤。
ppt课件
8
图是人们日常生活中常见的一种信息载体， 其突出的特点是直观、形象。图论，顾名思 义是运用数学手段研究图的性质的理论，但 这里的图不是平面坐标系中的函数，而是由 一些点和连接这些点的线组成的结构 。
P（G）表示连通分支的个数。连通图的连通 分支只有一个。
ppt课件
40
练习题---图的连通性问题
1.若图G是不连通的，则补图是连通的。 提示：直接证法。
根据图的不连通，假设至少有两个连通分 支；任取G中两点，证明这两点是可达的。
ppt课件
41
2.设G是有n个结点的简单图，且 |E|>(n-1)(n-2)/2，则G是连通图。
33
§8.2通路、回路与连通性
定义：通路与回路 设有向图G=<V,E>，考虑G中一条边的序列
（vi1,vi2,…, vik）,称这种边的序列为图的通路。 Vi1、vik分别为起点、终点。通路中边的条数称
为通路的长度。 若通路的起点和终点相同，则称为回路。
ppt课件
34
简单通路、基本通路
简单通路：通路中没有重复的边。 基本通路：通路中没有重复的点。 简单回路和基本回路。 基本通路一定是简单通路，但反之简单通路

离散数学PPT【共34张PPT】

离散数学PPT【共34张PPT】
15
18.4 点着色
定义17.9 (1) 图G的一种点着色——给图G的每个顶点涂上一种颜色，
使相邻顶点具有不同颜色 (2) 对G进行k着色（G是k-可着色的）——能用k种颜色给G
的顶点着色 (3) G的色数(G)=k——G是k-可着色的，但不是(k1)-可着色
的.
16
关于顶点着色的几个简单结果
定理17.19 (G)=1当且仅当G为零图 定理17.20 (Kn)=n 定理17.21 若G为奇圈或奇阶轮图，则(G)=3，若G为偶阶轮 图，则(G)=4. 定理17.22 若G的边集非空，则(G)=2当且仅当G为二部图.
路径 (7) M的交错圈——由M与EM中的边交替出现构成的G中圈
上图中，只有第一个图存在完美匹配
8
可增广路径及交错圈
(1)
(2)
(3)
设红色边在匹配M中，绿色边不在M中，则图(1)中的两条路 径均为可增广的交错路径；(2)中的全不是可增广的交错路 径；(3)中是一个交错圈. 不难看出，可增广交错路径中，不在M中的边比在M中的边 多一条. 交错圈一定为偶圈.
立集 (3) 最大点独立集——元素最多的点独立集 (4) 点独立数——最大点独立集中的元素个数，记为0
(1)
(2)
在图中，点独立数依次为2, 2, 3.
(3)
2
极大独立集与极小支配集
定理18.1 设G=<V,E>中无孤立点，则G的极大点独立集都是 极小支配集. 证明线索： (1) 设V*为G的极大点独立集，证明它也是支配集.
定理17.28 偶圈边色数为2，奇圈边色数为3. 定理17.29 (Wn) = n1, n4. 定理17.30 二部图的边色数等于最大度. 定理17.31 n为奇数（n1）时，(Kn)=n；
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

一开始，图论的理论价值似乎不大，因为图
论主要研究一些娱乐性的游戏问题：迷宫问 题、博弈问题、棋盘上马的行走线路问题。 但是随着一些图论中的著名问题如四色问题 （1852年）和哈密顿环游世界问题（1856 年）的出现，出现了以图为工具去解决其它 领域中一些问题的成果。
陕西师范大学计算机科学学院
1847年德国的克希霍夫将树的概念和理
陕西师范大学计算机科学学院
在自然界和人类社会中，用图形来描述
和表示某些事物之间的关系既方便又直观。
例如，国家用点表示，有外交关系的国家用
线连接代表这两个国家的点，于是世界各国
之间的外交关系就被一个图形描述出来了。
陕西师范大学计算机科学学院
另外我们ห้องสมุดไป่ตู้用工艺流程图来描述某项工程
中各工序之间的先后关系，用网络图来描述某
陕西师范大学计算机科学学院
定义10.1.1 一个图G定义为一个有序对<V, E>，记为G=<V, E>。其中V为非空有限集， 其元素称为结点或顶点（Vertex, Node）， E也是有限集，其元素称为边（Edge）。对E 中的每条边都有V中的两个结点与之对应，其 结点对可以有序也可无序。
陕西师范大学计算机科学学院
陕西师范大学计算机科学学院
图论的产生和发展经历了二百多年的历
史，大体上可分为三个阶段： 第一阶段是从 1736 年到 19 世纪中叶。 当时的图论问题是盛行的迷宫问题和游戏问 题。最有代表性的工作是著名数学家欧拉于 1736年解决的哥尼斯堡七桥问题。
陕西师范大学计算机科学学院
东普鲁士的哥尼斯堡城（今俄罗斯的加里宁格
题。
陕西师范大学计算机科学学院
哥尼斯堡七桥问题看起来并不复杂，因
此立刻吸引许多人的注意，但是实际上很难
解决。 瑞士数学家欧拉注意到了这个问题，并 在 1736 年写的有关 “ 哥尼斯堡七桥问题 ” 的论文中解决了这个问题。这篇论文被公认 为是图论历史上的第一篇论文，欧拉也因此 被誉为图论之父。
陕西师范大学计算机科学学院
论应用于电网络研究。1857年英国的凯莱也
独立地提出了树的概念，并应用于有机化合 物分子结构即CnH2n+2的同分异构物数目的研 究中。 1936年匈牙利的数学家哥尼格写出了第 一本图论专著《有限图与无限图的理论》， 标志着图论成为一门独立学科。
陕西师范大学计算机科学学院
第三阶段是 1936 年以后。由于生产管
理、军事、交通运输、计算机和通讯网络等
方面的大量问题的出现，大大促进了图论的
发展。特别是计算机的大量应用，使大规模
问题的求解成为可能。
陕西师范大学计算机科学学院
电网络、交通网络、电路设计、数据结
构以及社会科学中的问题所涉及到的图形都
是很复杂的，需要计算机的帮助才有可能进
行分析和解决。目前图论在物理、化学、运
若边e与无序结点对 [u, v]对应，称e为无
向边（ Undirected edge ），简称边，记为
e=[u, v]，u、v称为边e的端点，也称u和v为
邻接点，边 e关联 u与 v。关联同一结点的两条
边称为邻接边。连接一结点与它自身的边称为
离散数学
第十章
裘国永
2019年1月18日
图
本章内容及教学要点
10.1 图的基本概念 教学内容：结点（顶点），边，无向边， 有向边（弧），环（自回路）， 孤立结点，有向图，无向图， 度数，出（入）度， 欧拉握手定理
陕西师范大学计算机科学学院
10.2 路、回路与连通性 教学内容：路（通路），回路（圈）， 简单（回）路，基本（回）路， 连通图，连通分支，点（边）割集， 割（边），强（单向，弱）连通图， 强（单向，弱）分图
筹学、计算机科学、电子学、信息论、控制 论、网络理论、社会科学及经济管理等几乎 所有学科领域都有应用。
陕西师范大学计算机科学学院
10.1 图的基本概念
这一节的主要内容：
无（有）向边、环、孤立结点、无（有）
向图、混合图、基图、简单图、多重图、平凡
图、零图、完全图、加权图、度数、出度、入
度、欧拉握手定理。
通讯系统中各通讯站之间信息传递关系，用开
关电路图来描述IC中各元件电路导线连接关系 （芯片设计）等等。
陕西师范大学计算机科学学院
任何一个包含某种二元关系的系统都可
以用图形来表示。由于我们感兴趣的是两对
象之间是否有某种特定关系，所以图形中两 点之间连接与否最重要，而连接线的曲直长 短则无关紧要。由此经数学抽象产生了图的 概念。研究图的基本概念和性质、图的理论 及其应用构成了图论的主要内容。图是计算 机中数据表示、存储和运算的基础。
陕西师范大学计算机科学学院
欧拉是这样解决这个问题的：将四块陆
地表示成四个点，桥看成是对应结点之间的 连线。则哥尼斯堡七桥问题就变成了：从A， B ， C ， D 任一点出发，通过每边一次且仅一 次返回原出发点的路线（回路）是否存在？ 欧拉证明这样的回路是不存在的。
陕西师范大学计算机科学学院
第二阶段是从 19 世纪中叶到 1936 年。
勒）位于普雷格尔（ Pregel ）河的两岸，河中有
一个岛，于是城市被这条河、它的分支和岛分成了
四个部分，各部分通过7座桥彼此相通。该城的居
民喜欢在周日绕城散步。于是就产生了这样一个问
题：能不能设计一条散步的路线，使得一个人从家
里（或从四部分陆地任一块）出发，经过每座桥恰
好一次再回到家里？这就是有名的哥尼斯堡七桥问
陕西师范大学计算机科学学院
二叉树，树的遍历， 最优二叉树，
10.9 最短路径 教学内容：最短路径，Dijkstra算法
陕西师范大学计算机科学学院
图论是以图为研究对象的一个数学分
支。图论中的图指的是一些点以及连接这 些点的线的总体。通常用点代表事物，用 连接两点的线代表事物间的关系。图论则 是研究事物对象在上述表示法中具有的特 征与性质的学科。
陕西师范大学计算机科学学院
10.4 欧拉图与哈密顿图 教学内容：欧拉（回）路，欧拉图， 哈密顿（回）路，哈密顿图
陕西师范大学计算机科学学院
10.6 平面图 教学内容：平面图，面，边界，欧拉公式
陕西师范大学计算机科学学院
10.7 树及其应用 教学内容：树，树叶，分支点，生成树， 最小生成树，Kruskal算法， Prim算法，根树，有序树， Haffman算法