10.1 写出图10.20所示非赋权无向图的关联矩阵和邻接矩阵

绘制图 import networkx as nx

import pylab as plt

import numpy as np

A=np.zeros((6,6))

List=[(1,2),(1,4),(2,3),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)]

for i in List:

A[i[0]-1,i[1]-1]=1

G=nx.Graph(A)

pos=nx.spring_layout(G)

nx.draw(G,pos,with_labels=True,font_size=12)

plt.show()

10.2 计算图10.21所示赋权无向图中从

v

1

到

v

5

v_1到v_5

v1​到v5​的最短路径和最短距离

绘制图 import networkx as nx

import pylab as plt

import numpy as np

LIST=[(1,2,7),(1,3,3),(1,4,12),(2,3,3),(2,6,2),(3,4,8),(4,5,1),(5,6,3)]

G=nx.Graph()

G.add_nodes_from(range(1,7))

G.add_weighted_edges_from(LIST)

weight=nx.get_edge_attributes(G,'weight')#获取权重信息

pos=nx.shell_layout(G)

nx.draw(G,pos,font_size=12,font_weight='bold',with_labels=True)

nx.draw_networkx_edge_labels(G,pos,edge_labels=weight)

plt.show()

求解任意两点的最短路 distance=dict(nx.shortest_path_length(G,weight='weight'))

a=nx.to_numpy_matrix(G)

m,n=a.shape

for i in range(1,m+1):

for j in range(1,n+1):

if i!=j:

print('{0}到{1}的最短距离为：{2}\n'.format(i, j, distance[i][j]))

10.3 求图10.21 所示赋权无向图的最小生成树 import networkx as nx

import pylab as plt

import numpy as np

LIST=[(1,2,7),(1,3,3),(1,4,12),(2,3,3),(2,6,2),(3,4,8),(4,5,1),(5,6,3)]

G=nx.Graph()

G.add_nodes_from(range(1,7))

G.add_weighted_edges_from(LIST)

T=nx.minimum_spanning_tree(G)#默认为破圈法

w=nx.get_edge_attributes(T,'weight')

print("最小生成树的长度为：",sum(w.values()))

nx.draw(T,pos=nx.shell_layout(T),with_labels=True,node_color='blue')

nx.draw_networkx_edge_labels(T,pos=nx.shell_layout(T),edge_labels=w)

plt.show()

#最小生成树的长度为： 12

10.4 已知有6个村子，互相间道路的距离如图10.22所示，拟合建一所小学，已知A处有小学生100人，B处80人，C处60 人，D处40人，E处70人，F处90 人。问小学应再建在那个村庄，使学生上学最方便（走的总路程最短）

求每个点到其余各点的最短距离矩阵 （每个村庄）人数

×

\times

× 距离=总路程 import networkx as nx

import pylab as plt

import numpy as np

#绘制图

nodes='abcdef'.upper()

List=[(1,2,2),(1,3,7),(2,3,4),(2,4,6),(2,5,8),(3,4,1),(3,5,3),(4,5,1),(4,6,6),(5,6,3)]

G=nx.Graph()

G.add_nodes_from(range(1,7))

G.add_weighted_edges_from(List)

w=nx.get_edge_attributes(G,'weight')

pos=nx.shell_layout(G)

nx.draw(G,pos,node_color='red',labels=dict(zip(range(1,7),list(nodes))))

nx.draw_networkx_edge_labels(G,pos,font_size=10,edge_labels=w)

plt.show()

#构造最短距离矩阵

distance=nx.shortest_path_length(G,weight='weight')

matrix=np.zeros((6,6))

for i in distance:

a=i[0]-1

for j in range(1,7):

matrix[a][j-1]=i[1][j]

person=np.array([100,80,60,40,70,90]).reshape(6,1)

print((matrix@person).flatten())

#结果：

#[2350. 1870. 1550. 1590. 1710. 2490.] 由此可见应在C处建学校

10.5 已知95个目标点的数据（excel），第一列是这95个点的编号，第2，3列是这95个点

x

,

y

x,y

x,y 坐标，第4列这些点重要性分类，表明“1”的是第一类重要目标点，表面“2”的是第二列重要点，未标明类别的是一般目标点，第5，6，7列标明了这些点的链接关系。如第三行数据：

C

C

C -1160 587.5 D F 表示顶点

C

C

C 的坐标为

(

−

1160

,

587.5

)

(-1160,587.5 )

(−1160,587.5) ,它是一般目标点，

C

点和

D

点，

F

点相连

C点和D点，F点相连

C点和D点，F点相连 完成以下问题：

画出上面的无向图，第一类目标点用

⋆

\star

⋆ 表示，第二类目标点用*表示，一般目标点用‘.’这里要求画出无向图的度量图，即各个顶点的位置坐标必须准确（非拓扑图） 求顶点L到顶点M3的最短距离和最短路径，并画出最短路径 import networkx as nx

import pylab as plt

import math

import numpy as np

import pandas as pd

data = pd.read_excel('Pex10_5.xlsx',keep_default_na=False)

# 获取坐标构造pos

x_site = data['x坐标'].tolist()

y_site = data['y坐标'].tolist()

d = len(x_site)

position = zip(range(0, d), zip(x_site, y_site))

pos = dict(position) # 构造字典

nodes = data['顶点'].tolist() # 构造点的标签

matrix = pd.DataFrame(np.zeros((d, d)), index=nodes, columns=nodes) # 构造无向图的邻接矩阵

data1 = data.set_index('顶点')

pos_alph = dict(zip(nodes, zip(x_site, y_site))) # 插寻点的坐标

f = lambda X, Y: np.round(np.sqrt((X[0] - X[1]) ** 2 + (Y[0] - Y[1]) ** 2))

for i in nodes:

if len(data1['相邻的顶点1'][i]) != 0:

temp = data1['相邻的顶点1'][i]

x1, y1 = pos_alph[i]

x2, y2 = pos_alph[temp]

matrix[i][temp] = f([x1, x2], [y1, y2]) # 修改为两点之间的距离

if len(data1['相邻的顶点2'][i]) != 0:

temp = data1['相邻的顶点2'][i]

x1, y1 = pos_alph[i]

x2, y2 = pos_alph[temp]

matrix[i][temp] = f([x1, x2], [y1, y2]) # 修改为两点之间的距离

x3, y3 = pos_alph['P3']

x4, y4 = pos_alph['G3']

x5, y5 = pos_alph['O3']

matrix['P3']['G3'] = f([x3, x4], [y3, y4])

matrix['O3']['G3'] = f([x3, x5], [y3, y5])

mat = matrix.T.values # 转化为上三角矩阵

G=nx.Graph(mat)

w=nx.get_edge_attributes(G,'weight')

#求最短距离

source=nodes.index('L');end=nodes.index('M3')

dis=nx.shortest_path_length(G,source,end,weight='weight')

print('L到M3的最短距离为：',dis)

path=nx.shortest_path(G,source,end)

print('L到M3的路径为：',path)

path_edges=list(zip(path,path[1:]))

#绘制最短路径

nx.draw(G,pos,node_size=100,node_color='blue',width=0.7,labels=dict(zip(range(d),nodes)),alpha=0.7,font_size=10)

nx.draw_networkx_edge_labels(G,pos,edge_labels=w,font_size=4)

nx.draw_networkx_edges(G,pos,edgelist=path_edges,edge_color='red',width=2)

# 对应的点的标记修改

data2 = data.set_index('顶点类别')

point1=data2['顶点'][1].tolist()

point2=data2['顶点'][2].tolist()

ind1=[nodes.index(i) for i in point1 if i in nodes]

ind2=[nodes.index(i) for i in point2 if i in nodes]

nx.draw_networkx_nodes(G,pos,nodelist=ind1,node_color='red',node_shape='*')

nx.draw_networkx_nodes(G,pos,nodelist=ind2,node_color='red',node_shape='^')

plt.show()

#结果：

#L到M3的最短距离为： 2613.0

#L到M3的路径为： [10, 9, 22, 14, 26, 27, 49, 80, 79, 89]

当边的权值为两点之间的距离时，求上面无向图的最小生成树，并画出最小生成树 import networkx as nx

import pylab as plt

import math

import numpy as np

import pandas as pd

data = pd.read_excel('Pex10_5.xlsx',keep_default_na=False)

# 获取坐标构造pos

x_site = data['x坐标'].tolist()

y_site = data['y坐标'].tolist()

d = len(x_site)

position = zip(range(0, d), zip(x_site, y_site))

pos = dict(position) # 构造字典

nodes = data['顶点'].tolist() # 构造点的标签

matrix = pd.DataFrame(np.zeros((d, d)), index=nodes, columns=nodes) # 构造无向图的邻接矩阵

data1 = data.set_index('顶点')

pos_alph = dict(zip(nodes, zip(x_site, y_site))) # 插寻点的坐标

f = lambda X, Y: np.round(np.sqrt((X[0] - X[1]) ** 2 + (Y[0] - Y[1]) ** 2))

print(pos_alph)

print(data1)

for i in nodes:

if len(data1['相邻的顶点1'][i]) != 0:

temp = data1['相邻的顶点1'][i]

x1, y1 = pos_alph[i]

x2, y2 = pos_alph[temp]

matrix[i][temp] = f([x1, x2], [y1, y2]) # 修改为两点之间的距离

if len(data1['相邻的顶点2'][i]) != 0:

temp = data1['相邻的顶点2'][i]

x1, y1 = pos_alph[i]

x2, y2 = pos_alph[temp]

matrix[i][temp] = f([x1, x2], [y1, y2]) # 修改为两点之间的距离

x3, y3 = pos_alph['P3']

x4, y4 = pos_alph['G3']

x5, y5 = pos_alph['O3']

matrix['P3']['G3'] = f([x3, x4], [y3, y4])

matrix['O3']['G3'] = f([x3, x5], [y3, y5])

mat = matrix.T.values # 转化为上三角矩阵

G=nx.Graph(mat)

T=nx.minimum_spanning_tree(G)

w=nx.get_edge_attributes(T,'weight')

nx.draw(T,pos=pos,labels=dict(zip(range(d), nodes)),node_size=100,font_size=9,node_color='green',width=0.7)

nx.draw_networkx_edge_labels(T,pos,edge_labels=w,font_size='4')

print(w)

plt.show()

甲，乙两个煤矿分别生产煤500万吨，供应A,B,C三个电厂发电需要，各电厂用量分别为300，300，400（万吨）。已知煤矿之间，煤矿与电厂之间以及各电厂之间相互距离（单位：km）如表10.5，表10.6，表10.7所示。煤可以直接运达，也可以经转运抵达，试确定从煤矿到各电厂间煤的最优调运方案。

甲乙甲0120乙1000

ABC甲15012080乙6016040

ABCA070100B500120C1001500参考：2012年数学建模集训小题目 - 豆丁网 (docin.com)

考虑为线性规划问题+图论问题：

求解出在最短路约束下的分配情况 求解最短路：顶点集为

V

=

{

v

1

,

v

2

,

v

3

,

v

4

,

v

5

}

V=\{v_1,v_2,v_3,v_4,v_5\}

V={v1​,v2​,v3​,v4​,v5​} （甲，乙，A,B,C）边集为相应的路径（权重） import networkx as nx

import pylab as plt

import numpy as np

import pandas as pd

def floyd(graph):

m = len(graph)

dis = graph

path = np.zeros((m, m)) # 路由矩阵初始化

for k in range(m):

for i in range(m):

for j in range(m):

if dis[i][k] + dis[k][j] < dis[i][j]:

dis[i][j] = dis[i][k] + dis[k][j]

path[i][j] = k#更新先驱点

return dis, path

plt.rcParams['font.sans-serif']=['SimHei']

inf=np.inf

if __name__ == "__main__":

W=np.array([[0,120,150,120,80],[100,0,60,160,40],[inf,inf,0,70,100],[inf,inf,50,0,120],[inf,inf,100,150,0]])

nodes=list('甲乙ABC')

edges=[(i,j,W[i-1,j-1])for i in range(1,6)for j in range (1,6) ]

edge=edges.copy()

for i in edges:

if i[2]==inf or i[2]==0:

edge.remove(i)

G=nx.DiGraph()

for k in range(len(edge)):

G.add_edge(edge[k][0]-1,edge[k][1]-1,weight=edge[k][2])

w=nx.get_edge_attributes(G,'weight')

nx.draw(G,pos=nx.shell_layout(G),labels=dict(zip(range(5),nodes)),node_color='red')

nx.draw_networkx_edge_labels(G,nx.shell_layout(G),edge_labels=w)

plt.show()

dis,path=floyd(W)#dis 为最短距离矩阵

mat=dis[0:2,2:]#切片处理

table=pd.DataFrame(mat,columns=list('ABC'),index=['甲','乙'])

print(table.to_markdown())#转化为markdown格式

最短距离：

ABC甲15012080乙6013040 线性规划：

x

i

j

x_{ij}

xij​:第

i

i

i个煤矿到第

j

j

j个电厂的调运量

c

i

j

c_{ij}

cij​:第

i

i

i个煤矿到第

j

j

j个电厂的最短距离

b

j

b_{j}

bj​:第

j

j

j个电厂的需求量

a

i

a_{i}

ai​:第

i

i

i个煤矿的产量目标函数：总吨公里数（吨数

×

\times

×公里数）约束条件：

产量约束需求量约束 线性规划模型如下：

m

i

n

  

z

=

∑

i

=

1

2

∑

j

=

3

3

c

i

j

x

i

j

s

.

t

.

{

∑

j

=

1

3

x

i

j

=

a

i

,

i

=

1

,

2

∑

i

=

1

2

x

i

j

=

b

j

,

j

=

1

,

2

,

3

x

i

j

≥

0

,

i

=

1

,

2

;

j

=

1

,

2

,

3

min~~z=\sum_{i=1}^2\sum_{j=3}^3c_{ij}x_{ij}\\s.t. \left\{ \begin{aligned} &\sum_{j=1}^3x_{ij}=a_i,i=1,2\\ &\sum_{i=1}^2x_{ij}=b_j,j=1,2,3\\ &x_{ij}\ge0,i=1,2;j=1,2,3 \end{aligned} \right.

min  z=i=1∑2​j=3∑3​cij​xij​s.t.⎩

⎨

⎧​​j=1∑3​xij​=ai​,i=1,2i=1∑2​xij​=bj​,j=1,2,3xij​≥0,i=1,2;j=1,2,3​ LNGO： sets:

fac/1..2/:a;

plant/1..3/:b;

coo(fac,plant):x,c;

endsets

data:

a=500,500;

b=300,300,400;

c=150,120,80,60,130,40;

enddata

min=@sum(coo(i,j):c(i,j)*x(i,j));

@for(fac(i):@sum(plant(j):x(i,j))=a(i));

@for(plant(j):@sum(fac(i):x(i,j))=b(j));

Objective value: 78000.00

X( 1, 1) 0.00000

X( 1, 2) 300.0000

X( 1, 3) 200.0000

X( 2, 1) 300.0000

X( 2, 2) 0.000000

X( 2, 3) 200.0000

所以应该从甲地运往B地300万吨，C地200万吨；从乙地运往A地300 万吨，C地200万吨 10.7 图10.23 给出了6支球队的比赛结果，即1队战胜2，4，5，6对，而输给了3队；5队战胜3，6队，而输给1，2，4队；等等

利用竞赛图的适当方法，给出6支球队的一个排名顺序（竞赛图必存在哈密顿圈（不一定回到起始点））参考：《数学模型》（第五版）循环比赛问题

如果可以找到唯一的一条完全路径，则由它经过的顶点的顺序即为排名顺序如果存在多条路径：

双向连通图：接连矩阵的最大特征值对应的特征向量

→

\rightarrow

→ 排名顺序非双向连通图：无法确定所有队的排名 如图所示已经存在以下两条完全路径：排除第一种情况3-1-2-4-5-61-2-5-3-4-6 利用PageRank 算法，再次给出6支球队的排名顺序 import networkx as nx

import pylab as plt

import numpy as np

from scipy.sparse.linalg import eigs

# 绘制有向图

def floyd(graph):

m = len(graph)

dis = graph

path = np.zeros((m, m)) # 路由矩阵初始化

for k in range(m):

for i in range(m):

for j in range(m):

if dis[i][k] + dis[k][j] < dis[i][j]:

dis[i][j] = dis[i][k] + dis[k][j]

path[i][j] = k # 更新先驱点

return dis, path

if __name__ == '__main__':

L = [(1, 2), (1, 4), (1, 5), (1, 6), (2, 4), (2, 6), (2, 5), (3, 1), (3, 2), (3, 4), (4, 5), (4, 6), (5, 3), (5, 6),

(6, 3)]

G = nx.DiGraph()

G.add_nodes_from(range(1, 7))

G.add_edges_from(L)

matrix = np.array(nx.to_numpy_matrix(G)) # 接连矩阵

pos = nx.shell_layout(G)

nx.draw(G, pos, node_size=250, font_weight='bold', node_color='red', with_labels=True, arrowsize=17, width=0.5,

alpha=0.6)

A1 = matrix.copy()

A1[A1 == 0] = np.inf

dis, path = floyd(A1);

print(dis) # 可以看出竞赛图是双向连通图

# 竞赛图算法

w, v = np.linalg.eig(matrix)

print(v[:, 0].argsort()) # 1->3->2->5->4->6 排名顺序

# PageRank 算法

A2 = matrix / np.tile(matrix.sum(axis=1, keepdims=True), (1, matrix.shape[1])) # tile 扩展行和

A2 = 0.15 / matrix.shape[0] + 0.85 * A2 # 构造状态转移矩阵

W, V = eigs(A2.T, 1) # 特征值为1时的特征向量

V = V.real;

V = V.flatten() # 展开成一维数组

V = V / V.sum() # 向量归一化

# 绘制柱状图

plt.figure(2)

plt.bar(range(1, matrix.shape[0] + 1), V, width=0.7, color='b')

plt.show()

#排名为：1->2-> 5-> 4-> 6-> 3

计算如图10.24所示网络的度分布，网络直径，平均路径长度，各节点的聚类系数和整个网络的聚类系数

import networkx as nx

import pylab as plt

L = [(1, 2), (1, 5), (2, 4), (2, 3), (2, 5),

(3, 5), (3, 4), (5, 6)]

G = nx.Graph() # 构造无向图

G.add_nodes_from(range(1, 7)) # 添加顶点集

G.add_edges_from(L)

D = nx.diameter(G) # 求网络直径

LH = nx.average_shortest_path_length(G) # 求平均路径长度

Ci = nx.clustering(G) # 求各顶点的聚类系数

C = nx.average_clustering(G) # 求整个网络的聚类系数

print("网络直径为：", D, "\n平均路径长度为：", LH)

print("各顶点的聚类系数为：")

for index, value in enumerate(Ci.values()):

print("(顶点v{:d}: {:.4f})；".format(index + 1, value), end=' ')

print("\n整个网络的聚类系数为：{:.4f}".format(C))

nx.draw(G, pos=nx.shell_layout(G), with_labels=True)

plt.show()

# 网络直径为： 3

# 平均路径长度为： 1.5333333333333334

# 各顶点的聚类系数为：

# (顶点v1: 1.0000)； (顶点v2: 0.5000)； (顶点v3: 0.6667)； (顶点v4: 1.0000)； (顶点v5: 0.3333)； (顶点v6: 0.0000)；

# 整个网络的聚类系数为：0.5833

​

查看原文