数模竞赛-图论模型

NetworkX

基本操作：

python

import networkx

#创建空对象
G=networkx.Graph()
G=networkx.DiGraph()
G=networkx.MultiGraph()
G=networkx.MultiDiGraph()
#由邻接矩阵W创建图
G=networkx.Graph(W)
G=networkx.DiGraph(W)

networkx.draw(G,pos=None,ax=None,**kwds)
    #G为要绘制的网格图 pos为表示位置坐标的字典数据，参数如下：
    #circular_layout 顶点在圆环上均匀分布
    #random_layout 顶点在一个单位正方形内随机分布
    #shell_layout 顶点在多个同心圆上分布
    #spring_layout 用Fruchterman-Reingold算法排列顶点
    #spectral_layout 根据图的拉普拉斯特征向量排列顶点

示例：

python

import networkx,pylab

pylab.subplot(121)
G=networkx.cubical_graph()
networkx.draw(G,with_labels=True)

pylab.subplot(122)
s=['v'+str(i) for i in range(1,9)]
s=dict(zip(range(8),s))
networkx.draw(G,pos=networkx.circular_layout(G),labels=s,node_color='y',node_shape='s',edge_color='b')

pylab.show()

加边加点：

python

import networkx
G=networkx.Graph()
G.add_node(1)
G.add_nodes_from(['A','B'])
G.add_edge('A','B')
G.add_edge(1,2,weight=0.5)
e=[('A','B',0.3),('B','C',0.9),('A','C',0.5),('C','D',1.2)]
G.add_weighted_edges_from(e)
print(G.adj) #邻接表的字典数据
print(list(G.adjacency())) #邻接表的列表数据

画图：

python

import networkx,pylab
G=networkx.DiGraph()
List=[(1,2),(1,3),(2,3),(3,2),(3,5),(4,2),(4,6),(5,2),(5,4),(6,5)]
G.add_nodes_from(range(1,7))
G.add_edges_from(List)
pylab.rc('font',size=16)
networkx.draw(G,pos=networkx.shell_layout(G),with_labels=True,font_weight='bold',node_color='y')
W=networkx.to_numpy_matrix(G)
print(W) #导出邻接矩阵
pylab.show()

画赋权图：

python

import networkx,pylab,numpy
G=networkx.Graph()
List=[(1,3,10),(1,4,60),(2,3,5),(2,4,20),(3,4,1)]
G.add_nodes_from(range(1,5))
G.add_weighted_edges_from(List)
W1=networkx.to_numpy_matrix(G) #权重邻接矩阵
W2=networkx.get_edge_attributes(G,'weight') #赋权边字典数据
pos=networkx.spring_layout(G)
networkx.draw(G,pos,with_labels=True,font_weight='bold')
networkx.draw_networkx_edge_labels(G,pos,font_size=13,edge_labels=W2)
print(W1,G.adj,list(G.adjacency()),networkx.to_dict_of_lists(G)) #邻接矩阵、邻接表字典、邻接表列表、列表字典
numpy.savetxt('data.txt',W1,fmt='%d') #保存邻接矩阵
pylab.show()

最短路

Dijkstra

单源最短路，从 $1$ 到 $8$ 。

python

import networkx
G=networkx.DiGraph()
List=[(1,2,6),(1,3,3),(1,4,1),(2,5,1),(3,2,2),(3,4,2),(4,6,10),(5,4,6),(5,6,4),(5,7,3),(5,8,6),(6,5,10),(6,7,2),(7,8,4),(9,5,2),(9,8,3)]
G.add_nodes_from(range(1,10))
G.add_weighted_edges_from(List)
path=networkx.dijkstra_path(G,1,8,weight='weight')
d=networkx.dijkstra_path_length(G,1,8,weight='weight')
print(path,d) #最短路径、最小费用

Floyd-Warshall

全源最短路。

python

import networkx,numpy
G=networkx.Graph()
List=[(1,3,10),(1,4,60),(2,3,5),(2,4,20),(3,4,1)]
G.add_nodes_from(range(1,5))
G.add_weighted_edges_from(List)
d=networkx.floyd_warshall_numpy(G)
print(d) #最短距离矩阵
path=networkx.shortest_path(G,weight='weight',method='bellman-ford')
for i in range(1,len(d)):
    for j in range(i+1,len(d)+1):
        print(i,j,path[i][j]) #从点i到j的最短路径为...

路径输出：

python

import numpy,networkx,pylab
a=numpy.zeros((6,6))
a[0,1:]=[15,20,27,37,54]
a[1,2:]=[15,20,27,37]
a[2,3:]=[16,21,28]
a[3,4:]=[16,21]
a[4,5]=17
G=networkx.DiGraph(a)
p=networkx.shortest_path(G,0,5,weight='weight')
d=networkx.shortest_path_length(G,0,5,weight='weight')
print(p,d)
pylab.rc('font',size=16)
pos=networkx.shell_layout(G)
w=networkx.get_edge_attributes(G,'weight')
key=range(6)
s=['v'+str(i+1) for i in key]
s=dict(zip(key,s))
networkx.draw(G,pos,font_weight='bold',labels=s,node_color='r')
networkx.draw_networkx_edge_labels(G,pos,edge_labels=w)
path_edges=list(zip(p,p[1:]))
networkx.draw_networkx_edges(G,pos,edgelist=path_edges,edge_color='r',width=3)
pylab.show()

最小值地址：

python

import numpy,networkx
L=[(1,2,20),(1,5,15),(2,3,20),(2,4,60),(2,5,25),(3,4,30),(3,5,18),(5,6,15)]
G=networkx.Graph()
G.add_nodes_from(numpy.arange(1,7))
G.add_weighted_edges_from(L)
d=networkx.floyd_warshall_numpy(G)
md=numpy.max(d,axis=1) #逐行求最小值
mmd=min(md)
ind=numpy.argmin(md)+1 #找最小值地址
print(d,mmd,ind)

最短路问题的01整数规划

略。

最小生成树

代码：

python

import pylab,numpy,networkx
L=[(0,1,2),(0,2,1),(0,3,3),(0,4,4),(0,5,4),(0,6,2),(0,7,5),(0,8,4),(1,2,4),(1,8,1),(2,3,1),(3,4,1),(4,5,5),(5,6,2),(6,7,3),(7,8,5)]
G=networkx.Graph()
G.add_weighted_edges_from(L)
T=networkx.minimum_spanning_tree(G)
c=networkx.to_numpy_matrix(T)
print(c) #邻接矩阵
w=c.sum()/2
print(w) #最小生成树的权重
pos=networkx.circular_layout(G)

pylab.subplot(121)
networkx.draw(G,pos,with_labels=True,font_size=13)
w1=networkx.get_edge_attributes(G,'weight')
networkx.draw_networkx_edge_labels(G,pos,edge_labels=w1)

pylab.subplot(122)
networkx.draw(T,pos,with_labels=True,font_weight='bold')
w2=networkx.get_edge_attributes(T,'weight')
networkx.draw_networkx_edge_labels(T,pos,edge_labels=w2)
pylab.show()

着色问题

对图 $G = (V, E)$ 的顶点进行着色所需最少颜色数目用 $χ (G)$ 表示，称为图 $G$ 的色数。若 $G = (V, E), Δ = max d (v) ∣\in V$ 为图 $G$ 顶点的最大度数，则 $χ (G) ⩽ Δ + 1$ 。

设顶点个数为 $n$ ，顶点最大度为 $Δ$ ，引入0-1变量 $x_{i k}$ 当 $v_{i}$ 着第 $k$ 种颜色时为 $1$ ，否则为 $0$ 。设颜色总数为 $y$ ，建立整数线性规划模型：

$\begin{matrix} min y, \\ s . t . {\begin{cases} \sum_{k = 1}^{Δ + 1} x_{i k} = 1, i = 1, 2, \dots, n, \\ x_{i k} + x_{j k} ⩽ 1, (v_{i}, v_{j}) \in E, k = 1, 2, \dots, Δ + 1, \\ y ⩾ \sum_{k = 1}^{Δ + 1} k x_{i k}, i = 1, 2, \dots, n, \\ x_{i k} = 0 或 1, i = 1, 2, \dots, n, k = 1, 2, \dots, Δ + 1 \end{cases} \end{matrix}$

代码：

python

import cvxpy,numpy
L=[{'张','李','王'},{'李','赵','刘'},{'张','刘','王'},{'赵','刘','孙'},{'张','王','孙'},{'李','刘','王'}]
w=numpy.zeros((6,6))
for i in range(5):
    for j in range(i+1,6):
        if len(L[i]&L[j])>=1:
            w[i,j]=1
ni,nj=numpy.nonzero(w)
w=w+w.T
deg=w.sum(axis=1)
K=int(max(deg))
n=len(w)
x=cvxpy.Variable((n,K+1),integer=True)
y=cvxpy.Variable()
obj=cvxpy.Minimize(y)
con=[cvxpy.sum(x,axis=1)==1,x>=0,x<=1]
for i in range(n):
    con.append(y>=range(1,K+2)@x[i,:])
for k in range(K+1):
    for i in range(len(ni)):
        con.append(x[ni[i],k]+x[nj[i],k]<=1)
prob=cvxpy.Problem(obj,con)
prob.solve(solver='GLPK_MI')
i,k=numpy.nonzero(x.value)
print(prob.value,x.value,i+1,k+1) #最优值 最优解 顶点和颜色对应关系

网络流

最大流

给定一个有向图 $D = (V, A)$ ， $A$ 为弧集， $V$ 指定一点称为发点或源 $v_{s}$ ，该点只有发出的弧。指定一点称为收点或汇 $v_{t}$ ，该点只有进入的弧，其余点称为中间点。对于每一条弧 $(v_{i}, v_{j}) \in A$ 对应有一个 $c (v_{i}, v_{j}) ⩾ 0$ 称为弧的容量。把这样有向图 $D$ 称为一个网络记作 $D = (V, A, C)$ ，其中 $C = c_{i j}$ 。网络上的流指定义在弧集合 $A$ 上的一个函数 $f = f_{i j} = f (v_{i}, v_{j})$ ，称 $f_{i j}$ 为弧 $(v_{i}, v_{j})$ 上的流量。

满足下列条件的流 $f$ 称为可行流：满足容量限制条件 $\forall (v_{i}, v_{j}) \in A, 0 ⩽ f_{i j} ⩽ c_{i j}$ 。满足平衡条件有 $\sum_{j : (v_{i}, v_{j}) \in A} f_{i j} - \sum_{k : (v_{k}, v_{i}) \in A} f_{k i} = 0, \sum_{j : (v_{s}, v_{j}) \in A} f_{s j} = v, \sum_{k : (v_{k}, v_{t}) \in A} f_{k t} = v$ ，其中 $v$ 为这个可行流的流量，即发点的净输出量。可行流总是存在的，如零流。

若给定一个可行流 $f = f_{i j}$ ，把网络中使 $f_{i j} = c_{i j}$ 的弧称为饱和弧，使 $f_{i j} < f_{i j}$ 的弧称为非饱和弧。 $f_{i j} = 0$ 的弧称为零流弧， $f_{i j} > 0$ 的弧称为非零流弧。若 $μ$ 是网络中联结发点 $v_{s}$ 和收点 $v_{t}$ 的一条路，定义路的方向是从 $v_{s}$ 到 $v_{t}$ ，则路上的弧被分为两类：一类是弧的方向与路的方向一致称为前向弧，前向弧全体记为 $μ^{+}$ 。另一类弧与路的方向相反称为后向弧，后向弧全体记为 $μ^{-}$ 。

最大流问题写作线性规划模型为：

$\begin{matrix} max v, \\ s . t . {\begin{cases} \sum_{j : (v_{s}, v_{j}) \in A} f_{s j} = v, \\ \sum_{j : (v_{i}, v_{j}) \in A} f_{i j} - \sum_{k : (v_{k}, v_{i}) \in A} f_{k i} = 0, i \neq s, t, \\ \sum_{k : (v_{k}, v_{t}) \in A} f_{k t} = v, \\ 0 ⩽ f_{i j} ⩽ c_{i j}, \forall (v_{i}, v_{j}) \in A \end{cases} \end{matrix}$

设 $f$ 是一个可行流， $μ$ 时从 $v_{s}$ 到 $v_{t}$ 的一条路，若 $μ$ 满足前向弧是非饱和弧，后向弧时非零流弧，则 $μ$ 称为关于可行流 $f$ 的一条增广路。

Ford-Fulkerson求最大流标号法略。

代码：

python

import numpy,networkx,pylab
L=[(1,2,6),(1,3,4),(1,4,5),(2,3,3),(2,5,9),(2,6,9),(3,4,5),(3,5,6),(3,6,7),(3,7,3),(4,3,2),(4,7,5),(5,8,12),(6,5,8),(6,8,10),(7,6,4),(7,8,15)]
G=networkx.DiGraph()
G.add_nodes_from(range(1,9))
G.add_weighted_edges_from(L,weight='capacity')
value,flow_dict=networkx.maximum_flow(G,1,8)
print(value,flow_dict) #最大流流量 最大流
n=len(flow_dict)
adj_mat=numpy.zeros((n,n),dtype=int)
for i,adj in flow_dict.items():
    for j,weight in adj.items():
        adj_mat[i-1,j-1]=weight
print(adj_mat) #最大流邻接矩阵
ni,nj=numpy.nonzero(adj_mat)
pylab.rc('font',size=16)
pos=networkx.shell_layout(G)
w=networkx.get_edge_attributes(G,'capacity')
networkx.draw(G,pos,font_weight='bold',with_labels=True,node_color='y')
networkx.draw_networkx_edge_labels(G,pos,edge_labels=w)
path_edges=list(zip(ni+1,nj+1))
networkx.draw_networkx_edges(G,pos,edgelist=path_edges,edge_color='r',width=3)
pylab.show()

例题：人才招聘

python

import numpy,networkx
node=['s','A','B','C','D','E','2b','3b','4b','1','2','3','4','t']
n=len(node)
G=networkx.DiGraph()
G.add_nodes_from(node)
L=[('s','A',4),('s','B',3),('s','C',3),('s','D',2),('s','E',4),('A','2b',1),('A','1',1),('A','3b',1),('A','4b',1),('B','2b',1),('B','1',1),('B','3',1),('B','4b',1),('C','1',1),('C','2',1),('C','3',1),('C','4b',1),('D','1',1),('D','2',1),('D','3b',1),('D','4b',1),('E','2b',1),('E','1',1),('E','3',1),('E','4',1),('2b','2',2),('3b','3',1),('4b','4',2),('1','t',5),('2','t',4),('3','t',4),('4','t',3)]
for k in range(len(L)):
    G.add_edge(L[k][0],L[k][1],capacity=L[k][2])
value,flow_dict=networkx.maximum_flow(G,'s','t')
print(value,flow_dict)
A=numpy.zeros((n,n),dtype=int)
for i,adj in flow_dict.items():
    for j,f in adj.items():
        A[node.index(i),node.index(j)]=f
print(A)

最小费用流

设 $b_{i j}$ 为弧 $(v_{i}, v_{j})$ 上的单位费用，最小费用流问题可写作线性规划问题：

$\begin{matrix} min \sum_{(v_{i}, v_{j}) \in A} b_{i j} f_{i j}, \\ s . t . {\begin{cases} \sum_{j : (v_{s}, v_{j}) \in A} f_{s j} = v, \\ \sum_{j : (v_{i}, v_{j}) \in A} f_{i j} - \sum_{k : (v_{k}, v_{i}) \in A} f_{k i} = 0, i \neq s, t, \\ \sum_{k : (v_{k}, v_{t}) \in A} f_{k t} = v, \\ 0 ⩽ f_{i j} ⩽ c_{i j}, \forall (v_{i}, v_{j}) \in A \end{cases} \end{matrix}$

代码：

python

import numpy,networkx
L=[('vs','v2',5,3),('vs','v3',3,6),('v2','v4',2,8),('v3','v2',1,2),('v3','v5',4,2),('v4','v3',1,1),('v4','v5',3,4),('v4','vt',2,10),('v5','vt',5,2)]
G=networkx.DiGraph()
for k in range(len(L)):
    G.add_edge(L[k][0],L[k][1],capacity=L[k][2],weight=L[k][3])
maxFlow=networkx.max_flow_min_cost(G,'vs','vt')
mincost=networkx.cost_of_flow(G,maxFlow)
print(maxFlow,mincost) #最大流 最小费用
node=list(G.nodes())
n=len(node)
flow_mat=numpy.zeros((n,n))
for i,adj in maxFlow.items():
    for j,f in adj.items():
        flow_mat[node.index(i),node.index(j)]=f
print(sum(flow_mat[:,-1]),flow_mat) #最大流量 邻接矩阵

关键路径

设 $t (i, j)$ 为作业 $(i, j)$ 所需工时， $t_{E} (i)$ 为与事件 $j$ 相邻的各紧前事件的最早时间， $t_{E} (n)$ 也为总最早完工期，有：

$\begin{matrix} {\begin{cases} t_{E} (1) = 0, \\ t_{E} (j) = max_{j} {t_{E} (i) + t (i, j)} \end{cases} \end{matrix}$

设 $t_{L} (i)$ 表示以事件 $i$ 为始点的作业最迟必须开始时间，或以事件 $i$ 为终点的各作业最迟必须完成时间，需要从后往前递推，有：

$\begin{matrix} {\begin{cases} t_{L} (n) = t_{E} (n), \\ t_{L} (i) = min_{j} {t_{L} (j) - t (i, j)} \end{cases} \end{matrix}$

数模竞赛-图论模型

NetworkX

最短路

Dijkstra

Floyd-Warshall

最短路问题的01整数规划

最小生成树

着色问题

网络流

最大流

最小费用流

关键路径

微信扫一扫：分享