《python数学实验与建模》（10）图论模型

• 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$的最短路径和最短距离

  • 绘制图

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

  $C$ -1160 587.5 D F

  表示顶点$C$ 的坐标为$(-1160,587.5)$ ,它是一般目标点，$C点和D点，F点相连$ 完成以下问题：

  1. 画出上面的无向图，第一类目标点用$\star$ 表示，第二类目标点用*表示，一般目标点用‘.’这里要求画出无向图的度量图，即各个顶点的位置坐标必须准确（非拓扑图）

  2. 求顶点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]
     
     

  

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

     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所示。煤可以直接运达，也可以经转运抵达，试确定从煤矿到各电厂间煤的最优调运方案。

  	甲	乙
  甲	0	120
  乙	100	0

  	A	B	C
  甲	150	120	80
  乙	60	160	40

  	A	B	C
  A	0	70	100
  B	50	0	120
  C	100	150	0

  参考：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格式
    
    

  

  • 最短距离：

    	A	B	C
    甲	150	120	80
    乙	60	130	40

  • 线性规划：

    • $x_{ij}$:第$i$个煤矿到第$j$个电厂的调运量
    • $c_{ij}$:第$i$个煤矿到第$j$个电厂的最短距离
    • $b_j$:第$j$个电厂的需求量
    • $a_i$:第$i$个煤矿的产量
    • 目标函数：总吨公里数（吨数$\times$公里数）
    • 约束条件：
      • 产量约束
      • 需求量约束

  • 线性规划模型如下：
    $$\begin{gathered} minz=\sum _{i=1}^2\sum _{j=3}^3{c}_{ij}{x}_{ij} \\ s.t.\{\begin{array}{rl}& \sum _{j=1}^3{x}_{ij}=a_i,i=1,2\\ & \sum _{i=1}^2{x}_{ij}=b_j,j=1,2,3\\ & x_{ij}\ge 0,i=1,2;j=1,2,3\end{array} \end{gathered}$$

  • 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队；等等

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

   • 如果可以找到唯一的一条完全路径，则由它经过的顶点的顺序即为排名顺序
   • 如果存在多条路径：
     • 双向连通图：接连矩阵的最大特征值对应的特征向量$\to$ 排名顺序
     • 非双向连通图：无法确定所有队的排名
   • 如图所示已经存在以下两条完全路径：排除第一种情况
   • 3-1-2-4-5-6
   • 1-2-5-3-4-6

2. 利用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

​文章来源地址https://www.toymoban.com/news/detail-446247.html

到了这里，关于《python数学实验与建模》（10）图论模型的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！