人工智能数学基础（十）—— 图论

啊阿狸不会拉杆

发布于 2026-01-21 10:34:09

1090

图论作为数学的重要分支，为人工智能提供了强大的建模和分析工具。无论是社交网络分析、路径规划还是数据结构设计，图论都发挥着不可替代的作用。今天，我将带领大家深入浅出地探索图论的核心概念，并结合 Python 实例，让大家能够直观地理解和应用这些知识。

10.1 图的认识

10.1.1 图的基本概念

图是由一组顶点（或称节点）和一组边组成的数学结构。顶点代表实体，边代表实体之间的关系。图可以分为有向图和无向图。

10.1.2 图中结点的度数

在无向图中，顶点的度数是指与该顶点相连的边的数目。在有向图中，顶点的度数分为入度和出度，入度表示指向该顶点的边的数目，出度表示从该顶点出发的边的数目。

10.1.3 常见的图

完全图 ：每一对不同的顶点之间都有一条边相连。

二分图 ：顶点可以分成两个不相交的集合，且同一集合内的顶点之间没有边相连。

树：无环连通图。

有向无环图（DAG） ：没有有向环的有向图。

10.1.4 子图

子图是原图的一个子集，包含原图的一部分顶点和边。子图的顶点和边都来自原图。

10.1.5 图的同构

如果两个图在顶点和边的连接关系上完全相同，只是顶点的标签不同，则称这两个图为同构的。

示例（绘制简单图）

import networkx as nx
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False
# 创建一个无向图
G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (2, 3), (2, 4), (3, 4)])

# 绘制图
nx.draw(G, with_labels=True, node_color='skyblue', node_size=2000, edge_color='gray', linewidths=1, font_size=15)
plt.title('简单无向图')
plt.show()

10.2 路与回路

10.2.1 路与回路

路是指从一个顶点出发，沿着边行走所经过的顶点序列。回路是指起点和终点相同的路。

10.2.2 连通性

如果图中任意两个顶点之间都有路相连，则称该图为连通图。对于有向图，连通性分为强连通和弱连通。

10.2.3 最短路径

最短路径是指从一个顶点到另一个顶点的最短路。Dijkstra 算法和 Floyd 算法是常用的最短路径算法。

10.2.4 关键路径

关键路径是项目网络图中最长的路径，决定了项目的最短完成时间。

10.2.5 综合案例及应用

案例描述 ：在一个加权图中，求顶点 A 到其他各顶点的最短路径。

import networkx as nx
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei']
# 创建一个加权有向图
G = nx.DiGraph()
edges = [('A', 'B', 3), ('A', 'C', 6), ('B', 'C', 4), ('B', 'D', 4), ('C', 'D', 8), ('C', 'E', 2), ('D', 'E', 3), ('D', 'F', 5), ('E', 'F', 1)]
G.add_weighted_edges_from(edges)

# 计算最短路径
shortest_paths = nx.single_source_dijkstra_path(G, 'A')
shortest_distances = nx.single_source_dijkstra_path_length(G, 'A')

# 绘制图
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='skyblue', node_size=2000, edge_color='gray', linewidths=1, font_size=15)
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.title('加权有向图及最短路径')
plt.show()

# 输出结果
print("从 A 到各顶点的最短路径：", shortest_paths)
print("从 A 到各顶点的最短距离：", shortest_distances)

10.3 图的矩阵表示

10.3.1 邻接矩阵表示

邻接矩阵是一个方阵，用于表示图中顶点之间的邻接关系。如果顶点 i 和顶点 j 之间有边相连，则邻接矩阵的元素为 1，否则为 0。对于加权图，元素为边的权重。

10.3.2 关联矩阵表示

关联矩阵用于表示图中顶点和边的关联关系。每行对应一个顶点，每列对应一条边。如果顶点与边相连，则元素为 1，否则为 0。

10.3.3 综合案例及应用

案例描述 ：用邻接矩阵表示一个无向图，并绘制其图形。

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei']
# 定义邻接矩阵
adj_matrix = np.array([[0, 1, 1, 0],
                       [1, 0, 1, 1],
                       [1, 1, 0, 1],
                       [0, 1, 1, 0]])

# 创建图
G = nx.from_numpy_array(adj_matrix)

# 绘制图
nx.draw(G, with_labels=True, node_color='skyblue', node_size=2000, edge_color='gray', linewidths=1, font_size=15)
plt.title('邻接矩阵表示的无向图')
plt.show()

10.4 欧拉图与哈密顿图

10.4.1 欧拉图

欧拉图是指存在欧拉回路的图。欧拉回路是指经过图中每条边恰好一次且回到起点的回路。判断欧拉图的条件是：无向图所有顶点的度数为偶数；有向图每个顶点的入度等于出度。

10.4.2 哈密顿图

哈密顿图是指存在哈密顿回路的图。哈密顿回路是指经过图中每个顶点恰好一次且回到起点的回路。目前没有简单的判定条件，通常通过尝试构造哈密顿回路来判断。

10.5 树

10.5.1 树的概念

树是一种无环连通图。它具有以下性质：树中的任意两个顶点之间有且仅有一条路径；树有 n-1 条边，其中 n 是顶点数。

10.5.2 生成树

生成树是包含图中所有顶点的子图，并且是一个树。构造生成树的常用算法有 Krusky 算法和 Prim 算法。

10.5.3 二叉树

二叉树是每个顶点最多有两个子树的树。二叉树具有许多重要性质，广泛应用于数据结构和算法设计。

10.5.4 综合案例及应用

案例描述 ：用 Krusky 算法构造一个连通图的最小生成树。

import networkx as nx
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei']
# 创建一个加权无向图
G = nx.Graph()
edges = [('A', 'B', 1), ('A', 'D', 3), ('B', 'C', 2), ('B', 'D', 4), ('B', 'E', 5), ('C', 'E', 6), ('D', 'E', 7), ('D', 'F', 8), ('E', 'F', 9)]
G.add_weighted_edges_from(edges)

# 构造最小生成树
T = nx.minimum_spanning_tree(G, algorithm='kruskal')

# 绘制原图
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='skyblue', node_size=2000, edge_color='gray', linewidths=1, font_size=15)
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.title('原图')
plt.show()

# 绘制最小生成树
nx.draw(T, pos, with_labels=True, node_color='lightgreen', node_size=2000, edge_color='green', linewidths=1, font_size=15)
edge_labels = nx.get_edge_attributes(T, 'weight')
nx.draw_networkx_edge_labels(T, pos, edge_labels=edge_labels)
plt.title('最小生成树')
plt.show()

10.6 实验：最优树理论和应用

10.6.1 实验目的

掌握最优树的概念和构造方法，学会使用 Krusky 算法和 Prim 算法构造最小生成树。

10.6.2 实验要求

给定一个连通图，用 Krusky 算法和 Prim 算法分别构造其最小生成树，并比较结果。

10.6.3 实验原理

Krusky 算法 ：将边按权重从小到大排序，依次选择权重最小且不形成环的边，直到生成树包含所有顶点。
Prim 算法 ：从一个顶点开始，逐步加入权重最小且连接生成树和非生成树顶点的边，直到生成树包含所有顶点。

10.6.4 实验步骤

绘制连通图及其邻接矩阵。
使用 Krusky 算法构造最小生成树。
使用 Prim 算法构造最小生成树。
比较两种算法得到的最小生成树。

10.6.5 实验结果

import networkx as nx
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei']
# 创建一个加权无向图
G = nx.Graph()
edges = [('A', 'B', 1), ('A', 'D', 3), ('B', 'C', 2), ('B', 'D', 4), ('B', 'E', 5), ('C', 'E', 6), ('D', 'E', 7), ('D', 'F', 8), ('E', 'F', 9)]
G.add_weighted_edges_from(edges)

# 绘制原图
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='skyblue', node_size=2000, edge_color='gray', linewidths=1, font_size=15)
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.title('原图')
plt.show()

# 使用 Krusky 算法构造最小生成树
T_kruskal = nx.minimum_spanning_tree(G, algorithm='kruskal')
nx.draw(T_kruskal, pos, with_labels=True, node_color='lightgreen', node_size=2000, edge_color='green', linewidths=1, font_size=15)
edge_labels = nx.get_edge_attributes(T_kruskal, 'weight')
nx.draw_networkx_edge_labels(T_kruskal, pos, edge_labels=edge_labels)
plt.title('Krusky 算法最小生成树')
plt.show()

# 使用 Prim 算法构造最小生成树
T_prim = nx.minimum_spanning_tree(G, algorithm='prim')
nx.draw(T_prim, pos, with_labels=True, node_color='lightcoral', node_size=2000, edge_color='coral', linewidths=1, font_size=15)
edge_labels = nx.get_edge_attributes(T_prim, 'weight')
nx.draw_networkx_edge_labels(T_prim, pos, edge_labels=edge_labels)
plt.title('Prim 算法最小生成树')
plt.show()

10.7 图论知识总结

概念	定义与说明	相关性质
图	由顶点和边组成的数学结构	分为有向图和无向图
路与回路	从一个顶点出发，沿着边行走所经过的顶点序列	回路是起点和终点相同的路
图的矩阵表示	用矩阵表示图中顶点之间的关系	邻接矩阵和关联矩阵
欧拉图	存在欧拉回路的图	无向图所有顶点度数为偶数；有向图每个顶点入度等于出度
哈密顿图	存在哈密顿回路的图	目前没有简单的判定条件
树	无环连通图	生成树是包含图中所有顶点的子图，并且是一个树