简介《图论与网络最优化算法.pdf》是一份面向计算机科学、网络工程与算法学习者的专业讲义聚焦图论中最优化问题的核心理论与经典算法。内容系统梳理了加权图的最小生成树问题详细讲解Kruskal算法与Prim算法的构造思路及正确性证明并深入剖析割边、割集与割点等关键概念结合定理与推论阐明其在网络连通性分析中的意义。这些理论可直接应用于互联网路由选择、网络设计与负载均衡等场景帮助读者建立从数学原理到工程实践的完整认知。资源为单个PDF文件大小约1.45MB便于离线阅读。目前已有222人学习下载适合需要系统梳理图论算法、准备相关考试或从事网络优化工作的读者参考。1. 图论网络最优化算法的底层骨架图论在互联网里的出现频率远比想象中高。路由协议里的最短路径、数据中心网络里的冗余链路规划、CDN 节点之间的流量调度底层都是同一个东西图的模型。很多人把图论当成离散数学里一个考试用的章节但一旦上手真实网络拓扑就会发现 Kruskal、Prim、割点判定这些概念直接决定了网络能不能扛住单点故障。一份经典的图论讲义把生成树、割边割点、匹配、欧拉图和中国邮递员问题这几块硬骨头串在一起每一块都能直接映射到网络规划的真实场景。下文按这份讲义的结构展开给出可运行的代码和参数说明适合正在做网络规划、负载均衡或者复习算法的工程师对照使用。2. 最小生成树Kruskal 与 Prim 的求解逻辑与代码对照2.1 为什么最小生成树是网络设计的首选模型设计一个局域网或者接入网时最朴素的需求是用最少的线缆把所有节点连通。抽象到图上就是在加权无向图中找一个包含全部顶点、且边权总和最小的连通子图也就是最小生成树。讲义里的定理 2·10 和 2·11 分别证明了 Kruskal 算法和 Prim 算法选出的边集确实构成最小生成树证明思路都是反证法假设存在更优的生成树再推出与贪心选择规则矛盾的结论。直观理解上Kruskal 是全局贪心永远先拿当前权值最小的边只要不构成环就收下。Prim 是局部贪心从任意顶点出发每次挑一条连接已选集合和未选集合的最小权边。两者复杂度不同适用场景也不同在工程里需要按图的稀疏程度做选择。2.2 Kruskal 算法的 Python 实现class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) # 路径压缩 return self.parent[x] def union(self, x, y): rx, ry self.find(x), self.find(y) if rx ry: return False # 按秩合并保持树高度可控 if self.rank[rx] self.rank[ry]: self.parent[rx] ry elif self.rank[rx] self.rank[ry]: self.parent[ry] rx else: self.parent[ry] rx self.rank[rx] 1 return True def kruskal(n, edges): edges.sort(keylambda e: e[2]) # 按边权升序 uf UnionFind(n) mst [] total 0 for u, v, w in edges: if uf.union(u, v): # 不成环才收边 mst.append((u, v, w)) total w if len(mst) n - 1: break return mst, total代码逻辑说明先对全部边按权值排序然后用并查集判断一条边的两个端点是否已在同一连通分量。如果不在说明加入后不会成环就收进生成树如果在说明会成环直接跳过。find里的路径压缩和union里的按秩合并把并查集操作压到近似常数时间。当生成树边数达到 n-1 时所有顶点已连通循环提前结束。参数说明n是顶点数edges是三元组(u, v, w)列表u和v是端点编号w是边权。返回mst为选中边列表total为总权值。边数远大于顶点数时排序开销占主导边稀疏时Kruskal 通常比 Prim 更有优势。2.3 Prim 算法实现与差异对比import heapq def prim(n, adj): visited [False] * n min_heap [(0, 0, -1)] # (权值, 顶点, 父顶点) mst [] total 0 while min_heap: w, u, parent heapq.heappop(min_heap) if visited[u]: continue visited[u] True total w if parent ! -1: mst.append((parent, u, w)) for v, w2 in adj[u]: if not visited[v]: heapq.heappush(min_heap, (w2, v, u)) return mst, total这里adj是邻接表adj[u]存放(v, w2)表示 u 到 v 有一条权值为 w2 的边。min_heap是优先队列每次弹出当前已选集合与未选集合之间最小的跨边。visited保证每个顶点只处理一次堆里可能残留旧记录所以弹出时先检查是否已访问。若已访问直接丢弃。参数说明n是顶点个数返回结构与 Kruskal 一致。Prim 在稠密图上通常更快瓶颈在堆操作Kruskal 不依赖图的具体连通形态在稀疏图上更稳。讲义里两个定理的核心都在说明贪心选择不会把全局最优解排挤掉实现时只要正确维护环检测两种算法都能稳定跑上千节点的图。对比维度KruskalPrim贪心策略全局最小边局部最小跨边环检测并查集visited 标记时间复杂度O(E log E)O(E log V)适合场景稀疏图稠密图3. 割边与割点网络可靠性的判定尺度3.1 割边、割集与网络单点故障通信网络里一条链路断了会不会导致整个网络分裂是可靠性设计最先要回答的问题。定理 3·4 给了非常干脆的结论一条边是割边当且仅当它不在任何圈上。只要这条边参与构成某个环断掉后流量还能从环的另一侧绕过去反之如果它不在任何圈里那它就是唯一的连接通道断了必然让图不连通。从工程角度看割边就是单点故障链路。接入网做冗余设计时目标之一就是消灭割边让每条关键链路都至少属于一个环。割集的定义更严格一个边断集刚好把连通图断成两个分支才叫割集。对应到网络场景割集是一组链路把它们全部切断网络才会分裂。定理 3·6 的结论是生成树的余树不包含任何割集而生成树加一条边会得到唯一割集这个性质在故障隔离设计里直接可用。3.2 Tarjan 算法求割边def find_bridges(n, adj): disc [-1] * n low [-1] * n bridges [] time [0] def dfs(u, parent): disc[u] low[u] time[0] time[0] 1 for v in adj[u]: if v parent: continue if disc[v] -1: dfs(v, u) low[u] min(low[u], low[v]) if low[v] disc[u]: bridges.append((u, v)) else: low[u] min(low[u], disc[v]) for i in range(n): if disc[i] -1: dfs(i, -1) return bridgesdisc记录顶点第一次被访问的时间戳low记录该顶点通过回边能到达的最早时间戳。当low[v] disc[u]时说明 v 的子树里没有任何回边能绕到 u 之前的时间戳上那么边(u, v)就是割边。parent参数用来防止无向图里把回边误判成树边无向图的 DFS 会沿一条边从 u 到 v又从 v 走回 u如果不跳过父顶点正常边会被当成回边处理。参数说明n是顶点数adj是邻接表返回的bridges是割边列表。注意low[v] disc[u]是严格大于如果low[v] disc[u]说明 v 的子树里有一条回边能回到 u那么 u 和 v 之间除了这条树边外还有别的路径删除它不影响连通性。3.3 割点判定与推论 3·7 的工程含义割点的判定条件和割边略有差别。定理 3·7 的三个等价命题核心是如果存在两个顶点 u 和 w它们之间的所有路径都必须经过 v那 v 就是割点。DFS 实现里分两种情况根节点只要有两个以上子节点就是割点非根节点满足low[child] disc[u]就是割点。def find_articulation_points(n, adj): disc [-1] * n low [-1] * n ap set() time [0] def dfs(u, parent): children 0 disc[u] low[u] time[0] time[0] 1 for v in adj[u]: if v parent: continue if disc[v] -1: children 1 dfs(v, u) low[u] min(low[u], low[v]) if parent -1 and children 1: ap.add(u) if parent ! -1 and low[v] disc[u]: ap.add(u) else: low[u] min(low[u], disc[v]) for i in range(n): if disc[i] -1: dfs(i, -1) return aplow[v] disc[u]与割边的只有一处差别含义是 v 的子树即使有回边也只能回到 u 自己回不到 u 的祖先所以 u 一旦消失v 的子树就无法与 u 的祖先连通。推论 3·7·1 说树里度大于等于 2 的顶点都是割点在连通图里做初步排查非常省事推论 3·7·2 说任何无环非平凡连通图至少有两个非割点这保证了网络里总有一些节点可以安全下线维护而不影响整体连通。判定对象Tarjan 条件工程含义割边low[v] disc[u]唯一链路断则图裂割点非根low[v] disc[u]关键节点移除后图裂割点根children 1根有多个子树即割点4. 匹配理论与 Hall 定理从理论到最大匹配实现4.1 匹配的基本概念与 Berge 定理匹配问题在互联网里的典型场景是任务分配一批任务和一批执行节点每个节点只能处理某些任务问最多能同时执行多少个任务。这正是二部图最大匹配问题。定义 5·1 到 5·3 给出了匹配、渗透点、交错路径和可增长路径的概念。定理 5·1Berge 定理说一个匹配是最大匹配当且仅当不存在可增长路径。这个定理是整个最大匹配算法的理论基石。可增长路径是一条由非匹配边起始、也由非匹配边结束的交替路径沿着它翻转边的所属状态匹配数就加一。反复找可增长路径直到找不到了就得到最大匹配。这个翻转操作在下面的匈牙利算法里就是递归尝试重新分配的过程。4.2 匈牙利算法的工程实现def hungarian(n, m, adj): match_y [-1] * m def dfs(x, visited): for y in adj[x]: if not visited[y]: visited[y] True if match_y[y] -1 or dfs(match_y[y], visited): match_y[y] x return True return False result 0 for x in range(n): visited [False] * m if dfs(x, visited): result 1 return result, match_ydfs为当前 X 侧顶点寻找增广路径。match_y[y]记录 y 侧顶点当前匹配的 X 侧顶点编号-1 表示未匹配。visited保证每次尝试增广时不重复递归进入同一个 Y 顶点。核心逻辑如果 y 未匹配直接让 x 匹配 y如果 y 已匹配给 x_old就尝试给 x_old 重新找个新的 Y 顶点成功就把 y 让给 x匹配数加一。参数说明n是 X 侧顶点数m是 Y 侧顶点数adj[x]是 x 能连接的 Y 顶点列表。返回result为最大匹配数match_y为匹配方案。匈牙利算法在稠密二部图上复杂度约 O(n*m)配合邻接表实现后几千个顶点规模的分配问题能在秒级内出结果。4.3 Hall 定理与容量规划判断定理 5·2 的 Hall 条件二部图存在渗透 X 全部顶点的匹配当且仅当对任意 S ⊆ X都有 |N(S)| ≥ |S|。这个条件在做容量规划时非常直观如果一组节点能连接到的资源总数小于节点数那么无论如何分配都会有人落空。推论 5·2·1 说 k-正则二部图一定有理想匹配推论 5·2·2 把条件放宽到 X 侧最小度 ≥ t、Y 侧最大度 ≤ t。对应到负载均衡场景只要每个任务至少能联系 t 个节点且每个节点最多被 t 个任务联系理论上可以做到无一遗漏。实际工程里如果 Hall 条件不满足可以把问题转成最大流模型源点到每个 X 顶点容量 1X 到可连 Y 容量 1Y 到汇点容量 1跑 Dinic 得到最大流值就是最大匹配数。这种做法的好处是可以直接复用已有的流计算组件在千级节点规模下依然稳定。4.4 König 定理与最小点覆盖引理 5·3·1 和定理 5·3 给出了 König 定理二部图的最大匹配数等于最小点覆盖数。点覆盖是顶点集合使得每条边至少有一个端点在这个集合里。在安全监控场景中它对应最少需要监控哪些节点才能覆盖所有链路。因为 König 定理保证了在二部图里监控节点数量恰好等于最大匹配数所以可以先跑匈牙利算法得到匹配再按标准构造法把匹配转化为点覆盖方案拿到一组最优监控节点。这个技巧在防火墙部署、日志采集节点选择上都直接用得上。算法或定理解决的问题复杂度或条件匈牙利算法二部图最大匹配O(n*m)Hall 定理判断是否可完全匹配条件对一切 S ⊆ XKönig 定理最大匹配等于最小点覆盖仅适用于二部图最大流转换匹配转最大流复杂度取决于流算法5. 欧拉图与中国邮递员问题从判定到路线重建5.1 欧拉图的判定与 Fleury 算法边界如果一个连通图存在经过每条边恰好一次的闭路那它就是欧拉图。定理 6·1 给出了三个等价条件其中无奇次顶点是最容易验证的一条。在实际网络巡检场景里如果所有节点的链路度数都是偶数那么理论上可以找到一条不重复走任何链路、最后回到起点的巡检路线。如果恰好有两个奇次顶点则从其中一个出发、在另一个结束可以走出一条欧拉道路。Fleury 算法的核心策略是能不走割边就不走割边。也就是说每次选择下一条边时优先选择不会把剩余图拆开的边。这个策略说起来简单但每次选边都要判断当前剩余图的割边整体复杂度偏高。实际工程中更常用 Hierholzer 算法先用 DFS 找一条回路再把回路上的顶点作为入口继续找子回路最后拼接起来。Hierholzer 的复杂度是 O(E)比 Fleury 更适合大规模图。5.2 中国邮递员问题的求解步骤与代码中国邮递员问题要求找到一条从起点出发、遍历所有边至少一次、最后回到起点的最短闭路。当图本身是欧拉图时直接跑 Hierholzer 或 Fleury 即可当图不是欧拉图时需要把奇次顶点两两配对沿它们之间的最短路径添加重复边把图补成欧拉图。讲义里的例 6·6 给出了完整流程先用 Floyd 求所有奇次顶点之间的最短路径再构造以奇次顶点为节点、最短路径长度为边权的完备图求最小权完美匹配然后沿匹配边对应的最短路径加重复边。import itertools def odd_vertex_pairing(odd_vertices, dist): k len(odd_vertices) if k 0: return 0, [] best float(inf) best_pairing None # 固定第一个元素避免同一个配对被重复枚举 for perm in itertools.permutations(odd_vertices): if perm[0] ! odd_vertices[0]: continue total 0 pairing [] for i in range(0, k, 2): u, v perm[i], perm[i 1] total dist[u][v] pairing.append((u, v)) if total best: best total best_pairing pairing return best, best_pairingdist是顶点间最短路径距离矩阵odd_vertices是奇次顶点编号列表。为防止同一配对被重复枚举固定第一个元素不变这样排列数从 k! 降到 (k-1)!但依然是暴力枚举只适合奇次顶点数量很少的图通常不超过 10 个。大型图应改用带花算法求最小权完美匹配复杂度降到多项式级。参数说明odd_vertices是奇次顶点集合dist[i][j]是 i 到 j 的最短路径权值。返回best是重复边最小总权值best_pairing是具体配对方案。得到配对后在原始图上沿配对路径添加平行边组成新图再跑欧拉回路算法就能得到一条完整的最佳巡回路线。场景算法选择说明图本身是欧拉图HierholzerO(E)适合大规模只有两个奇次顶点最短路径加重复边直接沿最短路补边多个奇次顶点Floyd 加最小权匹配奇点少时用暴力枚举5.3 有向欧拉图与流量守恒有向欧拉图的判定条件是每个顶点的入度等于出度对应定理 6·5。这个条件在流量分析里很直观如果每个节点的输入流量和输出流量相等那么整个网络存在一条经过所有弧恰好一次的有向巡回。在做链路审计或环路检测时先检查入出度是否平衡可以快速判断是否存在严格不重复的遍历路径。若某个顶点出度比入度大 1它就是有向欧拉道路的起点入度比出度大 1 的则是终点对应推论 6·5 的条件。6. 平面图判定与拓扑可视化进阶技巧6.1 平面图与欧拉公式的快速筛选画网络拓扑图时最头疼的是交叉线。图论里把能画在平面上、边只在顶点处相交的图叫可平面图。定理 7·1 说任何图都能嵌入三维空间但平面嵌入就要苛刻得多。定理 7·2 用球极投影证明了平面嵌入和球面嵌入等价这个视角在地图类可视化里很常用把拓扑投影到球面再展开回平面交叉效果可能完全不同。定理 7·3 的欧拉公式 v - e f 2 是平面图最经典的约束。已知顶点数和边数可以直接算出面数。例如 10 个顶点、18 条边的连通平面图面数 f 2 - 10 18 10。反过来如果边数超过简单平面图的上界 3v - 6那它一定不是平面图这个不等式能在跑复杂判定前先把明显不合格的图过滤掉。6.2 NetworkX 平面性检测与布局理论上一个图是平面图当且仅当它不包含 K5 或 K3,3 的细分但直接用子图同构去验证是 NP 难的工程上不现实。更常用的做法是用线性复杂度的平面性测试算法NetworkX 里已经封装好了import networkx as nx G nx.Graph() G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (0, 4), (1, 4), (2, 4), (3, 4)]) is_planar, embedding nx.check_planarity(G) print(is_planar)这段代码构造的是 5 个顶点的完全图 K5输出为 False因为 K5 本身就是不可平面图的最小禁子图。check_planarity返回两个值第一个是布尔判定第二个是平面嵌入对象。若判定结果为 True可以用nx.planar_layout生成无交叉的布局坐标再做可视化。平面布局和常规的 spring_layout 相比最大的价值是保证边不交叉这在机房连线图、骨干网拓扑图上能显著减少误读。需要注意check_planarity的输入必须是简单无向图多重边或自环需要先预处理。平面性测试只回答能否画在一个平面上不回答怎样画更美观美观问题要靠布局算法或人工微调解决。实际操作中可以把embedding对象传给nx.combinatorial_embedding_to_pos生成顶点坐标再配合matplotlib输出 SVG 矢量图这样导出的拓扑图纸可以直接用在运维文档里。本文还有配套的精品资源点击获取