图论与网络优化概述

完全图（Complete Graph）\( K_n \)：任意两个顶点之间都有边，共有 \( \binom{n}{2} = \frac{n(n-1)}{2} \) 条边
二部图（Bipartite Graph）：顶点可分为两个不相交的集合，边只存在于两个集合之间
树（Tree）：连通且无回路的无向图，\( n \) 个顶点恰好有 \( n-1 \) 条边
有向无环图（DAG）：没有有向回路的有向图，常用于表示依赖关系
平面图（Planar Graph）：可以画在平面上使得边不相交的图
欧拉图：存在经过每条边恰好一次的回路的图
哈密顿图：存在经过每个顶点恰好一次的回路的图

常见图论问题概述

图的遍历

广度优先搜索（BFS）：从起始顶点出发，按层次逐步向外扩展，使用队列实现。时间复杂度为 \( O(n + m) \)。BFS 可用于：

求无权图的最短路径
检测图的连通性
层次遍历

深度优先搜索（DFS）：从起始顶点出发，尽可能深入探索，使用栈（或递归）实现。时间复杂度为 \( O(n + m) \)。DFS 可用于：

检测回路
拓扑排序
寻找连通分量
寻找割点和桥

最短路径问题

最短路径问题是图论中最经典的问题之一，常见算法包括：

Dijkstra 算法：求单源最短路径，要求边权非负。使用优先队列时，时间复杂度为 \( O((n + m) \log n) \)。

Bellman-Ford 算法：求单源最短路径，允许负权边，可检测负权回路。时间复杂度为 \( O(nm) \)。

Floyd-Warshall 算法：求所有顶点对之间的最短路径。时间复杂度为 \( O(n^3) \)，基于动态规划：

\[ d_{ij}^{(k)} = \min\left(d_{ij}^{(k-1)},\ d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\right) \]

最小生成树

最小生成树（Minimum Spanning Tree，MST）是连通加权无向图的一棵生成树，使得所有边的权重之和最小。

Kruskal 算法：按边权从小到大排序，依次加入不形成回路的边。时间复杂度为 \( O(m \log m) \)。

Prim 算法：从一个顶点开始，每次加入连接已选顶点和未选顶点的最小权边。使用优先队列时，时间复杂度为 \( O((n + m) \log n) \)。

拓扑排序

对于有向无环图（DAG），拓扑排序将所有顶点排成一个线性序列，使得对于每条有向边 \( (u, v) \)，顶点 \( u \) 在序列中排在顶点 \( v \) 之前。

拓扑排序的应用包括：任务调度、编译依赖分析、课程安排等。

图的匹配

匹配（Matching）是图中没有公共顶点的边的集合。最大匹配是包含边数最多的匹配。

二部图最大匹配：匈牙利算法，时间复杂度 \( O(nm) \)
最大权匹配：KM 算法（Kuhn-Munkres），时间复杂度 \( O(n^3) \)

图着色问题

图着色（Graph Coloring）是给图的顶点分配颜色，使得相邻顶点颜色不同。色数 \( \chi(G) \) 是所需最少颜色数。图着色问题是 NP 难问题，广泛应用于频率分配、考试安排等场景。

网络流基本概念

流网络的定义

流网络（Flow Network）是一个有向加权图 \( G = (V, E) \)，具有以下要素：

源点（Source）\( s \)：流的起点
汇点（Sink）\( t \)：流的终点
容量函数 \( c: E \to \mathbb{R}^+ \)：每条边的最大通过量

可行流与最大流

可行流 \( f \) 满足以下约束：

容量约束：对于每条边 \( (u, v) \in E \)，有： \[ 0 \leq f(u, v) \leq c(u, v) \]
流守恒约束：对于除源点和汇点外的每个顶点 \( v \)，流入等于流出： \[ \sum_{(u,v) \in E} f(u,v) = \sum_{(v,w) \in E} f(v,w) \]

最大流问题是在满足约束条件下，求从源点到汇点的最大流量值：

\[ \max |f| = \max \sum_{(s,v) \in E} f(s,v) \]

最大流最小割定理

割（Cut）是将顶点集合 \( V \) 分为两个不相交的子集 \( S \) 和 \( T = V \setminus S \)，使得 \( s \in S \) 且 \( t \in T \)。割的容量定义为：

\[ c(S, T) = \sum_{\substack{u \in S \ v \in T}} c(u, v) \]

最大流最小割定理（Max-Flow Min-Cut Theorem）：网络中最大流的值等于最小割的容量：

\[ \max |f| = \min_{(S,T)} c(S, T) \]

经典最大流算法

Ford-Fulkerson 方法：反复寻找从源点到汇点的增广路径，沿路径增加流量，直到不存在增广路径。

Edmonds-Karp 算法：Ford-Fulkerson 的 BFS 实现，时间复杂度为 \( O(nm^2) \)。

Dinic 算法：利用层次图和阻塞流，时间复杂度为 \( O(n^2 m) \)。

最小费用最大流

最小费用最大流（Minimum Cost Maximum Flow）在每条边不仅有容量限制，还有单位流量的费用 \( w(u,v) \)。目标是在达到最大流的前提下，使总费用最小：

\[ \min \sum_{(u,v) \in E} w(u,v) \cdot f(u,v) \]

常用算法是连续最短路径算法（Successive Shortest Paths），每次在残余网络上寻找费用最小的增广路径。

Python 中图的表示

NetworkX 简介

NetworkX 是 Python 中最常用的图论和网络分析库，提供了丰富的数据结构和算法。

安装方式：

pip install networkx

创建图

import networkx as nx

# 创建无向图
G = nx.Graph()

# 创建有向图
DG = nx.DiGraph()

# 创建加权图
WG = nx.Graph()

添加顶点和边

# 添加顶点
G.add_node(1)
G.add_nodes_from([2, 3, 4, 5])

# 添加边
G.add_edge(1, 2)
G.add_edge(1, 3, weight=4.5)
G.add_edges_from([(2, 3), (3, 4), (4, 5)])

# 添加加权边
G.add_weighted_edges_from([(1, 4, 2.0), (2, 5, 3.5)])

图的基本操作

# 查看顶点和边
print(f"顶点数: {G.number_of_nodes()}")
print(f"边数: {G.number_of_edges()}")

# 查看顶点的度
print(f"顶点1的度: {G.degree(1)}")

# 查看邻居
print(f"顶点1的邻居: {list(G.neighbors(1))}")

# 判断边是否存在
print(f"边(1,2)是否存在: {G.has_edge(1, 2)}")

# 获取邻接矩阵
A = nx.adjacency_matrix(G).todense()

常用图算法

# 最短路径（Dijkstra 算法）
path = nx.dijkstra_path(G, source=1, target=5)
length = nx.dijkstra_path_length(G, source=1, target=5)

# 最小生成树
MST = nx.minimum_spanning_tree(G)

# 连通分量
components = list(nx.connected_components(G))

# 拓扑排序（针对有向无环图）
DG = nx.DiGraph([(1, 2), (1, 3), (2, 4), (3, 4)])
topo_order = list(nx.topological_sort(DG))

网络流计算

# 创建流网络
FG = nx.DiGraph()
FG.add_edge('s', 'a', capacity=10)
FG.add_edge('s', 'b', capacity=8)
FG.add_edge('a', 'b', capacity=5)
FG.add_edge('a', 't', capacity=7)
FG.add_edge('b', 't', capacity=10)

# 求最大流
flow_value, flow_dict = nx.maximum_flow(FG, 's', 't')

# 求最小割
cut_value, partition = nx.minimum_cut(FG, 's', 't')

图的可视化

import matplotlib.pyplot as plt

pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue',
        node_size=500, font_size=12)
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.title("加权图可视化")
plt.show()

原生实现示例

在某些场景下，可能需要不依赖 NetworkX 的原生实现：

# 邻接表表示
class GraphList:
    def __init__(self, n):
        self.n = n
        self.adj = [[] for _ in range(n)]

    def add_edge(self, u, v, weight=1):
        self.adj[u].append((v, weight))
        self.adj[v].append((u, weight))  # 无向图

    def neighbors(self, u):
        return [v for v, _ in self.adj[u]]


# BFS 实现
from collections import deque

def bfs(graph, start):
    """广度优先搜索"""
    visited = set([start])
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order


# Dijkstra 算法实现
import heapq

def dijkstra(graph, source):
    """Dijkstra 最短路径算法"""
    n = graph.n
    dist = [float('inf')] * n
    dist[source] = 0
    pq = [(0, source)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph.adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))

    return dist

应用领域

交通与物流

图论在交通与物流领域有着最直接的应用：

路径规划：利用最短路径算法为车辆、行人规划最优路线。导航系统的核心就是在加权有向图上求解最短路径问题，权重可以是距离、时间或费用。
物流网络设计：利用网络流模型优化货物运输方案，最小化运输成本或最大化运输量。
车辆路由问题（VRP）：在满足容量约束和时间窗口的前提下，为一组车辆规划最优配送路线。
交通流量分配：利用网络流理论分析和优化城市交通网络中的车辆流量分配。

通信网络

网络拓扑设计：利用最小生成树和网络可靠性理论设计通信网络的物理拓扑结构，在保证连通性的同时最小化建设成本。
路由协议：互联网路由协议（如 OSPF、RIP）本质上是在网络图上运行最短路径算法。
带宽分配：利用网络流理论优化链路带宽分配，最大化网络吞吐量。
网络可靠性分析：通过图的连通性分析评估网络的抗毁能力。

社交网络分析

社区发现：利用图聚类算法识别社交网络中的社区结构。
影响力传播：研究信息在社交网络中的传播路径和影响力最大化问题。
中心性分析：通过度中心性、介数中心性、接近中心性等指标识别网络中的关键节点。

中心性度量的数学定义：

度中心性：\( C_D(v) = \frac{\deg(v)}{n - 1} \)

接近中心性：\( C_C(v) = \frac{n - 1}{\sum_{u \neq v} d(v, u)} \)

介数中心性： \[ C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}} \]

其中 \( \sigma_{st} \) 是从 \( s \) 到 \( t \) 的最短路径总数，\( \sigma_{st}(v) \) 是经过 \( v \) 的最短路径数。

生物信息学

蛋白质相互作用网络：蛋白质之间的相互作用关系可建模为图，通过图分析揭示生物功能模块。
代谢网络：细胞内的代谢反应构成复杂网络，图论方法可用于分析代谢通路。

项目管理

关键路径法（CPM）：将项目活动建模为有向无环图，通过求最长路径确定项目最短工期和关键活动。
PERT 网络：在 CPM 基础上引入活动时间的不确定性分析。

数学建模竞赛中的典型应用

在数学建模竞赛中，图论与网络优化问题经常出现，典型场景包括：

选址问题：如设施选址、基站布局，可转化为图上的中心问题或覆盖问题
调度问题：如车间调度、考试安排，可建模为图着色或匹配问题
网络设计：如通信网络、管道铺设，可转化为最小生成树或网络流问题
路径优化：如旅行商问题、中国邮递员问题

小结

图论与网络优化为数学建模提供了强大的理论工具和算法框架。掌握图的基本概念和表示方法是入门的基础，理解各类经典算法（最短路径、最小生成树、网络流等）是解决实际问题的关键。Python 中的 NetworkX 库极大地降低了图论算法的实现门槛，使建模者能够专注于问题的数学抽象和模型构建，而非底层算法实现。

在后续章节中，我们将深入讨论最短路径算法、最小生成树、网络流等专题，并结合具体的数学建模案例展示这些方法的应用。

Keyboard shortcuts

数学建模指南