当前位置：文档之家 › 图的定义和术语(4).ppt

图的定义和术语(4).ppt

  • 格式：ppt
  • 大小：4.25 MB
  • 文档页数：103

下载文档原格式

  / 103

合集下载

图论是离散数学

图论是离散数学

1
2
比如，顶点3的度是3。
3
Input Output
Total
4
5
• 有向图中，分入度和出度两部分，满足： TD(v) =
ID(v) + OD(v) 。
1
2
比如，顶点3的入度是1，出度为1，
度为2
3
4
7.2 图的相关术语
7.2.5 度
• 一般地，若图G中有n个顶点，e条边或弧，则图中
边与顶点的度的关系如下：
能否从河岸或小岛 出发，通过每一座 桥，而且仅仅通过 一次回到原地？
1736 年 29 岁的欧拉解决了该问题，这也意味新的 数学分支——图论的诞生
7.1 图的定义和基本术语
7.1.1 背景
• 四色问题（世界三大数学难题之一）
证明不论地图多么复 杂，最多使用四种颜 色就能保证相邻地区 使用不同颜色。
• G1是有向图（包含弧的图）
7.1 图的定义和基本术语
1
2
3
4
G1
7.1.3 图的基本术语
• G2是无向图（没有弧的图） • G2中有边(1,4), (1,2), (2,3),
(2,5), (3,5), (3,4) • 无序对（x，y）表示x和y之间的
一条边（edge）。所谓无序对， 就是指（x，y）等同于（y，x） • 1条边等于2条弧，即(1,4)等于 <1,4>加上<4,1>
• 图就是数据元素间为多对多关系的 1
2
数据结构。怎么理解？
3
• 线性表是一对一关系：每一对结点
中，前者只有一个直接后继，后者只 4
5
有一个直接前驱
• 树是一对多关系：每一对结点中，前者可能有多个直

图论讲义第4章-欧拉图与hamilton图

图论讲义第4章-欧拉图与hamilton图
[1] E. Lucas，Récréations Mathématiques IV, Paris, 1921.
Fleury 算法的步骤如下：
输入：欧拉图 G 输出：G 的欧拉闭迹。
step1. 任取 v0 ∈V (G) ，令 w0 := v0 ， i := 0 。 step2. 设迹 wi = v0e1v1 eivi 已取定。从 E \ {e1, e2 , , ei }中选取一条边 ei+1 ，使得 （1） ei+1 和 vi 相关联； （2） ei+1 不选 Gi = G \ {e1, e2 , , ei }的割边，除非没有别的选择。
个顶点都是偶度顶点。从而 G +e 有 Euler 闭迹。故 G 有 Euler 迹。证毕。
一个图 G 如果有一条欧拉迹或欧拉闭迹，则我们可以沿着欧拉迹或欧拉闭迹连续而不 重复地把 G 的边画完。因此存在欧拉迹或欧拉闭迹的图通常称为可一笔画的图，或者说它 可一笔画成。如果图 G 可分解为两条迹或闭迹的并，则 G 的边可用两笔不重复地画完。同 样地，如果图 G 可分解为 k 条迹或闭迹的并，则 G 可 k 笔画成。
获得 2k 个同类 u−v 迹。这种分类构成一个等价关系，因此形成了对有重复点的 u−v 迹集合
的划分。划分出的每一个等价类有偶数个条 u−v 路。这说明有重复点的 u−v 迹总共有偶数条。
有以上两方面知， G′ = G − e 中共有奇数条顶点不重复的 u−v 迹（即 u−v 路），因此，
G 中共有奇数个含有边 e 的圈。
step3. 当 step2 不能再执行时，停止。
定理 4.1.3 若 G 是 Euler 图，则 Fleury 算法终止时得到的是 G 的 Euler 闭迹。

数据结构第七章：图

数据结构第七章：图

例
a c G1
b d
vexdata firstarc adjvex next 1 4 ^ a 2 3 4 b c d 1 1 3 ^ ^ ^
19
7.3 图的遍历
深度优先遍历(DFS) 深度优先遍历
方法：从图的某一顶点 出发，访问此顶点； 方法：从图的某一顶点V0出发，访问此顶点；然后依 次从V 的未被访问的邻接点出发，深度优先遍历图， 次从 0的未被访问的邻接点出发，深度优先遍历图， 直至图中所有和V 相通的顶点都被访问到； 直至图中所有和 0相通的顶点都被访问到；若此时图 中尚有顶点未被访问， 中尚有顶点未被访问，则另选图中一个未被访问的顶 点作起点，重复上述过程， 点作起点，重复上述过程，直至图中所有顶点都被访 问为止。 问为止。
ω ij , 若(v i , v j )或 < v i , v j >∈ E(G) A[i, j ] = 0，其它
11
例
1 3
5
2
8 4 7 5 1 6 3 4 2
0 5 7 0 3
5 0 0 4 8
7 0 0 2 1
0 4 2 0 6
3 8 1 6 0
12
关联矩阵——表示顶点与边的关联关系的矩阵 表示顶点与边的关联关系的矩阵 关联矩阵
1
7.1 图的定义和术语
是由两个集合V(G)和E(G)组成的 组成的, 图(Graph)——图G是由两个集合 图 是由两个集合 和 组成的 记为G=(V,E) 记为
其中： 其中：V(G)是顶点的非空有限集 是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对 是边的有限集合， 是边的有限集合
有向图——有向图 是由两个集合 有向图G是由两个集合 有向图 有向图 是由两个集合V(G)和E(G)组成的 和 组成的

北京理工大学数据结构图课件

北京理工大学数据结构图课件
A
B C D
第 5 页
E
7.1 图的定义与术语
3、无向图——无向图G是由两个集合V(G)和 E(G)组成的。 其中：V(G)是顶点的非空有限集。 E(G)是边的有限集合，边是顶点的 无序对，记为 (v,w) 或 (w,v)，并且 (v,w)=(w,v)。
第 6 页
7.1 图的定义与术语

例如：
G2 = <V2,E2> V2 = { v0 ,v1,v2,v3,v4 } E2 = { (v0,v1), (v0,v3), (v1,v2), (v1,v4), (v2,v3), (v2,v4) }
V5
第 15 页
7.1 图的定义与术语
非 连 通 图
V0
V1
V2
V3
V0
V1 V3
V2
强连通分量
第 16 页
7.1 图的定义与术语
7、生成树
包含无向图 G 所有顶点的极小连通子图称为G生 成树。 极小连通子图意思是：该子图是G的连通子图， 在该子图中删除任何一条边，子图不再连通。
V0 V2 V3 V4 V3 连通图G1 V1 V0 V1 连通 所有顶点 V4 无回路
第 22 页
7.2 图的存储结构 3、有向图的逆邻接表 顶点：用一维数组存储（按编号顺序） 以同一顶点为终点的弧：用线性链表存储。
vexdata V0 V1 0 1 v0 v1 v2
v3
firstarc 3 0 0 ^ ^
V2
V3
2 3
^
^
2
章 类似于有向图的邻接表，所不同的是： 以同一顶点为终点弧：用线性链表存储
Boolean visited[MAX]; // 访问标志数组

第7章 图

第7章 图

假设一个连通图有 n 个顶点和 e 条边， 其中 n-1 条边和 n 个顶点构成一个极小 连通子图，称该极小连通子图为此连通图 的生成树 生成树。 生成树 B A F E C D 对非连通图，则 称由各个连通分 量的生成树的集 合为此非连通图 的生成森林 生成森林。 生成森林
基本操作
结构的建立和销毁 对顶点的访问操作 插入和删除顶点 插入和删除弧 对邻接点的操作 遍历
假若顶点v 和顶点w 之间存在一条边， 则称顶点v 和w 互为邻接点 邻接点， 邻接点
边(v,w) 和顶点v 和w 相关联 相关联。 和顶点v相关联的边的数目 边的数目定义为顶点v的度， 边的数目 度 记为TD（v）。 记为TD（ TD
B A F
C D E
例如: 例如: 右侧图中 TD(B) = 3 TD(A) = 2
个顶点相同的路径。
若图G中任意两个顶 点之间都有路径相通， 则称此图为连通图 连通图; A 连通图 B A F E C D
B
C D
F
E
若无向图为非连通图， 则图中各个极大连通 子图称作此图的连通 连通 分量。 分量
若任意两个顶点之间都存在 对有向图， 对有向图， 一条有向路径，则称此有向图为强连通图 强连通图。 强连通图 否则，其各个强连通子图称作它的 强连通分量。 强连通分量 A B C F E B C F A E
// 点”。若 w 是 v 的最后一个邻接点，则 // 返回“空”。
插入和删除顶点
InsertVex(&G, v); //在图G中增添新顶点v。 DeleteVex(&G, v); // 删除G中顶点v及其相关的弧。
插入和删除弧
InsertArc(&G, v, w); // 在G中增添弧<v,w>，若G是无向的， //则还增添对称弧<w,v>。 DeleteArc(&G, v, w); //在G中删除弧<v,w>，若G是无向的， //则还删除对称弧<w,v>。

图的定义和术语(4)

图的定义和术语(4)

连 通 图 强 连 通 图
2021/8/17
V0
V1
V2
V3
V4
V0
V1
V2
V3
V0
V1 V4
非 连
通
图
V3
V2 V5
V0
V1
非
强
连
通
V2
V3
图
7.权 某些图的边具有与它相关的数, 称之为权。这种带权 图叫做网络。
8.子图 设有两个图G=（V，{E}）、G1=（V1，{E1}），若 V1 V，E1 E，则称 G1是G的子图。 例:(b)、(c) 是 (a) 的子图
2021/8/17
基本术语：
1.有向图与无向图
在有向图中，顶点对<v, w>是有序的。在无向图中，顶 点对(x, y)是无序的。有向边又可称为弧, <vi,vj>中vi称 为弧尾或初始点，vj称为弧头或终端点。
1
1
3
2
4
3
2
654
5
6
7
无向图
V={1,2,3,4,5,6,7}
VR={(1,3),(3,4),(4,5),(1,2),(2, 6),(2,7),(6,7),(5,6),(1,5),(1,7) } 2021/8/17
adjvex nextarc 4^
3
5^
4
5^
3
^
3^
逆邻接表：有向图中对每个结点建立以Vi为弧头的弧的单链表。
例： a b
cd G1
vexdata firstarc adjvex nextarc
1
a
4^
2
b
1
^
3

图论


8/4/2013 11:54 PM
Zhibo Lu
3
图论方法建模
[定义]顶点： Ｖ中的元素称为顶点，用带标记的点表示，也 称为结点/Vertices。 [定义]边： 在有向图G中,若e=(a，b)∈E，e称为G的有向边 /directed edge。用由a到b带箭头的线把a和b连起 来； 在无向图G中,若e=(a,b)∈E，e称为G的无向边 /undirected edge 。a、ｂ间用连线连结； 有向边和无向边统称为G的边/edge。
8/4/2013 11:54 PM Zhibo Lu 22
图论方法建模
说明： 图Ｃ不是Ｅ的补图。（不互为补图） 因为：
Ｅ”＝Ｅ－Ｅ’ ＝ {[b,c],[b,d],[b,e], [c,d],[c,e],[d,e]}
Ｖ”＝{b,c,d,e} 而图C多了顶点a。
8/4/2013 11:54 PM Zhibo Lu 23
v5
v4 (b)
Zhibo Lu
v5
v4 (c)
v5
17
图论方法建模
[定义]补图/complementary graph ： Ｇ＝(V,E)是图，Ｇ’＝(V’,E’)是Ｇ 的子图，Ｅ”＝Ｅ－Ｅ’，Ｖ”＝V－V’或 是Ｅ”中边所关联的所有顶点集合，则Ｇ” ＝(Ｖ”,Ｅ”)称为Ｇ’关于Ｇ的相对补图。 [定义]绝对补图：
8/4/2013 11:54 PM Zhibo Lu
v1
v2 e2 e6 e3 v3
12
e4
图论方法建模
[定理 (Handshaking)] 设无向图G=(V,E) 有e条边，则G中所有顶点的次之和等于e的 两倍。 证明思路：利用数学归纳法。 [定理] 无向图中次为奇数的顶点个数恰 有偶数个。 证明思路：将图中顶点的次分类，再利用 定理1。

第5章 图结构分析

2018年10月14日
5.1 引言
5.1.1 问题的提出
第 3页
问题1：寻求走迷宫问题的解，迷宫可表示成图，求解即 为寻求满足某种要求的从迷宫的入口结点到迷宫的出口 结点的路径。 问题2：从公园入口处寻找一条参观某个动物的最短路径。 问题3：在几个村落之间铺设通讯线路，如何铺设最省钱。 问题4：计算机科学与技术专业的大学生，本科四年需要 学习公共基础课、专业基础课、专业课几十门，每门课 程都可能有先修课程的要求，如何合理安排课程的教学 顺序，使学生能够顺利完成学业。 。。。。。。
v1
v2
v3
v4
2018年10月14日
第6页
(3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) (14)
邻接点、邻接边 完全图 稠密图、稀疏图 顶点的度、入度、出度 边的权、网图 路径和路径长度 回路、简单路径、简单回路 子图 连通的、连通图、连通分量 强连通图、强连通分量 连通图（或子图）的生成树 非连通图的生成森林
2018年10月14日
5.2 图的存储方法
5.2.1 邻接矩阵 1.邻接矩阵的存储思想
(1) 图中顶点顺序存储；
第 9页
(2) 用一个n*n矩阵（设图有n个顶点）来存储任意两个 顶点之间边的信息，也就是各顶点之间的邻接关系。
A[i][j]=
{0 若(v ,v )或<v ,v >不是E(G)中的边
i j i j
1 若(vi,vj)或<vi,vj>是E(G)中的边
若G是带权图，则邻接矩阵可定义为：
A[i][j]=
{ 0或∞ 若(v ,v )或<v ,v >不是E(G)中的边
i j i j

图论 第1章 图的基本概念


G
G[{e1 , e4 , e5 , e6 }]
G − {e5 , e7 }
G + {e8 }
图G1，G2的关系
设 G1 ⊆ G, G2 ⊆ G. 若 V (G1 ) V (G2 ) = φ x-disjoint） 若 E (G1 ) E (G2 ) = φ ,则称G1和G2是边不交的 （edge-disjoint） G1和G2的并, G1 G2 其中 V (G1 G2 ) = V (G1 ) V (G2 )
连通性
设 u, v 是图G的两个顶点，若G中存在一条 (u, v)
≡ v表示顶点 u 和v是连通的。 如果图G中每对不同的顶点 u , v都有一条 (u , v)
以 u
道路，则称顶点 u和 v是连通的(connected)。
道路，则称图G是连通的。
连通图
连通图
图G的每个连通子图称为G的连通分支，简
证明：G中含奇数个 1 (n − 1) 度点。 2 | Vo | 为 证明 V (G ) = Vo Ve 由推论1.3.2知， 偶数。因为 n ≡ 1(mod 4) ，所以n为奇数个。 因此，| Ve | 为奇数个。 n ≡ 1(mod 4) ， 1 2 ( n − 1) 为偶数。 1 1 d ( x ) = n − 1 − d ( x ) ≠ (n − 1) 设 x ∈Ve。若 d ( x) ≠ 2 (n − 1)，则 且 2 为偶数。由 G ≅ G c ，存在y，使得 d ( y) = d ( x) 为偶数。即 y ∈Ve 且 d ( y) ≠ 1 (n − 1) 。Ve 中度不为 2 1 (n − 1) 的点是成对的出现的。 2
G
G[{v1 , v2 , v3 }]

_公差原则_标准的分析及应用_最大实体要求

表 1 术语及定义术语名称 符号 定 义 图例 ( 以孔为例)实际要素的任意正截面上两对应点之间的距离, 孔用 D a 、轴用 d a 实际尺寸AIS 表示。

见图例( b ) 中的 D 和图 1 ( b ) 、 ( c ) 中的 d 。

!0 . 03 &a a实际要素在给长度上处于 MMS ( D M 、d M ) 时, 且中心 要 素 的 形0 最 大 实 体 0 0实效状态MMV C 位误差等于形位公差值的综合极限状态。

0 30 . !实际要素在 MMV C 下的体外作用尺寸, 孔用 D M V 、轴用 d M V 表示。

( a ) 图样标注 ) 最 大 实 体即:D M V =D M - t 形位 ; d M V =d M +t 形位 。

见图例 ( b ) 中的 D M V 和图 1 ( b )D)实效尺寸 M MV S中的 d 。

M M BM M VB ( 7t (9 3 M V0 9 . .0 2 ! !)D具有理想形状且边界尺寸为 MMV S 的包容面 ( 极限圆柱面或两平D( 最 大 实 体 行平面) , 该包容面既包括内表面 ( 孔) , 也包括外表面 ( 轴) , 见图 3 0 实效边界 MMV B例 ( b ) 中的 MMV B 为内表面和图 1 ( b ) 、 ( c ) 的 M MV B 为外表面。

!( b ) D M V 与 D M 、t 形位 的关 系 《公差原则》标准的分析及应用 ——最大实体要求刘嵬嵬 李 莉 周 海 张也晗( 哈尔滨工业大学, 哈尔滨, 150001 )文 摘: 根据 《形状和位置公差》标准中的公差原则和公差要求规定及工程中的实际需要, 对最大实体要求的概念、图样标注方法以及它们在工程中的应用范围进行较详细地论述。

关键词: 形位公差; 公差原则; 最大实体要求; 分析与应用。

《航 天 标 准 化 》 在 2006 年 第 4 期 上 刊 登 了 最大实体要求适用于中心要素, 是指在设计 “《公差原则》标准的分析及应用”一文中, 差原则中的独立原则和包容要求作了介绍, 对公本文的 概时 用 最 大 实 体 实 效 边 界 ( MMVB ) 来 控 制 被 测 要 素的实际尺寸和形位误差的综合结果。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
❖ 基本操作的实现——构造图
输入：边<a,b> 输出：邻接矩阵表示 算法：①初始化邻接矩阵为0；
②输入一条边<a,b>； ③令顶点a的序号为i,设顶点b的序号为j; ④邻接矩阵的元素[i][j]=1；
重复②--④步，直到输入全部的边
数据结构与算法
7.2 图的存储结构
❖ 邻接表
用数组存储所有结点 每个顶点采用一链表存储对应的所有邻接点
网络连接图例
数据结构与算法
7.1 图的定义和术语
❖ 图是由顶点集合V及顶点间的关系集合E组成 的一种数据结构：
Graph＝( V, E )
任意一对顶点间都可以有关系； 图是最基本的数据结构，树和线性表可看作受限图。
245
1
3
6
G1
数据结构与算法
7.1 图的定义和术语
❖ 有向图与无向图
在有向图中，顶点对<x, y>是有序的。在无向 图中，顶点对(x, y)是无序的。
数据结构与算法
7.2.2 图的邻接表
❖ 在有向图的邻接表中易于计算顶点的出度； ❖ 计算顶点的入度，可采用逆连接表
数据结构与算法
7.2.2 图的邻接表
❖ 网络（带权图）的邻接表
数据结构与算法
7.3 图的遍历
❖ 从图中某一顶点出发访遍图中其余顶点，且 使每一个顶点仅被访问一次。这一过程就叫 做图的遍历。
W (i, j), 如果 i ! j 且 < i, j E 或 (i, j) E
A.Edge
[i][
j]
=
,
否则,但是 i != j
0, 对角线 i == j
数据结构与算法
7.2.1 图数组表示法
❖ 在有向图中, 统计第 i 行 1 的个数可得顶点 i 的 出度，统计第 j 行 1 的个数可得顶点 j 的入度。
245
1
3
6
数据结构与算法
7.2 图的存储结构
❖ 图的数组（邻接矩阵）存储表示
用一个矩阵表示图结构
A[i,
j]
1,若(vi , v 0，其它
j )或
vi ,
v
j E(G)
例1
2
0 1 1 0
0
0
0
0
3
4
G1
0 0 0 1 1 0 0 0
数据结构与算法
7.2.1 图数组表示法
❖ 网络的邻接矩阵
第7章 图
目录
❖ 图的定义和术语 ❖ 图的存储结构 ❖ 图的遍历 ❖ 图的连通性问题 ❖ 有向无环图及其应用 ❖ 最短路径
245
1
3
6
G1
数据结构与算法
7.1 图的定义和术语
❖ 图被广泛地用于模拟真实事件或抽象问题。 在语言学、逻辑学、物理、化学、电讯工程、 计算机、数学等学科领域得到了广泛的应用。
例 245
例 1
57
1
3
G1
6
32 4 6
G2
数据结构与算法
7.1 图的定义和术语
❖ 完全图
若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此图为完全无向图。有 n 个顶点的有向图有n(n1) 条边, 则此图为完全有向图。
2
2
1
3
有向完全图
1
3
无向完全图
数据结构与算法
7.1 图的定义和术语
❖ 在无向图中, 统计1 的个数可得边的个数的两倍。
数据结构与算法
7.2.1 图数组表示法
❖ 无向图的邻接矩阵是对称矩阵
数据结构与算法
7.2.1 图数组表示法
❖ 邻接矩阵存储结构
#define INF INT_MAX //最大值∞ #define MAX_VER_NUM 20 //顶点个数 typedef struct {
DestroyGraph(&G); // 销毁图G。 2 4 5 LocateVex(G, u); // 查找顶点u
GetVex(G, v);
// 返回v的值。 1
3
6
PutVex(&G, v, value); // 对v赋值value。
FirstAdjVex(G, v); // 返回v的第一个邻接点
❖ 回路 若路径上第一个顶点 v1 与最后一个顶点vm
重合, 则称这样的路径为回路或环。
数据结构与算法
7.1 图的定义和术语
➢连通图 图中任意两个顶点都有路径
➢强连通图 在有向图中, 每一对顶点vi和vj, 都存
在一条从vi到vj和从vj到vi的路径
例 245
例
5
1
3
6
连通图
3
6
强连通图
数据结构与算法
7.1 图的定义和术语
➢连通分量 非连通图的极大连通子图
数据结构与算法
7.1 图的定义和术语
❖ 生成树 一个连通图的生成树是它的极小连通子
图，在n个顶点的情形下，有n-1条边。但有向图则
可能得到它的由若干有向树组成的生成森林。
数据结构与算法

CreateGraph(&G,V,VR); // 按V和VR的定义构造图G。
ElemType vexs[MAX_VER_NUM]; //顶点向量 int arcs[MAX_VER_NUM][MAX_VER_NUM] ;//邻接矩阵 int vexnum, arcnum; //图的顶点数和边数 int kind; //图的种类 }MGraph;
数据结构与算法
7.2.1 图数组表示法
数据结构与算法
7.1 图的定义和术语
❖ 子图 设有两个图 G＝(V, E) 和 G‘＝(V’, E‘)。
若 V’ V 且 E‘E, 则称 图G’ 是 图G 的子图。
数据结构与算法
7.1 图的定义和术语
❖ 简单路径 若路径上各顶点 v1,v2,...,vm 均不互
相重复, 则称这样的路径为简单路径。
❖ 邻接顶点 如果 (u, v) 是 E(G) 中的一条边，
则称 u 与 v 互为邻接顶点。
❖ 顶点 v 的入度 是以 v 为终点的有向边的条数
❖ 顶点 v 的出度 是以 v 为始点的有向边的条数,
245
1
3
6
数据结构与算法
7.1 图的定义和术语
❖ 权 某些图的边具有与它相关的数, 称之为权。这
种带权图叫做网络。
NextAdjVex(G, v, w); //返回v的下一个邻接点。
数据结构与算法
7.1 图的定义和术语
❖ 图的基本操作(续）
InsertVex(&G, v); // 在图G中增添新顶点v。 DeleteVex(&G, v); // 删除G中顶点v及其相关的弧。 InsertArc(&G, v, w); // 在G中增添弧<v,w>， DeleteArc(&G, v, w); //在G中删除弧<v,w>， DFSTraverse(G, v, Visit()); // 从顶点v起深度优先遍历图 BFSTraverse(G, v, Visit()); // 从顶点v起广度优先遍历图