1. 连通性：图论世界的基石
第一次接触图论时，我被"连通性"这个概念困扰了很久。直到有天看到地铁线路图才恍然大悟——这不就是活生生的连通图吗？车站是顶点，轨道是边，从任意站点都能到达其他所有站点，这就是连通图最直观的例子。
判断图的连通性其实很简单。我常用的方法是广度优先搜索（BFS），就像玩迷宫游戏时用记号笔标记走过的路。下面这段Python代码可以快速判断无向图是否连通：
from collections import deque def is_connected(graph): if not graph: return True visited = set() queue = deque([next(iter(graph))]) while queue: node = queue.popleft() for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return len(visited) == len(graph)实际项目中遇到过有趣的情况：某社交网络分析显示，虽然整体是连通的，但存在明显的"桥梁节点"。删除这些割点后，网络会分裂成多个子图。这让我联想到城市供水系统——某些关键阀门一旦关闭，整个供水网络就会瘫痪。
边连通性同样重要。去年设计数据中心网络拓扑时，我们要求边连通度至少为2。这意味着任意一条光纤断裂，网络仍能保持连通。测试方法很直观：随机移除一条边后检查连通性，重复这个过程直到发现最小割集。
2. 欧拉图：一笔画的数学奥秘
小时候玩过的"一笔画"游戏，其实就是欧拉图的雏形。判断一个图是否存在欧拉回路（能够不重复地走过所有边并回到起点），关键在于顶点的度数：
- 无向图：所有顶点度数都是偶数
- 有向图：每个顶点入度等于出度
记得有次面试，面试官出了道变种题：某公园的步行道系统，问能否设计不重复的游览路线。这就是典型的欧拉通路问题，只需要检查奇度数顶点是否为0或2个：
def has_eulerian_path(graph): odd_degree = 0 for node in graph: if len(graph[node]) % 2 != 0: odd_degree += 1 return odd_degree == 0 or odd_degree == 2实际编码时踩过坑：忽略了图必须连通的前提条件。有次算法在断开图上误判了欧拉回路，导致物流路径规划出错。现在我的检查清单上永远把连通性验证放在第一位。
对于大规模图，可以用Hierholzer算法高效找出欧拉回路。算法思路很巧妙：随意走一条路径，遇到死路就回溯，把环插入到之前的路径中。这就像玩贪吃蛇时不断扩展自己的尾巴：
def find_eulerian_circuit(graph): path = [] stack = [next(iter(graph))] while stack: node = stack[-1] if graph[node]: next_node = graph[node].pop() stack.append(next_node) else: path.append(stack.pop()) return path[::-1]3. 哈密顿图：旅行商问题的近亲
与欧拉图关注边不同，哈密顿图关注的是顶点——能否找到经过每个顶点恰好一次的回路。这个问题看似简单，却是NP完全的，至今没有找到通用高效解法。
在实际路径规划中，我常用这些启发式方法：
- 最近邻法：每次都去最近的未访问节点
- 最小生成树法：先构造MST再生成回路
- 2-opt优化：不断交换边来改进现有解
记得有次用哈密顿图优化仓库拣货路径，将行走距离缩短了30%。关键点是利用了度序列条件：对于n个顶点的图，如果任意两个顶点度数之和≥n，则很可能是哈密顿图。
def is_hamiltonian(graph): n = len(graph) for i in graph: for j in graph: if i != j and j not in graph[i]: if len(graph[i]) + len(graph[j]) < n: return False return True但要注意这仅是充分条件。有次误判导致AGV调度出现死锁，后来增加了闭包测试：反复连接非相邻且度数和≥n的顶点对，直到无法继续，如果最终得到完全图则是哈密顿图。
4. 特殊图的应用实战
二分图在匹配问题中表现突出。去年开发招聘平台时，用匈牙利算法实现了求职者与岗位的智能匹配：
def bipartite_match(graph): match_to = {} result = 0 def bpm(u, seen): for v in graph[u]: if v not in seen: seen.add(v) if v not in match_to or bpm(match_to[v], seen): match_to[v] = u return True return False for u in graph: if bpm(u, set()): result += 1 return result平面图在PCB布线中至关重要。根据欧拉公式v-e+f=2，可以快速验证布线方案是否可行。有次设计六层电路板时，发现某信号层无法满足平面图条件，最终采用via优化解决了问题。
正则图在网络拓扑中很常见。设计数据中心网络时，我们选用3-正则图（每个交换机连接3台服务器），既保证可靠性又控制成本。判断正则图的代码很简单：
def is_regular(graph): if not graph: return True k = len(graph[next(iter(graph))]) return all(len(edges) == k for edges in graph.values())这些特殊图在实际工程中往往组合出现。比如地铁网络可能是平面图与欧拉图的结合，社交网络可能是二分图与非正则图的混合。理解它们的特性和转换条件，是解决复杂问题的关键。
