图论基础：从概念到可视化与路径问题详解
图论基础：从概念到可视化与路径问题详解
一、图论速概览
图论是研究图的性质和图之间关系的数学分支。图由节点和边组成，节点表示对象，边表示对象之间的关系。根据边的方向性，图可以分为无向图和有向图。
无向图：边没有方向，节点之间的连接是双向的。常用于描述简单的关系，如社交网络中的朋友关系。根据边有无权重，无向图可分为无权重无向图和有权重无向图。在无权重无向图中，通常使用 0 和 1 表示边的存在或不存在；在有权重无向图中，边有关联的数值，如欧氏距离、相似度、相关性系数等。
有向图：边有方向，从一个节点指向另一个节点。常用于描述有向关系，例如网页之间的链接、任务执行的顺序、陆地生物链的能量流动模式等。
图与矩阵之间存在密切的关系。例如，有向图可以用邻接矩阵表示：
同样，欧氏距离矩阵也可以抽象为一幅无向图：
更进一步，关联矩阵、度矩阵、拉普拉斯矩阵等都能反映图论与矩阵之间的奇妙关系。
图可以用于分类和聚类，树是图的特殊形态，如 k-NN 中的 kd 树、决策树、层次聚类等。图神经网络（GNNs）是图论的一种拓展，专门处理图结构数据。GNNs 能够在图上进行节点和边的信息传递，使得模型能够理解节点之间的复杂关系。自然语言处理中的大语言模型（LLM）也利用了图论的思想，将语言结构建模为图，其中单词或子词是节点，语法和语义关系是边。
在编程实践中，NetworkX 是一个常用的 Python 开源库，用于创建、操作和研究复杂网络结构。
二、无向图
关键概念
- 节点集：所有节点的集合，表示对象的集合。
- 边集：所有边的集合。
- 阶（order）：节点的数量。
- 大小（size）：边的数量。
- 度（degree）：无向图中，一个节点的度是与它相连的边的数量。
- 邻居（neighbors）：无向图中，一个节点的邻居是通过一条边直接相连的其他节点。
- 端点（end vertex, end node）：度数为 1 的节点。
- 孤立点（isolated node, isolated vertex）：度数为 0 的节点。
特殊结构
- 自环：一个节点与它自己连接的边叫做自环。
- 同构：节点名称、边名称、外观等都不同，但本质上的连接关系一致，即等价图。
- 多图：连接两个节点的边不止一条。这种结构在某些应用中很有用，如网络建模、流量分析等。
- 子图：原始图的一部分。
- 有权图：在无向图的每条边上附加了一个权重或值，表示连接两个节点之间的某种度量，例如距离、成本、时间等。
三、有向图
有向图由于其边的方向性，度分为出度和入度：
- 入度：指向该节点的边的数量。
- 出度：从该节点出发的边的数量。
除了节点集、边集、阶、大小、邻居等概念，有向图还引入了入度邻居（上家）和出度邻居（下家）的概念。
在社交网络或其他网络中，节点之间的连接关系可以形成不同类型的三元组。三元组由三个节点组成，它们之间存在特定的连接模式。以下是三元组的 16 种模式：
非三元组的有向图中可能包含三元组，可以拆分观察。
四、图的可视化
图的可视化是理解和分析图结构的重要手段。可视化的关键点包括节点位置、标签、颜色、大小、记号、选择性绘制，以及边的标签、颜色、线宽、线型、选择性绘制等。
节点位置
绘制有向图和无向图可以使用 networkx.draw_networkx() 函数，通过参数 pos 指定节点位置布局。常用的布局算法包括：
- 弹簧模型布局：使用
networkx.spring_layout()函数，模拟节点间的弹簧力和斥力关系。
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
# 创建无向图
G = nx.random_geometric_graph(200, 0.2, seed=888)
# 使用弹簧模型算法布局节点
pos = nx.spring_layout(G, seed=888)
# 可视化
plt.figure(figsize=(6, 6))
nx.draw_networkx(G,
pos=pos,
node_color='#3388FF',
alpha=0.5,
with_labels=False,
node_size=68)
plt.savefig('节点布局，弹簧算法布局.svg')
- 自定义节点位置：可以通过字典指定节点位置坐标。
data_loc = np.random.rand(200, 2)
# 随机数发生器生成节点平面坐标
# 创建节点位置坐标字典
pos_loc = {i: (data_loc[i, 0], data_loc[i, 1])
for i in range(len(data_loc))}
# 可视化
plt.figure(figsize=(6, 6))
nx.draw_networkx(G,
pos=pos_loc,
node_color='#3388FF',
alpha=0.5,
with_labels=False,
node_size=68)
plt.savefig('节点布局，随机数.svg')
节点装饰
可以调节节点的大小、透明度、颜色等属性。
边装饰
可以设置边的颜色、线宽，并选择性绘制边（比如仅仅保留欧式距离小于0.5的边）。
节点标签
使用 networkx.draw_networkx_labels() 函数可以添加节点标签。
常见图的绘制
NetworkX 提供了多种常见图的生成和布局函数，例如：
networkx.balanced_tree()：创建平衡树图networkx.barbell_graph()：创建哑铃型图networkx.binomial_tree()：创建二叉图networkx.bipartite.gnmk_random_graph()：创建随机二分图networkx.bipartite_layout()：二分图布局networkx.circular_layout()：圆周布局networkx.complete_bipartite_graph()：创建完全二分图networkx.complete_graph()：创建完全图networkx.complete_multipartite_graph()：创建完全多向图networkx.cycle_graph()：创建循环图networkx.ladder_graph()：创建梯子图networkx.lollipop_graph()：创建棒棒糖型图networkx.multipartite_layout()：多向图布局networkx.path_graph()：创建路径图networkx.star_graph()：创建星型图networkx.wheel_graph()：创建轮型图
五、路径问题
路径问题是图论中的一个重要概念，涉及通道、迹、路径、回路和环等概念。
- 通道：沿图的边依次经过一系列节点的序列，可包含重复边或经过相同节点。
- 迹：无重复边的通道，可以包含重复节点。
- 路径：无重复边、无重复节点的通道。
- 回路：闭合的迹。
- 环：闭合的路径。
常见路径问题对比
NetworkX 提供了多种处理路径问题的函数：
networkx.algorithms.approximation.christofides()：使用 Christofides 算法为加权图找到一个近似最短哈密顿回路networkx.all_simple_edge_paths()：查找图中两个节点之间所有简单路径，以边的形式返回networkx.all_simple_paths()：查找图中两个节点之间所有简单路径networkx.complete_graph()：生成一个完全图，图中每对不同的节点之间都有一条边networkx.DiGraph()：创建一个有向图networkx.find_cycle()：在图中查找一个环networkx.get_node_attributes()：获取图中所有节点的指定属性networkx.has_path()：检查图中是否存在从一个节点到另一个节点的路径networkx.shortest_path()：计算图中两个节点之间的最短路径networkx.shortest_path_length()：计算图中两个节点之间最短路径的长度networkx.simple_cycles()：查找有向图中所有简单环networkx.utils.pairwise()：生成一个节点对的迭代器，用于遍历图中相邻的节点对