图论--汉密尔顿图

oldcatcomplex

这是一篇关于一位被离散数学逼疯的当代大学生所总结的有关汉密尔顿图的知识，不全的的地方望大佬补充。
一、基本定义
汉米尔顿通路
图中一条经过每个顶点恰好一次的通路（不要求回到起点）。
汉米尔顿回路
图中一条经过每个顶点恰好一次的回路（起点和终点相同，且路径中无重复顶点）。
汉米尔顿图
含有汉米尔顿回路的图。
注意：仅含汉米尔顿通路但不含回路的图不是汉米尔顿图。
三、判定方法
（一）必要条件（用于否定汉米尔顿图的存在）
顶点度数条件（必要非充分）
若图 G是汉米尔顿图，则对
V(G)的任意非空真子集 S，有：ω(G−S)≤∣S∣其中 ω(G−S)表示删除 S中顶点后图的连通分支数。
补充：连通分支数(引用资料）
一、基本定义

• 连通分支
  
  • 对于无向图 G=(V,E)，若顶点子集 C⊆V 满足：
    
    • C 中任意两个顶点之间存在路径（即 C 是连通的）；
    • 不存在包含 C 的更大连通子集。
      则称 C 为图 G 的一个连通分支（或 “连通分量”）。
      
  • 通俗理解：图中彼此连通的最大子图，不同连通分支之间没有边相连。
    
• 连通分支数（ω(G)）
  
  • 图 G 中所有连通分支的数量，记作 ω(G)。
  • 例子：
    
    • 连通图（如一棵树或一个圈）的连通分支数 ω(G)=1；
    • 由两个不相连的三角形组成的图，连通分支数 ω(G)=2；
    • 完全图 Kn​ 是连通图，故 ω(Kn​)=1。
      
    
    
  
  

二、关键性质

• 与连通性的关系
  
  • 若 ω(G)=1，则图 G 是连通图；
  • 若 ω(G)≥2，则图 G 是非连通图（不连通图）。
    
  
  

应用：若存在某个子集 S使得 ω(G−S)>∣S∣，则 G不是汉米尔顿图。
度数和条件（必要非充分，适用于无向图）
若图 G是汉米尔顿图，则任意不相邻的顶点对 u,v
满足：deg(u)+deg(v)≥n(n 为顶点数)
若存在图G满足：deg(u)+deg(v)≥n-1(n 为顶点数)
则在图G中存在一条汉米尔顿路。
补充：deg为度数，点的度数指的是该点与其他结点的边的个数。
四、汉米尔顿图的性质
连通性
汉米尔顿图必为连通图（因存在经过所有顶点的回路）。
但连通图不一定是汉米尔顿图（如树结构连通但无回路）。
子图与补图
若 G 是汉米尔顿图，则其补图 不一定是汉米尔顿图（需具体分析）。
有向图中的特殊情况
强连通的有向图可能是汉米尔顿图，但弱连通的有向图需满足更强条件。
补充：强连通与弱连通（引用资料）
1. 强连通（Strong Connectivity）

• 定义：
  对于有向图 G=(V,E)，若对于任意两个顶点 u,v∈V，存在从 u 到 v 的有向路径，同时也存在从 v 到 u 的有向路径（即双向连通），则称 G 是强连通图。
• 强连通分支（Strongly Connected Component, SCC）：
  
  • 有向图中的一个极大子图（无法再扩展的子图），其中任意两点之间都存在双向有向路径。
  • 每个有向图都可以唯一分解为若干个强连通分支。
    
• 2. 弱连通（Weak Connectivity）
  
  • 定义：
    将有向图的边方向忽略，视为无向图后，若该无向图是连通的，则称原有向图是弱连通图。
  • 弱连通分支（Weakly Connected Component）：
    
    • 忽略边的方向后，无向图中的连通分支。
    • 弱连通分支的定义与无向图的连通分支一致，仅不考虑边的方向性。
      
  
  补充：一个图有割点或桥一定不是汉密尔顿图。
• 割点：删去此点，图就不连通的点。
• 桥：删去此边，图就不连通的边。
  

sxc

水帖踩了

stevenyoung1120

水贴