欧拉图和哈密顿图

觉得有用的话,欢迎一起讨论相互学习~

通路和回路

• 给定图G<V,E>中结点和边相继交错出现的序列,其中V表示图中结点集合,E表示图中边的集合

  \[\Gamma=v_0e_1v_1e_2v_2…e_kv_k
  \]
  1. 若\(\Gamma\)中边\(e_i\)的两个端点是\(v_{i-1}\)和\(v_i\) (G是有向图时要求\(v_{i-1}与v_{i}分别是e_{i}的起始点和终点\)),i=1,2,3,…k,则称\(\Gamma为结点v_0到结点v_k\)的 通路(entry) . \(v_0和v_k\)分别称为此通路的 始点和终点 , 统称为通路的 端点 . 通路中边的数目k称为此通路的 长度(length) .当\(v_0=v_k时，此通路称为\) 回路(circuit)
  2. 若通路中的所有 边(edges) 互不相同，则称此通路为 简单通路(simple entry) 或一条 迹(trail) ;若回路中的所有 边 互不相同，则称此回路为 简单回路(simple circuit,simple cycle) 或一条 闭迹
  3. 若通路中所有 结点(vertices) 互不相同，则称此通路为 基本通路(basic entry) 或 初级通路、路径(path) ,若回路中除 \(v_0=v_k\) 外的所有 结点 互不相同(从而所有边互不相同)，则称此回路为 基本回路(basic circuit) 或者 初级回路、圈

• 说明

  1. 回路是通路的特殊情况 因而如果说某条通路，则它可能是回路，但当说一基本通路时,一般指其不是基本回路的情况。
  2. 基本通路一定是简单通路 , 基本回路一定是简单回路 , 但是反之不然 , 因为没有重复的结点肯定没有重复的边,但没有重复的边不能保证一定没有重复的结点。

可达(accessible)和距离(distance)

• 在图G=<V,E>中, \(v_i,v_j\in V\)

  1. 如果从\(v_i\)到\(v_j\)存在通路,则称\(v_i到v_j\)是 可达的(accessible) ,否则称 \(v_i到v_j不可达\) 。规定：任何结点到自己都是可达的。
  2. 如果\(v_i到v_j\)可达，则称长度最短的 通路 为从\(v_i到v_j\)的 短线程(geodesic) ,从 \(v_i到v_j\) 的短线程的长度称为\(v_i到v_j的\) 距离(distance) ,记为 \(d(v_i,v_j)\) .如果\(v_i到v_j\)不可达，则通常记为\(d(v_i,v_j)=\infty\)

• 对于无向图，若\(v_i到v_j可达\),则\(v_j到v_i一定可达\);也有\(d(v_i,v_j)=d(v_j,v_i)\)

• 对于有向图，若\(v_i到v_j可达\),不一定有\(v_j到v_i一定可达\);也不一定有\(d(v_i,v_j)=d(v_j,v_i)\)

• 在一个具有n个结点的图中,如果从结点\(v_i到结点v_j(v_i\neq v_j)\) , 存在一条通路则从结点\(v_j到结点v_i\)存在一条长度不大于n-1的基本通路。

• 在一个具有n个结点的图中,如果存在经过结点\(v_i\)的回路，则存在一条经过结点\(v_i\)的长度不大于n的基本回路。

图的连通性

无向图的连通性

• 若无向图G中的任何两个结点都是可达的，则称G是连通图(connected graph),否则称G是非连通图(unconnected graph)

有向图的连通性

• 设G=<V,E>是一个有向图，
  1. 略去G中所有有向边得无向图G\’,如果无向图G\’是连通图，则称有向图G是连通图或弱连通图(weakly connected graph); 否则称G是非连通图.
  2. 若G中任何一对结点之间至少有一个结点到另一个结点是可达的，则称G是单向连通图(unilaterally connected graph)
  3. 若G中任何一对结点之间都是互相可达的，则称G是强连通图(strongly connected graph)
• 有向图G是强连通图的充分必要条件是G中存在一条经过所有结点的 回路
• 有向图G是单向连通图的充分必要条件是G中存在一条经过所有结点的 通路

欧拉图和欧拉通路/回路

• 设G是无孤立结点的图，若存在一条通路，经过图中每边一次且仅一次，则称此通路为该图的欧拉通路(eulerian entry)
• 设G是无孤立结点的图，若存在一条回路，经过图中每边一次且仅一次，则称此回路为该图的欧拉回路(eulerian circuit) ,具有欧拉回路的图称为 欧拉图(eulerian graph)
• 以上定义既适合无向图也适合有向图
• 欧拉通路是经过图中所有边的通路中长度最短的通路，即通过图中所有边的简单通路
• 欧拉回路是经过图中所有边的回路中长度最短的回路，即为通过图中所有边的简单回路

欧拉图的判定和性质

• 无向图 G=<V,E>具有一条 欧拉通路 ，当且仅当G是 连通的，且仅有零个或两个奇度数结点
• 无向图 G=<V,E>具有一条 欧拉回路 ，当且仅当G是 连通的， 并且 所有结点的度数均为偶数
• 有向图 G 具有一条 欧拉通路 ，当且仅当G是连通的，且除了两个结点以外，其余结点的入度等于出度，而这两个例外的结点中，一个节点的入度比出度大1，另一个结点的出度比入度大1.
• 有向图 G 具有一条 欧拉回路，当且仅当G是连通的，且所有结点的入度等于出度。

哈密顿图和哈密顿通路/回路

• 经过图中每个节点一次且仅一次的通路称为哈密顿通路(Hamiltonian entry/path)
• 经过图中每个节点一次且仅一次的回路称为哈密顿回路(Hamiltonian circuit/cycle)
• 存在哈密顿回路的图称为哈密顿图(Hamiltonian graph)
• 哈密顿图既适合无向图也适合有向图
• 哈密顿通路是经过图中所有结点的通路中长度最短的通路，即通过图中所有结点的基本通路
• 哈密顿回路是经过图中所有结点的通路中长度最短的回路，即通过图中所有结点的基本回路