离散数学-图论共89页

提示：反证法。
设有两个连通分支，这两个分支至多是完 全图。由此得到图中点与边之间的数量关系。
§8.3欧拉图

欧拉图产生的背景就是前面的七桥问题。

定义：图G的回路，若它通过G中的每条边一 次，这样的回路称为欧拉回路。具有欧拉回 路的图称为欧拉图。
定义欧拉通路：通过图G中每条边一次的通 路（非回路）称为欧拉通路。


基本通路：通路中没有重复的点。
简单回路和基本回路。

基本通路一定是简单通路，但反之简单通路 不一定是基本通路。基本回路必是简单回路。

定理：一个有向（n,m）图中任何基本通路长 度≤n-1。任何基本回路的长度≤n。 任一通路中如果删去所有回路，必得基本通 路。 任一回路中如删去其中间的所有回路，必得 基本回路。

例1：教材121页。
结点次数

引出次数：有向图中以结点v为起点的边的条数称为 v的引出次数，记 deg(v) 引入次数：有向图中以结点v为终点的边的条数称为 v的引出次数，记 deg(v)


结点次数：有向图中引出次数和引入次数之和称为 结点次数；无向图中与结点v相关联的边的条数称为 V的次数。统一为记deg(v)。
图论的发展

图论的产生和发展经历了二百多年的历史， 从1736年到19世纪中叶是图论发展的第一阶 段。 第二阶段大体是从19世纪中叶到1936年，主 要研究一些游戏问题：迷宫问题、博弈问题、 棋盘上马的行走线路问题。


一些图论中的著名问题如四色问题(1852年)和哈密 尔顿环游世界问题(1856年)也大量出现。同时出现 了以图为工具去解决其它领域中一些问题的成果。

有向连通图

(3)G1与G2的差,定义为图G3＝〈V3,E3〉,记为G3=G1-G2。 其中E3=E1-E2,V3=(V1-V2)∪{E3中边所关联的顶点}。 (4)G1与G2的环和,定义为图G3＝〈V3,E3〉,
G3=(G1∪G2)-(G1∩G2),记为G3=G1 G2。
除以上4种运算外,还有以下两种操作:
E={e1,e2}={(v1,v2),(ห้องสมุดไป่ตู้2,v3)};
f(v1)=5,f(v2)=8,f(v3)=11;
g(e1)=4.6,g(e2)=7.5
8.1.2 结点的次数
定义8.1―4在有向图中,对于任何结点v,以v为始点的 边的条数称为结点v的引出次数(或出度),记为deg+(v); 以v为终点的边的条数称为结点v的引入次数(或入度), 记为deg-(v);结点v的引出次数和引入次数之和称为 结点v的次数(或度数),记作deg(v)。在无向图中,结点 v的次数是与结点v相关联的边的条数,也记为deg(v)。
i 1
i 1
定理8.1―2在图中,次数为奇数的结点必为偶数个。
证 设次数为偶数的结点有n1个,记为(i=1,2,…,n1)。 次数为奇数的结点有n2个,记为(i=1,2,…,n2)。
由上一定理得
n
n1
n2
2m deg(i ) deg(Ei ) deg(Oi )
i 1
i 1
i 1
因为次数为偶数的各结点次数之和为偶数。所以
孤立结点的次数为零。
定理8.1―1 设G是一个(n,m)图,它的结点集合为
V={v1,v2,…,vn},则 n
deg(i ) 2m
i 1
证 因为每一条边提供两个次数,而所有各结点次数
之和为m条边所提供,所以上式成立。

第19页/共93页
• 完全图：一个（n,m）图G，其n个结点中每个结点均与其它n-1个结点相邻接，记为Kn。 • 无向完全图：m=n(n-1)/2 • 有向完全图：m=n(n-1) • 举例说明以上几种图。
第20页/共93页
定义补图
• 设图G=<V,E> ， G’=<V,E’> ，若G’’=<V,E∪E’> 是完全图，且E∩E’= 空集，则称G’是G的补图。 • 事实上，G与G’互为补图。
正则图
• 所有结点均有相同次数d的图称为d次正则图。 • 如4阶的完全图是3次正则图，是对角线相连的四边形。 • 试画出两个2次正则图。
第27页/共93页
两图同构需满足的条件
• 若两个图同构，必须满足下列条件： （1）结点个数相同 （2）边数相同 （3）次数相同的结点个数相同
• 例子
第28页/共93页
• 图是人们日常生活中常见的一种信息载体，其突出的特点是直观、形象。图论，顾 名思义是运用数学手段研究图的性质的理论，但这里的图不是平面坐标系中的函数， 而是由一些点和连接这些点的线组成的结构 。
第8页/共93页
• 在图形中，只关心点与点之间是否有连线，而不关心点具体代表哪些对象，也不关 心连线的长短曲直，这就是图的概念。
定义图的子图
• 子图：设G=<V,E> ， G’=<V’,E’> ，若V’是V的子集， E’是E的子集，则 G’是G的子图。 • 真子图：若V’是V的子集，E’是E的真子集。 • 生成子图：V’=V，E’是E的子集。 • 举例说明一个图的子图。
第18页/共93页
定义（n,m）图
• (n,m)图：由n个结点，m条边组成的图。 • 零图：m=0。即（n,0）图，有n个孤立点。 • 平凡图：n=1,m=0。即只有一个孤立点。

最短路径问题
实现方法：使用 队列数据结构， 将起始节点入队， 然后依次处理队 列中的每个节点， 直到找到目标节
点或队列为空
Dijkstra算法和Prim算法
Dijkstra算法：用于 求解单源最短路径问 题，通过不断更新最 短路径来寻找最短路 径。
Prim算法：用于求解 最小生成树问题，通过 不断寻找最小权重的边 来构建最小生成树。
图的矩阵表示
邻接矩阵的定义和性质
定义：邻接矩阵是一个n*n的矩阵，其 中n是图的顶点数，矩阵中的元素表示 图中顶点之间的连接关系。
性质：邻接矩阵中的元素只有0和1， 其中0表示两个顶点之间没有边相连， 1表示两个顶点之间有一条边相连。
应用：邻接矩阵可以用于表示图的连通 性、路径长度等信息，是图论中常用的 表示方法之一。
图像处理：优化图像分割， 提高图像质量
物流配送：优化配送路径， 降低配送成本
社交网络：优化社交网络 结构，提高用户活跃度
感谢您的观看
汇报人：PPT
数学：用于图论、组合数 学、代数拓扑等领域
物理学：用于量子力学、 统计力学等领域
生物学：用于蛋白质结构、 基因调控等领域
社会科学：用于社会网络 分析、经济模型等领域
图的基本概念
图的定义和表示方法
图的定义：由节点和边组成的数学结构，节点表示对象，边表示对象之间的关系
节点表示方法：用点或圆圈表示 边表示方法：用线或弧线表示 图的表示方法：可以用邻接矩阵、邻接表、关联矩阵等方式表示
顶点和边的基本概念
顶点：图中的基本元素，表示一个对象或事件 边：连接两个顶点的线，表示两个对象或事件之间的关系 度：一个顶点的度是指与其相连的边的数量 路径：从一个顶点到另一个顶点的边的序列 连通图：图中任意两个顶点之间都存在路径 强连通图：图中任意两个顶点之间都存在双向路径

结点的次数
2020/1/17
问题1：是否存在这种情况：25个人中，由于意见不同，每 个人恰好与其他5个人意见一致？
在建立一个图模型时，一个基本问题是决定这个图是什么 —— 什么是结点？什么是边？ 在这个问题里，我们用结点表示对象——人； 边通常表示两个结点间的关系——表示2个人意见一致。 也就是说，意见一致的2个人（结点）间存在一条边。
第七章 图论基础
Graphs
第一节 图的基本概念
2020/1/17
一个图G定义为一个三元组：G=<V, E, Φ>
V —— 非空有限集合，V中的元素称为结点 (node)或 顶点(vertex)
E —— 有限集合（可以为空），E中的元素称为边(edge)
Φ —— 从E到V的有序对或无序对的关联映射
以v为起始结点的弧的条数，称为出度(out-degree) （引出次数），记为d+(v)
以v为终结点的弧的条数，称为入度(in-degree)
（引入次数），记为d-(v)
v3
v的出度和入度的和，称为v的度数(degree)
（次数），记为d(v) = d+(v) + d-(v)
v1 (a) v2
结点的次数
(associative mapping)
v3
v3
v3
v1 (a) v2
v1
v2
(b)
v1
v2
(c)
图的基本概念
2020/1/17
图G=<V, E, Φ>中的每条边都与图中的无序对或有序对联系
若边e E 与无序对结点[va, vb]相联系，即Φ(e)= [va, vb] （va, vb V）则称e是无向边（或边、棱）

j 1
j 1
nm
③
mij
i1 j 1

2m
,即所有元素之和等于边数的2倍;
④平行边的列的元素完全对应相同.
2．(无向图)相邻矩阵
设G＝<V，E>, V n, E m
A(G)= aij n
其中aij=vi与vj相关联的边的条数(行、列均为结点).
具有性质:
① A(G)是对称矩阵；
设D=<V,E>, V n, E m
A(D)= aij n
其中aij=邻接vi与vj的边的条数 (与A(G)类似) ( 以行和列均为结点)
nm
具有性质： aij m i1 j1
5．(有向图)可达矩阵 设D=<V,E>，V n, E m
P(D)= pij n
（2）欧拉图或通路的判定 1) 无向连通图G是欧拉图G不含奇数度结点(G的
所有结点度数为偶数):(定理1) 2) 非平凡连通图G含有欧拉通路G最多有两个奇
数度的结点；(定理1的推论) 3) 连通有向图D含有有向欧拉回路(即欧拉图)D
中每个结点的入度＝出度
4）连通有向图D含有有向欧拉通路D中除两个结 点外，其余每个结点的入度＝出度，
二、图的矩阵表示、欧拉图
1．（无向图)关联矩阵
设G=<V,E>, V n, E m M(G)= mij nm
其中mij=vi与ej的关联次数(行为结点，列为边). 具有性质：
m
① mij 2(列元素之和为2)；
i 1
m
② mij deg(v,i若)
m mij ,0表明vi是孤立点;
且此两点满足deg－(u)－deg＋(v)＝1. (定理2)

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
即所有顶点度数之和等于边数的两倍。
推论
在任何无向图中，奇数度的顶点数必是偶 数。

C
A
B
D 图2
此图实际上是反 映了客观事物 之间的相互关系
10
离散数学
本世纪40年代，一个数学游戏也使用类似的方法得到 了解决：某人挑一担菜、并带一只狗、一只羊，要从河 的北岸到南岸。由于船小，只允许带狗、羊、菜三者中 的一种过河；而由于明显的原因，当人不在场时狗与羊、 羊与菜不能呆在一起。问此人应采取怎样的办法才能将 这三样东西安全地带过河去？ 方法一：不对称状态空间法 将人(person)、狗(dog)、羊(sheep)、菜(cabbage)中任意 几种在一起的情况看作是一种状态，则北岸可能出现的 状态共有十六种，其中 安全状态有下面十种： (人，狗，羊，菜)，(空)； (P,D,S,C) ，() ； (人，狗，羊)， (菜)； (P,D,S,) ，(C) ； (人，狗，菜)，(羊)； (P,D,C) ，(S) ；
7
离散数学
但当地的居民和游人做了不少的尝试，却都没有取得成 功。于是，有好事者便向当时居住在该城的大数学家欧 拉请教。 1736年，瑞士的数学家L.Euler解决了这个问题。他将 四块陆地表示成四个结点，凡陆地间有桥相连的，便在 两点间连一条线，这样图1就转化为图2了。此时，哥尼 斯堡七桥问题归结为：在图2 所示的图中，从 A, B, C, D 任一点出发，通过每条边一次且仅一次而返回出发点 的回路是否存在？后人称如此的问题为Euler环游。 欧拉断言这样的回路是不存在的。理由是：从图2中 的任一结点出发，为了要回到原来的出发点，要求与每 个结点相关联的边数均为偶数。这样才能保证从一条边 进入某结点后，可从另一条边出去，而不经过已走过的
v3
1 2
v1
1 1 1
v4 v2
2 1
图论的基本概念性术语和一些特殊图： 图3 (1)(n,m)图: |V| = n,|E| = m，即有n个结点和m条边的图称 为 ( n, m ) 图。 (2)无向边：(undirected edges简edges)在定义3下，若边 (u, , v)与边(v, ,u)表示同一条边，则称此边为无 向边。 22

二分图
二分图是指一个图中的所有顶点可 以被分成两个不相交的集合，即两 个集合内的点之间没有边。
树
树是一种特殊的无向图，他是一个 无环连通图。
图的表示
1
邻接矩阵
邻接矩阵是表示图的最直观的一种方法，它将图中的每个点与其他点之间的连接 关系用一个矩阵来表示。
2
邻接表
邻接表是图中比较常见的一种数据结构，用于存储有向图或无向图中顶点的邻接 关系。
Kruskal算法是一种贪心算
2 自反闭包
3 反对称闭包
在一个有向图中，如果由顶 点i到顶点j有路径，由顶点j 到顶点k有路径，则从i到k也 有路径。这种情况称为传递 闭包。
在一个有向图中，如果自己 只能到自己，则称之为自反 闭包。
在一个有向图中，如果存在 有向边从i到j，同时存在一 个从j到i的反向边，则称之 为反对称闭包。
3
关联矩阵
关联矩阵是一个图矩阵，它将图中的所有点和边都表示为元素，可以将和特定边 相关的点和总结点联系起来。
图的遍历
1 深度优先遍历
深度优先遍历是从图中的起始点开始，递归地访问所有可达的顶点。它通常用堆栈来实 现。
2 广度优先遍历
广度优先遍历是从图中的起始点开始访问每一层可达的顶点。它通常用队列来实现。
最短路径
Dijkstra算法
Dijkstra算法是一种用来求图中单个源点到其他所有点 的最短路径的平均算法。
Floyd算法
Floyd算法是一种用于发现非负权重图中所有点对之间 的最短路径的算法。
最小生成树
1
Prim算法
Prim算法用于寻找加权无向连通图的最小生
Kruskal算法
2
成树，该树包含了关键点并且保证了所有点 都连通。

2012-2-3
v1
e1 e3 e4
v3 e5
v2
离散数学
5
关于图的术语
图G的阶：G的顶点数，称为G的阶。 若 |V(G)|=n，则称G为n阶图 G(p,q) 表示有p个顶点，q条边的图。 用p(G)和q(G)分别表示图G的顶点数和边 数。 如果图G的V(G)和E(G)都是有限集，称G 为有限图，否则称为无限图。
2012-2-3 离散数学 21
§5.4 子图及图的运算
定义5.4.1：设G和H是两个图，如果 V(H)⊆V(G)且E(H)⊆E(G)，则称H是G的子 图。记为H≤G。 如果H≤G，而H≠G，则称H是G的真子图。 记为H<G。 如果H≤G，且V(H) = V(G)，则称H是G的 生成子图。 即包含了全部顶点的子图。
2012-2-3 离散数学 3
关于点与边的术语
端点：在图G中,若e∈E(G)，ϕ(e) = uv, u,v∈V(G)， 则称u,v为e的端点。 邻接(点)：若e∈E(G)，ϕ(e) = uv，则称u,v两点是邻 接的，也称边e与u,v 两点关联。 (一条边的两个端点。) 邻接(边)： 若ϕ(e1) = uv,ϕ(e2) = vw,则称e1与e2邻接. 即两条不同的边关联同一个点。 (有共同端点的两条边) 环： 若ϕ(e) = uu,则称e为环。即一条边的两个端点 重合。 杆：若ϕ(e) = uv,u≠v,则称e为杆。即 一条边的两个端 点不重合。 孤立点：不与任何边关联的点。
2012-2-3 离散数学 22
子图的例子
下面各图：G为母图，H1和 H2为G的真子图。
v1 e1 e6 v3 e4 e 2 v4 e5 e3 v2 e1 v3 e3 v1 e2 v2 v4 e6 v3 v2 v3 e1 v1 e4 e2 v4 e3 v2

一 、图的基本概念
• 邻接和关联 • 无向图和有向图 • 零图和平凡图 • 简单图 • 完全图（无向完全图和有向完全图） • 有环图
一 、图的基本概念
• 有限图和无限图 设图G为< V，E，Ψ>
（l）当V和E为有限集时，称G为有限图，否则称G为无限图。 （2）当ΨG为单射时，称G为单图；当ΨG为非单射时，称G为重图，又称满足
二、生成树
1、生成树定义：
若无向图的一个生成子图T是树，则称T 为G的生 成树，T中的边称为树枝，E（G）-E（T）称为树T 的补，其中的每一边称为树T 的弦。
在任何图中，结点v的度（degree）d(v)是v所关联边的数目。
第三节 生成树、最短路径和关键路径 由结点a和它所有的后代导的子图，称为T的子树.
∴ T连通且具有m=n-1的图
{e5,e4,e8} ， {e7，e6，e5，e2，e4} 第四节 欧拉图和哈密顿图
第四节 特殊图（欧拉图和哈密顿图等）
第五节 树、二叉树和哈夫曼树
离散数学教学图论
（优选 欧拉图和哈密顿图
(3)2=>3 ∴W(T)≤W(T1) ∴W(ei+1)≥W(f) 二. 哈密顿图的由来—周游世界问题：
第二节 图的矩阵表示 第四节 欧拉图和哈密顿图
证明：若G中一个边割集和一生成 树无公共边，则表示该边割集所分离的结点不在生成树中，这导致与生成树的定义矛盾。 哈密顿图的由来—周游世界问题： c)对新图向下旋转45度。 ei之后将取f而不是ei+1
为该顶点的度,列之和一定为2. • 有向图的关联矩阵 ----- 以节点数为行,边数为列.节点与边无关系,为0,有关系,则起点为1,
终点为-1;列之和一定为0,每行绝对值之和等于该节点的度数;其 中1的个数为该节点的出度,-1的个数为对应节点的入度;所有元 素的和为0,1的个数等于-1的个数,都等于边数m.

否则称G为非连通图。
如图G1是非连通图， G2是连通图。
G1
G2
21
连通分支：设无向图G=<V, E>，V关于顶点之间的 连通关系 的商集 V/ ={V1,V2,…,Vk}，Vi为等价 类，称导出子图G[Vi] (i=1,2,…,k) 为G的连通分 支, 其个数记作p(G)=k。
如： p(G1)=2， p(G2)=1 G是连通图 p(G)=1 n阶零图的连通分支数最多， p(Nn)=n
有圈的长度2。
• 复杂通路和复杂回路： 中的边重复出现。
20
14.3 图的连通性
（23）无向图的连通性 设无向图G=<V, E>，u, vV， u与v连通：u与v之间存在通路. 记作uv. 规定uu。 连通关系： ={<u,v>| u,vV且uv}是等价关系。 连通图：平凡图, 任意两点都连通的图。
注意：图的数学定义与图形表示，在同构的意义 下是一一对应的。
7
（5）几个特殊的图
通常用G表示无向图, D表示有向图, 也常用G泛指 无向图和有向图, 用ek表示无向边或有向边. V(G), E(G) —表示图G的顶点集, 边集.
|V(G)|, |E(G)| —表示图G的顶点数集（阶）和边数.
n 阶图、有限图、零图、平凡图、空图、基图
（6）顶点和边的关联
关联、关联次数、环、孤立点
（7）相邻
vi
vj
点相邻、边相邻
(vi,vj)
ek el
8
（8）邻接
vi
邻接到、邻接于
（9）邻域和关联集
设无向图G, vV(G)
v的邻域、 v的闭邻域、 v的关联集
设有向图D, vV(D)
v的后继元集

1
2
3
(3)为(1)的生成子图，(2)为(1)的真子图。
补图
定义7 设图G=<V, E> ,若G是n阶无向图，则G的补图为： KnG。即为n阶完全无向图与G的差。若G是n阶有向图， 则G的补图为：n阶有向完全图与G的差。
（这一节介绍了图的一些基本概念，如图的定义，图 中顶点的度，图的所有顶点的度为边的2倍，且一个 图中有偶数个奇顶点，简单图等的定义，图的运算， 子图，补图的一些概念。要掌握这些简单的定义）
e3
d e2
d 1 1 1 0 0
c
e

0
0
0
0
0
有向图的矩阵表示
与无向图相对应，有向图也有类似的矩阵表示。 如右图：
称e关联于顶点a和b；称a和b是邻接的。 若边e对应的是无序偶{a,b},则称e为无向边。同样
称a,b是端点，称e关联于顶点a和b；称a和b是邻接 的。 每一条边都是有向边的图，称为有向图。每条边都 是无向边的图，称为无向图。
图中不与任何顶点邻接的点称为 孤立点。全都是孤 立点的图称为零图。关联于一个顶点的边称为自回路， 也称为自圈。
哥尼斯堡七桥问题
城的四个陆地部分分别表以A，B（大岛），C，D（小岛)， 将陆地设想为图的顶点，把桥画成相应的边，
A
B
D
C
则问题等价于在图中从某一顶点出发找一条回径，通过它的每条 边一次且仅一次，并回到原顶点。
（你能否看出，此问题无解，即这样的走法不存在呢？）
主要内容
1.图的基本概念 2.路径与回路 3.图的矩阵表示 4.几种特殊的图 5.无向树, 有向树
定义5 在有向图G中，如果在任两个顶点中，存在从一个顶点到 另一个顶点的路径，则称图G为单向连通的。如果在G中，任 何两个顶点都互相可达，则称G为强连通的。如果它的基础图 （底图）是连通的，则称之为弱连通的。

第六章 图论基础图是建立和处理离散数学模型的一种重要工具。

图论是一门应用性很强的学科。

许多学科，诸如运筹学、网络理论、控制论、化学、生物学、物理学、社会科学、计算机科学等，凡是研究事物之间关系的实际问题或理论问题，都可以建立图论模型来解决。

随着计算机科学的发展，图论的应用也越来越广泛，同时图论也得到了充分的发展。

这里将主要介绍与计算机科学关系密切的图论的内容。

6.1 图的基本概念我们已知集合的笛卡尔积的概念，为了定义无向图，还需要给出集合的无序积的概念。

任意两个元素a ,b 构成的无序对（Unordered pair ）记作(a ,b )，这里总有),(),(a b b a =。

设B A ,为两个集合，无序对的集合}),{(B b A a b a ∈∧∈称为集合A 与B 的无序积（Unordered Product ），记作B A &。

无序积与有序积的不同在于A B B A &&=。

例如，设=A {}b a ,，{}2,1,0=B ，则)}2,(),1,(),0,(),2,a (),1,(),0,{(&b b b a a B A = A B &=,)},(),,(),,{(&b b b a a a A A =。

为了引出图的定义，我们先介绍如下的例子。

例 6.1-1 (1) 北京、上海、香港、澳门是中国的几个著名的城市，分别用字母表示为M H S B ,,,,城市的集合为{}M H S B V ,,,=，这些城市间现有的航空线的集合是{}),(),,(),,(),,(),,(M S H S M B H B S B E =。

我们也可以将这些城市间的航空线关系用图6.1-1来表示。

⑵∑=101i i 的程序框图如图6.1-2图6.1-1图6.1-26.1.1 图的定义及相关概念定义 6.1-1 一个无向图(Undirected Graph)G 是一个有序二元组><E V ,，记作>=<E V G ,，其中V 是一个非空集合，V 中的元素称为结点或顶点（Vertex ）；E 是无序积V V &的多重子集（元素可重复出现的集合），称E 为G 的边集(Edge Set)，E 中的元素称为无向边或简称边(Edge)。

XDC
C
S
|
证明(续1)
1) 若k＝n，则P为G中经过所有结点的路径，即 为哈密尔顿路径。 2) 若k＜n，说明G中还有在P外的结点，那么此 时可以证明存在仅经过P上所有结点的基本回 路，证明如下： a) 若在P上v1与vk相邻，则v1v2…vkv1为仅经过 P上所有结点的基本回路。
S
W
U
S T
XDC
XDC
S
W
U
S T
C
S
|
例
a
S
W
c (a) (b) (c) (d)
U
S T
既存在哈 密尔顿路 径，又存 在哈密尔 顿回路， 即为哈密 尔顿图。 XDC
既不存在哈 密尔顿路径， 也不存在哈 密尔顿回路。
既存在哈密 尔顿路径， 又存在哈密 尔顿回路， 即为哈密尔 顿图。
存在哈密尔 顿路径，但 不存在哈密 尔顿回路。
S
W
U
S T
XDC
C
S
|
尽量避免走桥 求欧拉图中欧拉回路的算法-------Fleury算法：
S
W
U
S T
1. 任取v0∈V，令P0＝v0； 2. 设P0＝v0e1v1e2…eivi，按下面的方法从 E-{e1,e2,…,ei}中选取ei+1： 1) ei+1与vi相关联； 2) 除非无别的边可选取，否则ei+1不应该为 G'＝G-{e1,e2,…,ei}中的桥； 3）当2）不能再进行时，算法结束。
短的路径（即为通过图中所有边的简单路径）； 欧拉回路是经过图中所有边的回路中长度最 短的回路（即为通过图中所有边的简单回路）。
XDC
S
W