利用MATLAB和Python进行图与网络模型的高级应用与分析

见贤思齐

专栏：数学建模学习笔记一、图与网络的基本概念1.无向图与有向图无向图：由顶点集合和边集合组成，边是无方向的。表示为G=(V,E)，其中V是顶点集合，E是边集合。有向图：边是有方向的，从一个顶点指向另一个顶点。表示为G=(V,E)，其中每条边用有序对表示。2.简单图、完全图、赋权图简单图：无重复边和自环的图。完全图：每对顶点之间都有边的图，Kn​表示n个顶点的完全图。赋权图：边带有权值的图，用于表示边的某种属性，如距离、费用等。3.顶点的度度：与顶点相连的边的数目。在无向图中，顶点的度即为相连边的数目。在有向图中，入度为指向该顶点的边数，出度为从该顶点出发的边数。4.子图与连通性子图：由原图的一部分顶点和边组成的图。连通性：图中任意两顶点之间存在路径。无向图称为连通图，有向图称为强连通图。5.图的矩阵表示邻接矩阵：表示顶点之间是否有边的矩阵。若顶点i和顶点j之间有边，则矩阵A[i][j]为1，否则为0。关联矩阵：表示顶点和边关系的矩阵。若边ek​连接顶点vi​和vj​，则矩阵A[i][k]和]A[j][k]分别为1。MATLAB代码实例%MATLAB代码%创建无向图和有向图的邻接矩阵表示%无向图的邻接矩阵A_undirected=[0110;1011;1101;0110];%有向图的邻接矩阵A_directed=[0100;0010;0001;1000];%显示邻接矩阵disp('无向图的邻接矩阵:');disp(A_undirected);disp('有向图的邻接矩阵:');disp(A_directed);%创建图对象并可视化G_undirected=graph(A_undirected);G_directed=digraph(A_directed);%绘制图figure;subplot(1,2,1);plot(G_undirected);title('无向图');subplot(1,2,2);plot(G_directed);title('有向图');无向图的邻接矩阵:0110101111010110有向图的邻接矩阵:0100001000011000邻接矩阵表示无向图的邻接矩阵：A_undirected是一个4x4矩阵，其中A_undirected(i,j)表示顶点i和顶点j之间是否有边。对于无向图，矩阵是对称的。有向图的邻接矩阵：A_directed是一个4x4矩阵，其中A_directed(i,j)表示顶点i到顶点j之间是否有边。对于有向图，矩阵不是对称的。显示邻接矩阵使用disp函数显示无向图和有向图的邻接矩阵，以便于检查矩阵的正确性。创建图对象并可视化graph(A_undirected)创建无向图对象。digraph(A_directed)创建有向图对象。使用plot函数可视化图对象。subplot函数将图分成两部分，分别显示无向图和有向图。Python代码实例 importnetworkxasnximportmatplotlib.pyplotaspltimportnumpyasnpfrommatplotlib.font_managerimportFontProperties#设置中文字体font=FontProperties(fname=r"C:\Windows\Fonts\simsun.ttc",size=15)#无向图的邻接矩阵A_undirected=np.array([[0,1,1,0],[1,0,1,1],[1,1,0,1],[0,1,1,0]])#有向图的邻接矩阵A_directed=np.array([[0,1,0,0],[0,0,1,0],[0,0,0,1],[1,0,0,0]])#使用邻接矩阵创建无向图和有向图G_undirected=nx.from_numpy_array(A_undirected)G_directed=nx.from_numpy_array(A_directed,create_using=nx.DiGraph)#绘制无向图plt.figure(figsize=(10,5))plt.subplot(1,2,1)nx.draw(G_undirected,with_labels=True,node_color='skyblue',edge_color='black',node_size=1500,font_size=20)plt.title('无向图',fontproperties=font)#绘制有向图plt.subplot(1,2,2)nx.draw(G_directed,with_labels=True,node_color='lightgreen',edge_color='red',node_size=1500,font_size=20,arrows=True)plt.title('有向图',fontproperties=font)plt.show()注意的细节知识点邻接矩阵表示确保邻接矩阵的对称性（对于无向图）。邻接矩阵的大小应为nxn，其中n是顶点数量。显示矩阵使用disp或print函数显示矩阵，便于检查矩阵的正确性。创建图对象使用graph和digraph函数分别创建无向图和有向图对象。确保输入的邻接矩阵符合图的类型（无向或有向）。可视化图使用plot函数可视化图对象，便于直观理解图的结构。在Python中，可以使用networkx库中的draw函数进行可视化，matplotlib库中的subplot函数分割图形窗口。MATLAB和Python的差异MATLAB中的graph和digraph函数对应于Python中的nx.Graph和nx.DiGraph。MATLAB中的disp函数对应于Python中的print函数。MATLAB中的plot函数对应于Python中的nx.draw函数。二、最短路径问题1.最短路径问题的定义最短路径问题是寻找从一个顶点到另一个顶点的路径，使得路径上的边权值和最小。2.Dijkstra算法适用于非负权图的单源最短路径问题。算法步骤：初始化：设置起点到自己的距离为0，其他顶点为无穷大。选择未处理的顶点中距离最小的顶点，将其标记为已处理。更新该顶点的邻接顶点的距离。重复步骤2和3，直到所有顶点都被处理。MATLAB代码实例%MATLAB代码%Dijkstra算法实现function[dist,path]=dijkstra(A,start_node)n=size(A,1);%顶点数量dist=inf(1,n);%初始化距离dist(start_node)=0;visited=false(1,n);%访问标记path=-ones(1,n);%路径fori=1:n%选择未处理顶点中距离最小的顶点[~,u]=min(dist+visited*inf);visited(u)=true;%更新邻接顶点的距离forv=1:nifA(u,v)>0&~visited(v)alt=dist(u)+A(u,v);ifalt0&~visited(v)：如果顶点v与顶点u之间有边且未被访问。alt=dist(u)+A(u,v)：计算通过顶点u到顶点v的距离。ifalt0andnotvisited[v]:alt=dist[u]+weightifalt0edges=[edges;i,j,A(i,j)];endendendedges=sortrows(edges,3);parent=1:n;mst_edges=[];mst_weight=0;functionp=find(parent,x)ifparent(x)==xp=x;elsep=find(parent,parent(x));parent(x)=p;endendfork=1:size(edges,1)u=edges(k,1);v=edges(k,2);w=edges(k,3);pu=find(parent,u);pv=find(parent,v);ifpu~=pvmst_edges=[mst_edges;u,v];mst_weight=mst_weight+w;parent(pu)=pv;endendend%示例图的邻接矩阵A=[01065;100015;6004;51540];%计算最小生成树[mst_edges,mst_weight]=kruskal(A);%显示结果disp('最小生成树的边:');disp(mst_edges);disp('最小生成树的权重:');disp(mst_weight);%可视化结果G=graph(A);figure;h=plot(G,'EdgeLabel',G.Edges.Weight);highlight(h,mst_edges(:,1),mst_edges(:,2),'EdgeColor','r','LineWidth',2);title('Kruskal最小生成树');最小生成树的边:341412最小生成树的权重:19初始化n=size(A,1)：获取图中顶点的数量。edges=[]：初始化边的列表。使用嵌套循环遍历邻接矩阵，收集所有边的信息。边的排序edges=sortrows(edges,3)：按边的权值从小到大排序。并查集的初始化parent=1:n：初始化每个顶点的父节点为自身。mst_edges=[]：初始化最小生成树的边列表。mst_weight=0：初始化最小生成树的权重和。并查集查找函数functionp=find(parent,x)：递归查找顶点的根节点，并进行路径压缩。Python代码实例classUnionFind:def__init__(self,n):self.parent=list(range(n))deffind(self,u):ifself.parent[u]!=u:self.parent[u]=self.find(self.parent[u])returnself.parent[u]defunion(self,u,v):root_u=self.find(u)root_v=self.find(v)ifroot_u!=root_v:self.parent[root_u]=root_vdefkruskal(A):n=len(A)edges=[(A[i][j],i,j)foriinrange(n)forjinrange(i+1,n)ifA[i][j]>0]edges.sort()uf=UnionFind(n)mst_edges=[]mst_weight=0forweight,u,vinedges:ifuf.find(u)!=uf.find(v):uf.union(u,v)mst_edges.append((u,v))mst_weight+=weightreturnmst_edges,mst_weight#示例图的邻接矩阵A=[[0,10,6,5],[10,0,0,15],[6,0,0,4],[5,15,4,0]]#计算最小生成树mst_edges,mst_weight=kruskal(A)#显示结果print('最小生成树的边:',mst_edges)print('最小生成树的权重:',mst_weight)注意的细节知识点初始化确保并查集正确初始化，每个顶点的父节点为自身。边的收集与排序收集所有边的信息，并按权值从小到大排序，以便于后续选择最小权值边。并查集查找函数使用递归查找顶点的根节点，并进行路径压缩，提高查找效率。边的选择与合并在选择边时，确保不会形成圈，使用并查集的查找和合并操作。更新最小生成树的边和权重，确保最小生成树的正确性。四、钢管订购和运输问题1.问题描述需要从多个钢厂订购钢管，并将其运输到施工地点，铺设天然气主管道。图中表示钢厂、枢纽点和施工地点，边的权值表示运输距离。2.问题分析分解为两个子问题：从钢厂到枢纽点的运输和从枢纽点到施工地点的铺设。需要综合考虑订购费用、运输费用和铺设费用。3.模型的建立与求解运费矩阵的计算模型：计算从供应点到需求点的最小购运费。总费用的数学规划模型：包括订购费用、运输费用和铺设管道的运费。模型求解：利用Floyd算法计算最短路径，运用数学规划模型优化总费用。MATLAB代码实例%MATLAB代码%构造铁路距离赋权图functiondist=floyd_warshall(A)n=size(A,1);dist=A;dist(dist==0)=inf;dist(1:n+1:end)=0;fork=1:nfori=1:nforj=1:nifdist(i,k)+dist(k,j)