吴世涵的博客
0%

【数学建模笔记 05】数学建模的图与网络

发表于 分类于
本文字数： 11k 阅读时长 ≈ 10 分钟
图论是数学的一个分支，研究图的性质和图之间的关系。图论的基本概念有：无向图、有向图、完全图、子图、结点的度等。本文主要介绍图与网络的基本概念、最短路、最小生成树、最大流等内容，并给出了 Networkx 包的使用方法。

05. 图与网络

基本概念

  • 无向图：一个非空有限集合 和 中的某些元素的无序对集合 ​ 构成的二元组，记 其中 称顶点集或结点集， 称边集，​ 中的每个元素 ​ 为 ​ 中某两个元素 的无序对，记 或 称从 ​ 到 的边；

    • 有限图：结点集和边集都有限的图；
    • 简单图：没有环也没有两条边连接同一对结点。

  • 有向图：一个有向图 由一个非空有限集合 和 中的某些元素的有序对集合 构成二元组，记 其中 称顶点集或结点集， 称弧集， 中的每个元素 为 中某两个元素的有序对，记 称从 到 的弧；

  • 完全图：每一对不同的顶点都有一条边相连的简单图；

  • 子图：如果 ​，称 ​ 是 ​ 的子图， 是 ​ 的母图；

  • 结点的度：设 ， 中与 关联的边数称 的度，记 。​

问题求解

最短路

对于给定的赋权图 ，其中 为结点集，​ 为边集，邻接矩阵 ，其中 之间边的权值之间有边之间无边

固定起点 Dijkstra 算法

为 中某个固定起点，求 到 中另一顶点 的最短距离和最短路径。

Dijkstra 的步骤：

  1. 为每个结点维护：

    • : ​表示起点到结点 的长度；
    • : 表示结点 的父结点。

  2. 令 ，对 ，令

  3. 对每个 ，令 若此次迭代利用结点 ​ 修改了 ，则 ，否则不变；

  4. 将结点 加入 ，构成新的集合；

  5. 若 或 进入 ​，算法终止；否则转步骤 3。

每对结点 Floyd 算法

Floyd 算法：

对于赋权图 ​​，对于邻接矩阵： 有迭代公式： 其中 是迭代次数。

如果要求得最短路径，还需引入路由矩阵

  • 初始时

  • 迭代公式为 其中

最小生成树

在赋权图 中，边权之和最小的生成树称最小生成树。

Kruskal 算法

步骤：

  1. 初始化 ​；
  2. 每次从 ​ 中选取一条边，加入 ，要求使得 ​​​​ 不构成圈的边中权值最小；
  3. 直到选取 个边为止 为结点个数。

Prime 算法

步骤：

  1. 初始化 ​​；

  2. 每次找最短边 ，其中 ，使

  3. 直到 中包含所有结点。

最大流

给定有向图 ​​，在 ​ 中指定发点 (源) ​ 和收点 (汇) ​。对于每一条弧，对应有一个 ​ 称容量，构成一个网络记 其中 。

满足下列条件的流 称可行流：

  • 容量限制：对每一弧 ，；

  • 平衡： 即，发点的流出为 ，收点的流入为 ，其余点流出量=流入量。

根据上述条件，可以构造线性规划模型

不过对于图论模型，有效率更高的解决方法。

Ford-Fulkerson 算法

步骤：

  1. 初始化一个残差网络，与原网络相同，为每条弧 ​​​ 初始化空闲流量 (即未使用的流量) ​​​，其中 ​​​​ 为容量；

  2. 找到一个从发点到收点的路径，记经过的弧集 取空闲流量最小值作为路径的流量，对每条弧更新空闲流量

  3. 对找到的路径生成反向路径，记经过的弧集 其中 即为 的反向弧，每条弧的空闲流量即为之前的正向路径扣除的流量

  4. 合并相同方向的弧，使它们的空闲流量相加；

  5. 直到找不到发点到收点的路径，迭代结束，否则转步骤 2；

  6. 令初始网络的每条弧的容量 与迭代后的残差网络对应的弧的闲流量 相减，即为该条弧的流量

Networkx 包

networkx 是一个用 Python 开发的图论与复杂网络建模工具，内置常用的图与复杂网络的分析算法。

常用函数如下：

  • Graph(): 创建无向图；
  • DiGraph(): 创建有向图；
  • add_edge()：加边；
  • add_edge_from()：加多条边；
  • add_node()：加结点；
  • add_node_from()：加多个结点；
  • dijkstra_path()：求最短路径；
  • dijkstra_path_length()：求最短距离。

画图

对于邻接矩阵表示的无向图： 画图代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# %%

import numpy as np
import networkx as nx

# %%

A = np.array([[0, 9, 2, 4, 7],
              [9, 0, 3, 4, 0],
              [2, 3, 0, 8, 4],
              [4, 4, 8, 0, 6],
              [7, 0, 4, 6, 0]])
G = nx.Graph(A)

# %%

pos=nx.spring_layout(G, iterations=20)

nx.draw_networkx(G, pos=pos)
nx.draw_networkx_edge_labels(G,pos=pos,
                             edge_labels=nx.get_edge_attributes(G, 'weight'))

输出如下：

求最短路

对下图：

graph LR

v1
v2
v3
v4
v5
v6
v7

v1 --3--> v2
v1 --2--> v3
v2 --4--> v4
v2 --6--> v5
v2 --2--> v6
v3 --8--> v2
v3 --1--> v4
v3 --3--> v6
v4 --2--> v5
v6 --5--> v5
v5 --7--> v7
v6 --3--> v7

固定起点

求解 ​ 到其余所有结点的最短路和最短距离，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# %%

import numpy as np
import networkx as nx

# %%

G = nx.DiGraph()
G.add_weighted_edges_from([
    ('v1', 'v2', 3),
    ('v1', 'v3', 2),
    ('v2', 'v4', 4),
    ('v2', 'v5', 6),
    ('v2', 'v6', 2),
    ('v3', 'v2', 8),
    ('v3', 'v4', 1),
    ('v3', 'v6', 3),
    ('v4', 'v5', 2),
    ('v6', 'v5', 5),
    ('v5', 'v7', 7),
    ('v6', 'v7', 3),
])

# %%

path = nx.dijkstra_path(G, source='v1',
                        target='v7',
                        weight='weight')
dist = nx.dijkstra_path_length(G, source='v1',
                               target='v7',
                               weight='weight')

path, dist

输出如下：

1
(['v1', 'v3', 'v6', 'v7'], 8)

于是有，最短路径为 ，最短距离为 8。

每对结点

对于上述问题，求解任意每对结点间的最短距离和路径，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# %%

import numpy as np
import networkx as nx

# %%

G = nx.DiGraph()
G.add_weighted_edges_from([
    ('v1', 'v2', 3),
    ('v1', 'v3', 2),
    ('v2', 'v4', 4),
    ('v2', 'v5', 6),
    ('v2', 'v6', 2),
    ('v3', 'v2', 8),
    ('v3', 'v4', 1),
    ('v3', 'v6', 3),
    ('v4', 'v5', 2),
    ('v6', 'v5', 5),
    ('v5', 'v7', 7),
    ('v6', 'v7', 3),
])

# %%

path = nx.shortest_path(G, weight='weight')
length = nx.shortest_path_length(G, weight='weight')
dict(path), dict(length)

输出如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
({'v1': {'v1': ['v1'],
   'v2': ['v1', 'v2'],
   'v3': ['v1', 'v3'],
   'v4': ['v1', 'v3', 'v4'],
   'v6': ['v1', 'v3', 'v6'],
   'v5': ['v1', 'v3', 'v4', 'v5'],
   'v7': ['v1', 'v3', 'v6', 'v7']},
  'v2': {'v2': ['v2'],
   'v4': ['v2', 'v4'],
   'v5': ['v2', 'v5'],
   'v6': ['v2', 'v6'],
   'v7': ['v2', 'v6', 'v7']},
  'v3': {'v3': ['v3'],
   'v2': ['v3', 'v2'],
   'v4': ['v3', 'v4'],
   'v6': ['v3', 'v6'],
   'v5': ['v3', 'v4', 'v5'],
   'v7': ['v3', 'v6', 'v7']},
  'v4': {'v4': ['v4'], 'v5': ['v4', 'v5'], 'v7': ['v4', 'v5', 'v7']},
  'v5': {'v5': ['v5'], 'v7': ['v5', 'v7']},
  'v6': {'v6': ['v6'], 'v5': ['v6', 'v5'], 'v7': ['v6', 'v7']},
  'v7': {'v7': ['v7']}},
 {'v1': {'v1': 0, 'v3': 2, 'v2': 3, 'v4': 3, 'v6': 5, 'v5': 5, 'v7': 8},
  'v2': {'v2': 0, 'v6': 2, 'v4': 4, 'v7': 5, 'v5': 6},
  'v3': {'v3': 0, 'v4': 1, 'v6': 3, 'v5': 3, 'v7': 6, 'v2': 8},
  'v4': {'v4': 0, 'v5': 2, 'v7': 9},
  'v5': {'v5': 0, 'v7': 7},
  'v6': {'v6': 0, 'v7': 3, 'v5': 5},
  'v7': {'v7': 0}})

可以发现，如 到 ​ 的最短距离为 8，最短路径为 ​，与之前的结论相同，其余结点间也可以查阅。

求最小生成树

对画图示例的邻接矩阵求最小生成树，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# %%

import numpy as np
import networkx as nx

# %%

A = np.array([[0, 9, 2, 4, 7],
              [9, 0, 3, 4, 0],
              [2, 3, 0, 8, 4],
              [4, 4, 8, 0, 6],
              [7, 0, 4, 6, 0]])
G = nx.Graph(A)

# %%

T = nx.minimum_spanning_tree(G)

# %%

pos=nx.spring_layout(T, iterations=20)

nx.draw_networkx(T, pos=pos)
nx.draw_networkx_edge_labels(T,pos=pos,
                             edge_labels=nx.get_edge_attributes(T, 'weight'))

输出如下：

求最大流

对于求最短路的示例，将权值看作容量，求 到 的最大流，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# %%

import numpy as np
import networkx as nx

# %%

G = nx.DiGraph()

edge_list = [
    ('v1', 'v2', 3),
    ('v1', 'v3', 2),
    ('v2', 'v4', 4),
    ('v2', 'v5', 6),
    ('v2', 'v6', 2),
    ('v3', 'v2', 8),
    ('v3', 'v4', 1),
    ('v3', 'v6', 3),
    ('v4', 'v5', 2),
    ('v6', 'v5', 5),
    ('v5', 'v7', 7),
    ('v6', 'v7', 3),
]

for edge in edge_list:
    G.add_edge(edge[0], edge[1], capacity=edge[2])

# %%

value, flow_dic = nx.maximum_flow(G, 'v1', 'v7')

# %%

value, flow_dic

# %%

dic = {}
for s in flow_dic:
    for t in flow_dic[s]:
        dic[(s,t)] = flow_dic[s][t]

pos = nx.spring_layout(G)
nx.draw_networkx(G, pos=pos)
nx.draw_networkx_edge_labels(T,pos=pos,
                             edge_labels=dic)

输出如下：

1
2
3
4
5
6
7
8
(5,
 {'v1': {'v2': 3, 'v3': 2},
  'v2': {'v4': 0, 'v5': 3, 'v6': 0},
  'v3': {'v2': 0, 'v4': 0, 'v6': 2},
  'v4': {'v5': 0},
  'v5': {'v7': 3},
  'v6': {'v5': 0, 'v7': 2},
  'v7': {}})

最大流为 5，并给出具体流向和流量。 e, flow_dic

%%

dic = {} for s in flow_dic: for t in flow_dic[s]: dic[(s,t)] = flow_dic[s][t]

pos = nx.spring_layout(G) nx.draw_networkx(G, pos=pos) nx.draw_networkx_edge_labels(T,pos=pos, edge_labels=dic) 

1
2
3
4
5
6
7
8
9
10
11
12

输出如下：

```python
(5,
 {'v1': {'v2': 3, 'v3': 2},
  'v2': {'v4': 0, 'v5': 3, 'v6': 0},
  'v3': {'v2': 0, 'v4': 0, 'v6': 2},
  'v4': {'v5': 0},
  'v5': {'v7': 3},
  'v6': {'v5': 0, 'v7': 2},
  'v7': {}})

[外链图片转存中...(img-CFykI3AE-1627132572853)]

最大流为 5，并给出具体流向和流量。