2025年数学建模笔记 day-07

科技前沿 • 2025-03-02 20:16 • 阅读 45

大家好，我是讯享网，很高兴认识大家。

第七章图论模型

一、图的生成

1. 画无向图：graph

例1：

clc,clear a=zeros(5); %邻接矩阵初始化 a(1,[2,4])=1; a(2,[3,5])=1; %输出邻接矩阵的上三角元素 a(3,[4,5])=1; b=graph(a,'upper') %等价于 aa=a+a' b=graph(aa) plot(b)

讯享网

2. 画有向图: digraph

例2：

讯享网clc ,clear a=zeros(4); %邻接矩阵的初始化 a(1,[2,3])=1; a(3,4)=1; a(4,1)=1; b=digraph(a) %构造有向图 plot(b)

3.其他命令

G=graph() %创建空的无向图对象 G=graph(A) %使用邻接矩阵A创建赋权无向图 G=graph(A,nodes) %使用邻接矩阵A和节点名称nodes创建赋权无向图 G=graph(s,t) %使用节点对组s、t创建无向图 G=graph(s,t,weights) %使用节点对组s、t和权重向量weights创建赋权无向图 G=graph(s,t,weights,nodes) %使用字符向量元胞数组或字符数组nodes指定节点名称 G=graph(s,t,weights,num) %使用数值标量num指定图中的节点数 G=graph(A[,nodes],type) %仅使用A的上或下三角形构造赋权图，type可以是'upper''lower'

例3：画出一个60个顶点的3正则图(每个顶点的度都为3)。

讯享网G=graph(bucky); p=plot(G)

二、数据存储结构

Matlab存储网络的相关数据时，使用了稀疏矩阵，这有利于在存储大规模稀疏网络时节省存储空间。

附：a([1,7,18])=1 %是指一列一列地竖着看，第1个，第7个和第18个为1

例1：

讯享网

clc,clear,close all a=zeros(4); a([4,5,9,15])=1; %邻接矩阵初始化 nodes=cellstr(strcat('v',int2str([1:4]'))) G=digraph(a,nodes); plot(G,'LineWidth',1.5,'Layout','circle','NodeFontSize',15) W1=adjacency(G) %导出邻接矩阵的稀疏矩阵 W2=incidence(G) %导出关联矩阵的稀疏矩阵 ww1=full(W1) %导出全矩阵 ww2=full(W2) %导出全矩阵

三、生成树

1. n个顶点的完全图有 $n^{n-2}$ 个生成树

例1：

讯享网clc,clear, close all a=zeros(5); a(1,[2:4])=[5,3,7]; a(2,[3,5])=[8,4]; a(3,[4,5])=[1,6]; a(4,5)=2; %输入邻接矩阵的三角元素 G=graph(a,'Upper') %graph生成的是一个结构数组 h=plot(G,'Layout','force','EdgeLabel',G.Edges.Weight) %生成图像 T=minspantree(G) % 求最小生成树（生成的也是一个结构数组） L=sum(T.Edges.Weight)% 计算最小的总权值 highlight(h,T) % 标出最小生成树

注意!!!: minspantree默认使用的是 Prim's algorithm,如果想要使用 Kruskal's algorithm 必须得加'sparse'。

附：find(t) t-矩阵作用：查找非0元素的索引和值

同理： find(~t) 作用：查找值为0的元素的索引和值

all(t) 作用：确定所有的数组元素是为非零还是true

setdiff(A,B) 作用:查找A中存在，B中不存在的值

例2:

clc,clear,close all a=zeros(5);a(1,[2:4])=[5,3,7];a(2,[3,5])=[8,4]; a(3,[4,5])=[1,6];a(4,5)=2;%输入邻接矩阵上三角元素 w=a+a' ; w(w==0)=10^6; n=size(w,1); prob=optimproblem; x=optimvar('x',n,n,'Type','integer','LowerBound',0,'UpperBound',1); u=optimvar('u',n,'LowerBound',0); prob.Objective=sum(sum(w.*x)); prob.Constraints.con1=[sum(x(:,[2,n]))'==1;u(1)==0]; con2=[1<=sum(x(1,:));1<=u(2:n);u(2:n)<=n-1]; for i= 1:n for j =2:n con2=[con2;u(i)-u(j)+n*x(i,j)<=n-1]; end end prob.Constraints.con2=con2; [sol,fval,flag,out]=solve(prob) [i,j]=find(sol.x); ind = [i';j'] %输出树的顶点编号

2025年数学建模笔记 day-07

第七章 图论模型

一、图的生成

二、数据存储结构

三、生成树

相关推荐

第七章图论模型