图论深度指南

文档概述

图论是研究离散结构中关系的数学分支，其理论在社交网络分析、神经网络、交通路由、推荐系统、知识图谱、分子生物学等人工智能领域有广泛应用。本指南系统介绍图的基本概念与分类、最短路径算法（Dijkstra、Bellman-Ford、Floyd-Warshall、A*）、网络流与匹配（最大流最小割、完美匹配）、图的着色问题、平面图与拓扑图论、谱图理论，以及图神经网络（GNN、GCN、GraphSAGE、GAT）的数学基础。附录包含极值图论、随机图、图算法复杂度分类、拟阵理论等高级专题。

---

零、写在前面：为什么搞AI的人要学图论？

很多人学机器学习、深度学习的时候，觉得自己数学功底还行，线代、概率论、微积分都能handle。但一看到图相关的问题就懵了——什么邻接矩阵、什么最短路径、什么拉普拉斯算子，听着就头大。

其实图论真的没那么可怕。它的核心思想特别简单：世界上的很多东西，本质上就是点和点之间的关系。你朋友圈的好友是点，好友关系是边；网页是点，超链接是边；神经元是点，突触是边；城市是点，公路是边。

把”关系”抽象成”边”，把”实体”抽象成”点”，这就是图论干的事。一旦你这么想，很多AI领域的问题就突然清晰了：

• 社交网络分析：找出意见领袖、发现社群
• 推荐系统：基于用户-商品图做协同过滤
• 知识图谱：实体和关系构成的知识网络
• 分子分析：原子和化学键构成的分子图
• 交通优化：路口和道路构成的路网
• 神经网络：神经元和连接构成的计算图

所以图论不是一门孤立的数学分支，它是理解复杂系统的一把钥匙。掌握了图论，你看很多AI问题的视角都会不一样。

---

一、图的基本概念

1.1 图是什么？点和边如何描述真实世界？

说白了，图就是一堆顶点（也叫结点、节点）和连接它们的边组成的。你可以把图想象成一幅简笔画——几个圆点，用线连起来。

数学上，我们把图记作 $G=(V,E)$。这里 $V$ 是顶点的集合，$E$ 是边的集合。比如你有5个人，互相认识的就连一条线，这就构成了一个”认识关系图”。

无向图 vs 有向图

最简单的区分：边有没有方向。

无向图就像双向车道，你从A能到B，从B也能到A。朋友圈就是这样——你是我的好友，我肯定也是你的好友。有向图就像单行道，Twitter/微博的关注就是有向图——我可以关注你，但你未必关注我。

无向图里，一条边记作 $(u,v)$，有向图里记作 $⟨u,v⟩$。有序对和无序对，一目了然。

加权图

有时候光知道”有关系”还不够，还得知道这个关系有多强、距离有多远、代价有多高。这时候就给边加个权重。地图导航就是最典型的加权图——两点之间不仅有路，还有这条路的长度或者通行时间。

权重可以是距离、时间、成本、容量…看你具体在描述什么问题。

同构与子图

两个图如果顶点和边的连接方式一模一样（只是顶点的名字不同），我们就说它们是同构的。这就像两个不同的公司的组织架构图，只要职位和汇报关系一样，虽然人名不同，但结构是同构的。

子图更好理解，就是从大图里挑一部分顶点，再挑一部分边，组成的更小的图。

1.2 图的类型：一张图搞定分类

图论里对图的分类特别多，刚开始容易搞混。我帮你捋一捋：

按方向分：

• 无向图：边没有方向
• 有向图：边有方向
• 混合图：既有无向边又有有向边

按权重分：

• 无权图：边只有”有”或”没有”的区别
• 加权图：边有权重

按稀疏程度分：

• 稀疏图：边数远少于顶点数，$E\approx O(V)$
• 稠密图：边数接近顶点数平方，$E\approx O(V^2)$

大多数社交网络、互联网图都是稀疏的——一个用户的好友数相比于总用户数总是很小的。稠密图反而比较少见。

特殊图类：

• 完全图 $K_n$：每对顶点之间都有边，$n$ 个顶点有 $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ 条边。想象一个所有人都是好友的社群——这就是完全图。

• 二分图：顶点分成两拨，所有边都只连接不同拨的顶点。男生女生相亲配对就是二分图——边只出现在男女之间，同性之间没有边。

• 树：连通且无环的图。树是图论里最重要的结构之一，它有 $|E|=|V|-1$ 的性质——$n$ 个顶点只需要 $n-1$ 条边就能连起来。

• 森林：若干棵树的集合，也就是无环图。

• 正则图：所有顶点度数相同的图。完全图是正则图，立方体图也是正则图。

• 平面图：可以画在平面上、边不相交的图。现实中很多网络都有 planar 的特性。

1.3 度和邻居：认识一个人通过他的朋友

度（degree） 是图论里最基础的概念之一。顶点 $v$ 的度就是和它相连的边的数量。在无向图里就这么简单。

在有向图里，度要分出度和入度。出度是从这个顶点出发的边数，入度是进入这个顶点的边数。想想微博——你的粉丝数就是入度，你关注的人数就是出度。

握手定理：所有顶点的度数之和等于两倍的边数。为什么？因为每条边贡献两个度数（两个端点各一个）。这个定理有个有趣的推论：度数为奇数的顶点一定是偶数个。你下次参加聚会的时候可以数一数，看看是不是这样。

邻居：和某个顶点直接相连的顶点就是它的邻居。在社交网络里，你的邻居就是你的好友。朋友的朋友（二度关系）也是重要的概念——很多算法都是基于”同质性”假设：相似的顶点更可能相连。

1.4 路径、环、连通性

路径就是从一个顶点走到另一个顶点经过的顶点序列。比如从北京去上海，经过石家庄、济南，这就是一条路径。路径的长度就是边的数量（无权图）或者权重之和（加权图）。

环就是起点和终点相同的路径。绕了一圈又回来了。简单环就是没有重复顶点的环——你不会在环里反复经过同一个城市。

连通性：

• 在无向图里，如果任意两个顶点之间都有路径相连，这就是连通图。否则就是非连通图，它的连通分量就是它的”孤岛”们。

• 在有向图里，连通性更复杂：

  • 强连通：任意两个顶点 $u,v$，$u$ 能到 $v$，$v$ 也能到 $u$
  • 弱连通：忽略方向之后是无向连通的
  • 强连通分量（SCC）：极大强连通子图

找强连通分量有 Kosaraju 算法和 Tarjan 算法，两者都是 $O(V+E)$ 的线性时间算法。Kosaraju 简单直接——两次 DFS，先逆拓扑序再转置图。Tarjan 更巧妙，一次 DFS 搞定，靠的是 lowlink 值。

---

二、图的存储：邻接矩阵与邻接表

写图算法之前，得先解决怎么在计算机里表示图。两种主流方式：

2.1 邻接矩阵

用 $n\times n$ 的矩阵 $A$ 来表示，$A[i][j]=1$ 表示顶点 $i$ 和 $j$ 之间有边。对于加权图，$A[i][j]$ 就存权重。

# 邻接矩阵示例（Python）
import numpy as np
 
# 5个顶点的图
n = 5
A = np.zeros((n, n))
 
# 添加边 (0, 1), (1, 2), (2, 3), (3, 4)
A[0][1] = A[1][0] = 1  # 无向图要对称
A[1][2] = A[2][1] = 1
A[2][3] = A[3][2] = 1
A[3][4] = A[4][3] = 1

优点：查询两点是否相邻是 $O(1)$ 操作，矩阵乘法可以得到路径信息。

缺点：空间是 $O(V^2)$，对于大图很占内存。而且如果是稀疏图（大多数实际网络都是），很多格子都是0，很浪费。

2.2 邻接表

对每个顶点维护一个列表，存它的邻居。

# 邻接表示例
from collections import defaultdict
 
adj_list = defaultdict(list)
adj_list[0] = [1, 4]      # 顶点0的邻居是1和4
adj_list[1] = [0, 2, 3]
adj_list[2] = [1, 4]
adj_list[3] = [1, 4]
adj_list[4] = [0, 2, 3]

优点：空间是 $O(V+E)$，很适合稀疏图。遍历某个顶点的邻居很方便。

缺点：查询两点是否相邻需要遍历邻居列表，最坏 $O(V)$。

2.3 实际选择

大多数情况下用邻接表。除非你的图特别稠密（$E\approx V^2$），或者你需要频繁做”两点是否相邻”的查询，这时候邻接矩阵更合适。

在 Python 里，用 NetworkX 库可以方便地创建和操作图：

import networkx as nx
 
# 创建空图
G = nx.Graph()  # 无向图
# G = nx.DiGraph()  # 有向图
 
# 添加顶点和边
G.add_nodes_from([1, 2, 3, 4, 5])
G.add_edge(1, 2, weight=3.0)
G.add_edge(2, 3, weight=1.5)
 
# 或者一步到位
G = nx.Graph()
G.add_weighted_edges_from([
    (1, 2, 3.0),
    (2, 3, 1.5),
    (3, 4, 2.0),
    (4, 5, 1.0),
    (1, 5, 4.5)
])
 
# 获取邻居
print(list(G.neighbors(1)))  # [2, 5]
 
# 获取度
print(G.degree(1))  # 2
 
# 获取所有边
print(G.edges())

---

三、图的遍历：BFS与DFS

遍历图是很多图算法的基础。就像你去一个城市旅游，得先把主要街道走一遍才能规划路线。

3.1 BFS：广度优先搜索——层层扩散

BFS 的核心思想是”先近后远”。从起点出发，先访问所有距离为1的顶点，再访问距离为2的，以此类推。

这就像你往水里扔一颗石子，涟漪一圈一圈往外扩散。

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[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return order

BFS 的性质：

• 找到的路径一定是最少边数的路径（无权图）
• 遍历顺序按距离分层
• 时间复杂度 $O(V+E)$

BFS 的应用：

• 最短路径（无权图）
• 连通分量检测
• 寻找两个顶点之间的最短距离

3.2 DFS：深度优先搜索——一条路走到黑

DFS 的核心思想是”不撞南墙不回头”。从起点出发，一直往下走，直到没有未访问的邻居，才回退到上一个岔路口。

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start)
    print(start, end=' ')
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    
    return visited

DFS 的性质：

• 可以用递归或栈实现
• 会产生深度优先树
• 每个顶点有发现时间和完成时间

DFS 的应用：

• 拓扑排序
• 检测环
• 找强连通分量
• 解决迷宫问题

3.3 BFS vs DFS：什么时候用哪个？

简单说：

• 找最短路径 → BFS
• 检测环、拓扑排序 → DFS
• 深度优先利于记忆化/动态规划
• 空间效率：BFS的队列在最坏情况下需要 $O(V)$，DFS的递归栈深度也可能是 $O(V)$

---

四、最短路径算法

最短路径问题是图论里最经典的问题之一。从A点到B点，怎么走最近？导航软件每秒钟都在解决这类问题。

4.1 Dijkstra算法：非负权图的首选

Dijkstra 算法1959年由 Edsger W. Dijkstra 提出，是最短路径问题的经典算法。它的核心思想是”贪心”——每次选择当前已知最短距离的顶点，尝试通过它来缩短到其他顶点的距离。

import heapq
 
def dijkstra(graph, start):
    # graph: {u: [(v, weight), ...]}
    dist = {v: float('inf') for v in graph}
    dist[start] = 0
    pq = [(0, start)]  # (距离, 顶点)
    parent = {start: None}
    
    while pq:
        d, u = heapq.heappop(pq)
        
        if d > dist[u]:  # 跳过过时条目
            continue
        
        for v, weight in graph[u]:
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                parent[v] = u
                heapq.heappush(pq, (new_dist, v))
    
    return dist, parent

关键点：

• 只适用于非负权边。如果有负权边，Dijkstra可能给出错误结果
• 使用优先队列时复杂度是 $O((V+E)\log V)$
• 朴素实现（线性扫描最小值）是 $O(V^2)$

Dijkstra 的正确性：可以用”数学归纳法”证明。每次取出最小距离的顶点 $u$，如果存在更短的路径到达 $u$，那条路径必须经过 $Q$ 中的某个顶点，而那个顶点的距离又比 $u$ 小，矛盾。

A*算法：Dijkstra的升级版，加了个”启发函数”来优先搜索更有希望的方向。如果启发函数是真实距离的下界（可采纳的），A能找到最优路径。游戏寻路、机器人导航经常用A。

4.2 Bellman-Ford算法：处理负权边

Bellman-Ford 算法可以处理负权边（只要没有负环），还能检测负环的存在。

def bellman_ford(graph, start, n):
    # graph: 边列表 [(u, v, weight), ...]
    dist = [float('inf')] * n
    dist[start] = 0
    
    # 松弛所有边，重复 n-1 次
    for _ in range(n - 1):
        for u, v, w in graph:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    
    # 第 n 次检查负环
    for u, v, w in graph:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None, None  # 存在负环
    
    return dist, None

核心思想：最短路径最多包含 $V-1$ 条边（否则就有环，可以去掉）。所以松弛 $V-1$ 轮就足够了。如果第 $V$ 轮还能松弛，就说明存在负环。

复杂度：$O(VE)$，比 Dijkstra 慢。但如果图里有负权边，Dijkstra就不行了，只能用它。

SPFA：Bellman-Ford的队列优化版，只松弛那些被更新过的顶点所在的边。在实践中通常快很多，但最坏情况还是 $O(VE)$。

4.3 Floyd-Warshall算法：全对最短路径

Dijkstra 和 Bellman-Ford 都是单源最短路径——从一个点到其他所有点。如果我想知道所有点对之间的最短距离呢？

def floyd_warshall(n, edges):
    # n: 顶点数, edges: 边列表 [(u, v, weight), ...]
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    
    for i in range(n):
        dist[i][i] = 0
    
    for u, v, w in edges:
        dist[u][v] = w
        dist[v][u] = w  # 无向图
    
    # DP: 逐步加入中间顶点
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

核心思想：动态规划。$d_{ij}^{(k)}$ 表示最多经过前 $k$ 个顶点时，$i$ 到 $j$ 的最短距离。递推关系是取”经过 $k$“和”不经过 $k$“的最小值。

复杂度：$O(V^3)$ 时间，$O(V^2)$ 空间。适合顶点数不太多（几百个）的情况。对于大图，用 $|V|$ 次 Dijkstra 更划算。

Johnson算法：结合 Dijkstra 和 Bellman-Ford，处理稀疏图的全对最短路径，复杂度 $O(VE\log V)$。

---

五、最小生成树：连接所有点的最小代价

最小生成树（Minimum Spanning Tree, MST）问题是：给定一个连通加权无向图，找一棵生成树（包含所有顶点、无环），使得边权之和最小。

为什么重要？因为这是”用最少的资源连接所有节点”的数学抽象。铺设通信线路、规划公路网络、聚类分析，都可能用到它。

5.1 Kruskal算法：贪心加边

Kruskal 的思想很简单：把边按权重从小到大排序，然后依次加入，只要不产生环就加。

def kruskal(n, edges):
    # edges: [(weight, u, v), ...]
    edges.sort()  # 按权重排序
    parent = list(range(n))
    rank = [0] * n
    
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])  # 路径压缩
        return parent[x]
    
    def union(x, y):
        px, py = find(x), find(y)
        if px == py:
            return False
        if rank[px] < rank[py]:
            px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]:
            rank[px] += 1
        return True
    
    mst = []
    for w, u, v in edges:
        if union(u, v):
            mst.append((u, v, w))
            if len(mst) == n - 1:
                break
    
    return mst

正确性：基于”切割性质”——在任何切割中，横跨切割的最小边一定在某个最小生成树里。Kruskal 每次选的边都是当前可用的最小边，所以最终一定得到 MST。

复杂度：$O(E\log E)$（排序） + $O(E\cdot \alpha (V))$（并查集），其中 $\alpha$ 是 Ackermann 函数的反函数，几乎是常数。

5.2 Prim算法：贪心扩展

Prim 的思想和 Kruskal 相反：从一个顶点开始，每次选择连接已选集合和未选集合的最小边，逐步扩展。

import heapq
 
def prim(n, graph):
    # graph: {u: [(v, weight), ...]}
    visited = [False] * n
    min_edge = [float('inf')] * n
    min_edge[0] = 0
    pq = [(0, 0)]  # (weight, vertex)
    mst = []
    
    while pq and len(mst) < n:
        w, u = heapq.heappop(pq)
        if visited[u]:
            continue
        
        visited[u] = True
        if w != 0:
            mst.append((u, w))
        
        for v, weight in graph[u]:
            if not visited[v] and weight < min_edge[v]:
                min_edge[v] = weight
                heapq.heappush(pq, (weight, v))
    
    return mst

Prim vs Kruskal：

• Prim 更适合稠密图，因为可以用 $O(V^2)$ 的朴素实现
• Kruskal 更适合稀疏图，因为 $O(E\log E)$ 更有优势
• 两者都产生 MST，边的权重之和相同

---

六、PageRank：Google排名算法的图论秘密

PageRank 是 Google 创始人 Larry Page 和 Sergey Brin 在斯坦福读书时发明的算法，它是 Google 搜索引擎排名系统的核心。虽然现在 Google 的算法复杂得多，但 PageRank 的思想至今仍有重要影响。

6.1 PageRank 的核心思想

PageRank 的核心洞察是：一个网页的重要性，取决于链接到它的其他网页的重要性，以及这些网页链接出去的数量。

这听起来有点绕，但逻辑其实很简单：你被很多重要的牛人认可，那你就是牛人；如果那些牛人还到处”推荐”别人（出链多），那他们的认可含金量就更高。

数学上，PageRank 定义为：

$PR(u)=\frac{1-d}{n}+d{\sum }_{v\in B_u}\frac{PR(v)}{L(v)}$

其中：

• $B_u$ 是链接到 $u$ 的所有网页集合
• $L(v)$ 是网页 $v$ 的出链数
• $d$ 是阻尼因子（通常设为 0.85）
• $n$ 是总网页数

第一项 $\frac{1-d}{n}$ 是”随机跳转”的概率——用户可能不按链接走，而是随机跳到任何一个网页。

6.2 PageRank 的矩阵形式与幂迭代

PageRank 可以写成矩阵形式：

$\pi =(1-d)\frac{1}{n}{1}^T+d{P}^T\pi$

其中 $P$ 是转移矩阵，$P_{ij}$ 表示从网页 $j$ 跳转到网页 $i$ 的概率。

求解这个方程可以用幂迭代法：

import numpy as np
 
def pagerank(adj_matrix, d=0.85, tol=1e-6, max_iter=100):
    """
    adj_matrix: 邻接矩阵（每列和为1，表示转移概率）
    """
    n = adj_matrix.shape[0]
    pi = np.ones(n) / n  # 初始均匀分布
    
    for _ in range(max_iter):
        new_pi = (1 - d) / n + d * adj_matrix @ pi
        if np.linalg.norm(new_pi - pi, 1) < tol:
            break
        pi = new_pi
    
    return pi
 
# 或者用 NetworkX
import networkx as nx
 
G = nx.DiGraph()
G.add_edges_from([
    (0, 1), (0, 2), (1, 2), (2, 0), (2, 3), (3, 3)
])
 
pr = nx.pagerank(G, alpha=0.85)
print(pr)

6.3 PageRank 的实际应用

除了网页排名，PageRank 的思想被广泛应用：

• 社交网络影响力：衡量用户的影响力
• 推荐系统：基于随机游走的协同过滤
• 文本摘要：句子重要性排序
• 金融风控：识别系统重要性机构
• 知识图谱：实体重要性计算

个性化 PageRank：在重启向量里加入用户偏好，可以做个性化推荐。比如你喜欢的电影类型、最近的行为记录。

---

七、社交网络分析：图论在社交领域的应用

社交网络是图论最直接的应用场景之一。你、我、我们所有人，都在编织一张巨大的社交网络图。

7.1 度分布与幂律

社交网络有一个重要特性：度分布服从幂律。也就是说，大部分人的朋友很少，但有少数人朋友非常多。

数学上，度为 $k$ 的顶点数量约等于 $k^{-\gamma }$，其中 $\gamma$ 通常在2到3之间。

这种网络叫无标度网络（Scale-free Network）。它意味着：

• 没有”典型”的度数
• 存在”超级连接者”（hub）
• 对随机故障有鲁棒性，但对针对性攻击很脆弱

想象一下：你的朋友圈可能就几十个人，但有些人可能有几十万粉丝。这就是幂律分布。

7.2 社群检测

社交网络里，用户往往会形成”社群”——内部连接紧密，外部连接稀疏。

Louvain算法是最流行的社群检测算法之一。它优化的是模块度（Modularity）：

$Q=\frac{1}{2m}{\sum }_{ij}\left[A_{ij}-\frac{k_i{k}_j}{2m}\right]\delta (c_i,c_j)$

模块度衡量的是社群内部边数减去”期望边数”的比例。Louvain 通过迭代优化模块度，时间复杂度接近线性。

import networkx as nx
 
# 使用 NetworkX 的社群检测
G = nx.karate_club_graph()  # 空手道俱乐部网络，经典数据集
 
# Louvain 算法
from networkx.algorithms.community import louvain_communities
communities = louvain_communities(G)
 
print(f"发现 {len(communities)} 个社群")
for i, community in enumerate(communities):
    print(f"社群 {i+1}: {len(community)} 个成员")

7.3 影响力最大化

在社交网络里，怎么找出最有影响力的”种子用户”，让信息通过他们传播到最大范围？这就是影响力最大化问题。

一个经典的贪心算法是CELF（Cost-Effective Lazy Forward），它利用子模函数的性质，每次选一个能带来最大边际收益的节点：

def celf_influence_maximization(G, k, simulation_rounds=100):
    """
    简化的 CELF 算法示例
    """
    from networkx.algorithms.community import louvain_communities
    
    S = set()  # 选中的种子集合
    # 实际实现需要蒙特卡洛模拟传播过程
    # 这里返回占位
    
    return list(S)

7.4 链接预测

给定一个社交网络，哪些人之间未来可能会建立联系？这就是链接预测问题。

常见的特征包括：

• 共同邻居数：两人有多少共同好友
• Jaccard系数：共同邻居 / 总邻居
• Adamic-Adar指数：加权共同邻居（度数大的邻居贡献小）
• 优先连接：度大的节点更容易连新边

---

八、知识图谱：图数据库与知识表示

知识图谱是 AI 领域非常重要的技术。Google、百度、搜狗都有自己的知识图谱，用来增强搜索结果。

8.1 什么是知识图谱？

知识图谱本质上是一个多关系有向图：

• 实体（Entity）是顶点
• 关系（Relation）是边
• 每条边是一个三元组 $(h,r,t)$：head（头实体），relation（关系），tail（尾实体）

比如三元组 (北京, 是中国的首都, 北京) 表示北京是北京的首都（显然），但 (北京, 位于, 中国) 是正确的。

8.2 知识图谱嵌入

知识图谱里的实体和关系是符号化的，计算机不方便处理。知识图谱嵌入（KGE）把它们映射到连续的向量空间。

TransE（Bordes et al., 2013）是最经典的模型：

$\mathbf{h}+\mathbf{r}\approx \mathbf{t}$

就是把头实体向量加上关系向量，应该接近尾实体向量。比如”北京 + 首都 ≈ 中国”。

DistMult 是双线性模型，用点积衡量三元组的相似性：

$f(h,r,t)={\mathbf{h}}^T\mathbf{Rt}$

RotatE 把关系建模为复数空间中的旋转：

$\mathbf{h}\circ \mathbf{r}=\mathbf{t}$

这些嵌入可以用于：

• 链接预测（补全知识图谱）
• 实体分类
• 关系抽取
• 问答系统

8.3 图数据库

存储知识图谱需要专门的数据库，叫图数据库。常见的图数据库有：

• Neo4j：最流行的图数据库，使用 Cypher 查询语言
• NebulaGraph：国产高性能图数据库
• TigerGraph：大规模图分析
• JanusGraph：基于 Apache TinkerPop

# Cypher 查询示例（Neo4j）
# 创建知识图谱
CREATE (Beijing:City {name: "北京", population: 21000000})
CREATE (China:Country {name: "中国", capital: "北京"})
CREATE (Beijing)-[:是 {relation: "首都"}]->(China)

---

九、图神经网络GNN：图上的深度学习

这是图论和深度学习交叉的前沿领域。如果你想搞 AI 研究，GNN 是必须了解的。

9.1 为什么需要GNN？

传统的深度学习（CNN、RNN）处理的是规整数据：图像是像素网格，文本是词向量序列。但很多数据天生就是图结构：

• 社交网络：用户-用户关系
• 分子图：原子-化学键结构
• 推荐系统：用户-商品交互
• 知识图谱：实体-关系三元组

CNN 的卷积操作利用的是图像的局部性和平移不变性。图上也有类似的”局部性”——一个顶点的属性很大程度上由它的邻居决定。GNN 就是把卷积操作推广到了图结构上。

9.2 消息传递范式

GNN 的核心是消息传递（Message Passing）范式：

$h_v^{(l+1)}=UPDATE\left(h_v^{(l)},{⨁}_{u\in \mathcal{N}(v)}MESSAGE\left(h_v^{(l)},h_u^{(l)}\right)\right)$

简单说就是：

1. 每个顶点接收邻居发来的”消息”
2. 汇总（$⨁$ 可以是求和、平均、注意力等）所有消息
3. 更新自己的表示

9.3 常见GNN架构

GCN（图卷积网络）：

$H^{(l+1)}=\sigma \left({\tilde{D}}^{-1/2}\tilde{A}{\tilde{D}}^{-1/2}{H}^{(l)}{W}^{(l)}\right)$

这是 Kipf 和 Welling 2017年提出的，是最基础的 GNN 架构。核心操作是归一化的邻接矩阵乘以特征矩阵。

GraphSAGE：

不再对所有邻居一视同仁，而是采样一部分邻居，然后用不同的聚合函数（Mean、LSTM、Pooling）来聚合邻居信息。

GAT（图注意力网络）：

用注意力机制来加权不同邻居的贡献：

$h_v^{(l+1)}=\sigma \left({\sum }_{u\in \mathcal{N}(v)}{\alpha }_{vu}W{h}_u^{(l)}\right)$

其中注意力系数 ${\alpha }_{vu}$ 是学出来的：

${\alpha }_{vu}=\frac{\exp \left(\text{LeakyReLU}\left(a^T[W{h}_v\Vert W{h}_u]\right)\right)}{{\sum }_{k\in \mathcal{N}(v)}\exp \left(\text{LeakyReLU}\left(a^T[W{h}_v\Vert W{h}_k]\right)\right)}$

9.4 GNN的应用

GNN 的应用非常广泛：

• 节点分类：对图中的顶点进行分类（垃圾用户检测）
• 链接预测：预测两个顶点之间是否有边（推荐系统）
• 图分类：对整个图进行分类（分子性质预测）
• 图生成：生成具有特定性质的图（新药分子设计）
• 图匹配：判断两个图是否同构

# PyTorch Geometric 示例
import torch
from torch_geometric.datasets import Planetoid
from torch_geometric.nn import GCNConv
 
class GCN(torch.nn.Module):
    def __init__(self, num_features, num_classes):
        super().__init__()
        self.conv1 = GCNConv(num_features, 16)
        self.conv2 = GCNConv(16, num_classes)
    
    def forward(self, x, edge_index):
        x = self.conv1(x, edge_index)
        x = torch.relu(x)
        x = torch.dropout(x, p=0.5, train=self.training)
        x = self.conv2(x, edge_index)
        return torch.log_softmax(x, dim=1)

---

十、拓扑排序：任务调度与依赖管理

拓扑排序是 DAG（有向无环图）特有的排序。它把顶点排成一个线性序列，使得所有有向边都从序列的前面指向后面。

10.1 为什么需要拓扑排序？

很多实际问题都有”依赖关系”：

• 编译顺序：编译B需要先编译A
• 课程安排：上数据结构之前要先上编程入门
• 任务调度：装修房子要按顺序：水电 → 泥瓦 → 木工 → 油漆

这些依赖关系形成 DAG，拓扑排序就是找一个可行的执行顺序。

10.2 拓扑排序算法

from collections import deque, defaultdict
 
def topological_sort(n, edges):
    """
    Kahn算法（BFS-based）
    """
    graph = defaultdict(list)
    in_degree = [0] * n
    
    for u, v in edges:  # u -> v
        graph[u].append(v)
        in_degree[v] += 1
    
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    if len(result) != n:
        return None  # 图中有环，无法拓扑排序
    
    return result
 
# DFS-based 拓扑排序
def topological_sort_dfs(n, graph):
    visited = [False] * n
    on_stack = [False] * n
    order = []
    
    def dfs(v):
        if on_stack[v]:
            return False  # 有环
        if visited[v]:
            return True
        visited[v] = on_stack[v] = True
        
        for neighbor in graph[v]:
            if not dfs(neighbor):
                return False
        
        on_stack[v] = False
        order.append(v)  # 后序加入
        return True
    
    for v in range(n):
        if not visited[v]:
            if not dfs(v):
                return None
    
    return order[::-1]  # 逆序得到拓扑序

Kahn算法的核心是”逐步移除入度为0的顶点”，DFS算法利用”后序遍历再逆序”。两者复杂度都是 $O(V+E)$。

---

十一、经典问题：欧拉回路、哈密顿回路、着色问题

11.1 欧拉回路：一笔画问题

欧拉回路起源于著名的”哥尼斯堡七桥问题”：普莱格尔河上有七座桥，询问能否从某地出发，走过每座桥恰好一次后回到起点？

欧拉证明了这不可能，从而开创了图论。

判断一个图是否有欧拉回路（无向图）：

• 图必须是连通的
• 所有顶点度数为偶数

Hierholzer算法可以在 $O(E)$ 时间内找到欧拉回路：

def hierholzer(n, edges):
    # 构建邻接表
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    # 找起点（任意偶数度顶点）
    start = next(v for v in graph if len(graph[v]) % 2 == 1) if any(
        len(graph[v]) % 2 == 1 for v in graph
    ) else next(iter(graph))
    
    stack = [start]
    path = []
    
    while stack:
        v = stack[-1]
        if graph[v]:
            u = graph[v].pop()
            graph[u].remove(v)
            stack.append(u)
        else:
            path.append(stack.pop())
    
    return path

11.2 哈密顿回路：TSP问题

哈密顿回路是访问每个顶点恰好一次的回路。这个问题比欧拉回路难得多——它是 NP-完全的。

Dirac定理给出了一个充分条件：$n\ge 3$ 的简单图，如果每个顶点度都 $\ge n/2$，则必存在哈密顿回路。

**旅行商问题（TSP）**是哈密顿回路的加权版本：找总权重最小的哈密顿回路。TSP 是经典的 NP-hard 问题，实际中常用：

• Christofides算法：1.5-近似（度量空间）
• Lin-Kernighan启发式：实际效果很好
• 分支定界：精确求解小规模问题

11.3 图着色问题

图着色问的是：给顶点染色，要求相邻顶点颜色不同，最少需要几种颜色？

四色定理：任何平面图都可以用4种颜色染好。这是个计算机辅助证明的经典案例。

图着色问题是 NP-hard 的，在实际中有以下应用：

• 考试安排：冲突的课程不能安排在同一时间
• 频率分配：相邻区域用不同频率
• 寄存器分配：编译器优化

---

十二、代码演示：用NetworkX创建和分析图

import networkx as nx
import matplotlib.pyplot as plt
 
# 创建图
G = nx.karate_club_graph()  # 空手道俱乐部网络
 
print(f"顶点数: {G.number_of_nodes()}")
print(f"边数: {G.number_of_edges()}")
print(f"平均度: {2 * G.number_of_edges() / G.number_of_nodes():.2f}")
 
# 计算中心性
degree_centrality = nx.degree_centrality(G)
betweenness_centrality = nx.betweenness_centrality(G)
pagerank = nx.pagerank(G)
 
# 找出最重要的节点（按PageRank）
top_nodes = sorted(pagerank.items(), key=lambda x: x[1], reverse=True)[:5]
print("\nPageRank Top 5:")
for node, score in top_nodes:
    print(f"  节点 {node}: {score:.4f}")
 
# 社区检测
communities = nx.community.louvain_communities(G)
print(f"\n社区数: {len(communities)}")
 
# 可视化
plt.figure(figsize=(10, 8))
pos = nx.spring_layout(G, seed=42)
nx.draw(G, pos, node_color=[list(communities).index(next(c for c in communities if v in c)) 
                            for v in G.nodes()],
        cmap=plt.cm.tab10, with_labels=True)
plt.title("Karate Club Network - Community Detection")
plt.show()

---

十三、动手实验：分析社交网络数据

用真实的社交网络数据来练习图论算法。你可以从以下来源获取数据集：

• Stanford Large Network Dataset Collection
• Network Repository

import networkx as nx
import numpy as np
 
# 下载 Facebook 社交网络数据（ ego network）
# G = nx.read_edgelist("facebook_combined.txt")
 
# 或者用内置数据集
G = nx.karate_club_graph()
 
# 实验1：度分布
degrees = [G.degree(n) for n in G.nodes()]
print(f"度分布 - 最小: {min(degrees)}, 最大: {max(degrees)}, 平均: {np.mean(degrees):.2f}")
 
# 实验2：最短路径
if nx.is_connected(G):
    diameter = nx.diameter(G)
    avg_path = nx.average_shortest_path_length(G)
    print(f"直径: {diameter}, 平均路径长度: {avg_path:.3f}")
 
# 实验3：聚类系数
clustering = nx.average_clustering(G)
print(f"平均聚类系数: {clustering:.4f}")
 
# 实验4：连通分量
if not nx.is_connected(G):
    components = list(nx.connected_components(G))
    print(f"连通分量数: {len(components)}")
 
# 实验5：生成树
mst = nx.minimum_spanning_tree(G)
print(f"最小生成树边数: {mst.number_of_edges()}")
 
# 实验6：Bridge 边（删除后使图不连通的边）
bridges = list(nx.bridges(G))
print(f"桥的数量: {len(bridges)}")
 
# 实验7：核心度（K-core分解）
core_numbers = nx.core_number(G)
print(f"最大K-core: {max(core_numbers.values())}")

---

十四、图论发展简史

年份	里程碑
1736	Euler 解决哥尼斯堡七桥问题，图论诞生
1847	Kirchhoff 将树理论应用于电网络
1852	四色猜想提出（1976年证明）
1930	Kuratowski 平面性判定定理
1936	Kőnig 出版图论第一本专著
1941	Turán 开创极值图论
1956	Ford-Fulkerson 最大流最小割定理
1959	Dijkstra 最短路径算法
1971	Karp 证明21个NP-完全问题（含多个图论问题）
1998	Kleinberg 提出 HITS 算法
1999	PageRank 论文发表
2017	Kipf & Welling 提出 GCN
2018	Veličković et al. 提出 GAT

---

相关文档

• 线性代数深度指南 - 图矩阵的线性代数基础
• 概率论深度指南 - 马尔可夫链与图模型
• 博弈论基础 - 网络博弈与图结构博弈
• 凸优化深度指南 - 图割与组合优化
• 统计学深度指南 - 图模型与贝叶斯网络