图论与其Matlab实现

Author：怪使
发布时间：August 16, 2019
1016views
No comments
5302 words
Categories：数学建模

图与网络模型及方法

1 概论

图论的起源就不必多说了，来自于欧拉（大神，盲了还能心算微积分和级数求和）。而树则来源于电网络方程或者是计数同分异构体。而最为知名的莫过于哈密尔顿的“周游世界”游戏：找到一个连通图中的生成圈。图论目前应用广泛。

所谓“图”指的是某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了
一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。

图与网络是运筹学中的一个经典和重要的分支，所研究的
问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。

首先举一些例子来了解什么叫网络优化问题：

例1：最短路问题（SPP）

一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。

例2：公路连接问题

某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？

例3：指派问题

一家公司经理准备安排 N 名员工去完成 N 项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？

例4：中国邮递员问题（CPP）

一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？

例5：旅行商问题（TSP）

一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？

例6：运输问题

某种原材料有 M 个产地，现在需要将原材料从产地运往 N 个使用这些原材料的工厂。假定 M 个产地的产量和 N 家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？

上述问题有两个共同的特点：

它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化问题。
它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络。

与图和网络相关的最优化问题就是网络最优化称为网络优化问题。（也成为网络流或者网络流规划）

2 图与网络的基本概念

2.1 无向图

这里主要注意，无向图是一个无序对集合构成的二元组，且要注意顶点集，顶点，边集，边的概念，还有相邻概念。

边上赋权的无向图称为赋权无向图或无向网络

一个图称为有限图：它的顶点集和边集都有限。图$G$的顶点数用$v(G)$表示，而边数则用$\varepsilon(G)$表示

端点重合为一点的边称为环。

一个图称为简单图:既没有环也没有两条边连接同一对顶点。

2.2 有向图

这里主要注意，有向图是一个有序对集合构成的二元组，主要就是有序,这里由于有序，之前的边被称之为弧，且有弧尾和弧头之分，从尾部指向头部。

有向图和无向图的主要区别就在于方向，所以对边和弧这两个概念有所区分。

2.3 完全图，二分图

每一对不同的顶点都有一条边相连的简单图称之为完全图。$n$个顶点的完全图即为$K_n$。

二分图的概念则是指：顶点集可以分成两个非空子集，而且这两个非空子集中没有相邻的顶点对。（图中每条边依附的两个顶点都分别属于这两个互不相交的子集，两个子集内的顶点不相邻。）

完全二分图：在二分图的基础上，要求使得第一个集合中的所有顶点都与第二个集合中的所有顶点相连。

2.4 子图

子图概念：图$H$为图$G$的子图，记作$H{\subset}G$，要求：$V(H){\subset}V(G)$，且$E(H){\subset}E(G)$。相对的，图$G$则为图$H$的母图。这里揭示了：要求是顶点集包含与边集包含同时成立。

图$G$的支撑子图(生成子图)：指的是满足子图条件下，且$V(G)=V(H)$:也就是满足了顶点集相同，边集包含于的关系。

2.5 顶点的度

设$v{\in}V(G)$,图$G$中与$v$关联的变数（每个环算两条边）称为$v$度，记作$d(v)$。若$d(v)$为奇数，则称$v$为奇顶点；若$d(v)$为偶数，则称$v$为偶顶点。关于顶点的度，我们有这样的规律：

$$ \sum_{v{\in}V}d(v)=2\varepsilon\\ 任意一个图的奇顶点的个数是偶数 $$

2.6 图与网络的数据结构

网络优化研究的是网络上的各种优化模型与算法。为了在计算机上实现网络优化的算法，首先我们必须有一种方法（即数据结构）在计算机上来描述图与网络。一般来说，算法的好坏与网络的具体表示方法，以及中间结果的操作方案是有关系的。这里我们介绍计算机上用来描述图与网络的 5 种常用表示方法：邻接矩阵表示法、关联矩阵表示法、弧表表示法、邻接表表示法和星形表示法。

P.S：下面的讨论若没有特殊说明，均为简单有向图。

邻接矩阵表示法

邻接矩阵表示法是将图以邻接矩阵的形式存储在计算机中。图$G=(V,A)$的邻接矩阵$C$定义：是一个0-1方阵，若两个顶点之间有一条弧，则邻接矩阵中的对应元素为1，否则为0。

优点是表示直接简单，缺点则是在网络比较稀疏的情况下，0元占比比较大，表示会浪费大量的存储空间，增加了在网络中查找弧的时间。

关联矩阵表示法

关联矩阵表示法是将图以关联矩阵的形式存储在计算机中。图$G=(V,A)$的关联矩阵$B$是这样定义的：$B$是一个普通矩阵（非方阵），而且元素为-1，0，1；给定了顺序：在关联矩阵中，每行对应于图的一个节点，每列对应于图的一条弧。如果一个节点是一条弧的起点，则关联矩阵中对应的元素为 1；如果一个节点是一条弧的终点，则关联矩阵中对应的元素为 − 1 ；如果一个节点与一条弧不关联，则关联矩阵中对应的元素为 0。

这里首先要筛选出总共有多少条对应弧，然后依次确定该点是否为该弧的起点还是终点还是没有关联。

优点是表示简单直接，但是同样浪费存储，但是有许多比较好的理论性质。

弧表表示法

弧表表示法将图以弧表的形式存储在计算机中。所谓图的弧表，也就是图的弧集合中的所有有序对。弧表表示法直接列出所有弧的起点和终点，共需$2m$个存储单元，因此当网络比较稀疏时比较方便。此外，对于网络图中每条弧上的权，也要对应地用额外的存储单元表示。

弧表表示法，同样也需要把所有的对应弧找出来，然后记录好对应的起点和终点（以及权重）即可。

为了便于检索，一般按照起点、终点的字典序顺序存储弧表。

邻接表表示法

邻接表表示法将图以邻接表的形式存储在计算机中。所谓图的邻接表，也就是图的所有节点的邻接表的集合；而对每个节点，它的邻接表就是它的所有出弧。邻接表表示法就是对图的每个节点，用一个单向链表列出从该节点出发的所有弧，链表中每个单元对应于一条出弧。为了记录弧上的权，链表中每个单元除列出弧的另一个端点外，还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数组表示。

每个节点是一个单向链表，从起点指向终点，同一个起点的按照字典顺序排列存储并赋予指针，中间还可用开辟空间存储权重。

星形表示法

星形表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点，它也是记录从该节点出发的所有弧，但它不是采用单向链表而是采用一个单一的数组表示。实际上相当于给所有的弧给出一个顺序与编号，只是从同一结点出发的弧的顺序可以任意排列。而且为了能够快速检索从每个节点出发的所有弧，我们一般还用一个数组记录每个节点出发的弧的起始地址（即弧的编号）。

前向星形表示法有利于快速检索每个节点的所有出弧，但不能快速检索每个节点的所有入弧。为了能够快速检索每个节点的所有入孤，可以采用反向星形表示法。

对于网络图的表示法：

1，星形表示法和邻接表表示法在实际算法实现中都是经常采用的。星形表示法的优点是占用的存储空间较少，并且对那些不提供指针类型的语言（如 FORTRAN 语言等）也容易实现。邻接表表示法对那些提供指针类型的语言（如 C 语言等）是方便的，且增加或删除一条弧所需的计算工作量很少，而这一操作在星形表示法中所需的计算工作量较大（需要花费$O(m)$的计算时间）。有关“计算时间”的观念是网络优化中需要考虑的一个关键因素。

2，当网络不是简单图，而是具有平行弧（即多重弧）时，显然此时邻接矩阵表示法是不能采用的。其他方法则可以很方便地推广到可以处理平行弧的情形。

3，上述方法可以很方便地推广到可以处理无向图的情形，但由于无向图中边没有方向，因此可能需要做一些自然的修改。例如，可以在计算机中只存储邻接矩阵的一半信息（如上三角部分），因为此时邻接矩阵是对称矩阵。无向图的关联矩阵只含有元素0 和 +1 ，而不含有 −1 ，因为此时不区分边的起点和终点。又如，在邻接表和星形表示法中，每条边会被存储两次，而且反向星形表示显然是没有必要的，等等。

2.7 轨与连通

这里给出了道路，起点和终点，内部顶点的概念。

从而引出迹的概念，道路的边互不相同。从而引出轨的概念，道路的顶点互不相同。引出闭的概念：如果道路有正的长且起点和重点相同。起点和终点重合的轨叫做圈。

两个顶点之间若存在道路，则称这两个顶点连通。顶点之间最短的轨的长度叫做两个顶点之间的距离，记为$d(u,v)$。

连通图：图的任意两个顶点都是连通的。

故而有以下的规律：
1，图$P$是一条轨的充要条件是$P$是连通的，且有两个一度的顶点，其余顶点的度为2。

2，图$C$是一个圈的充要条件是$C$是各顶点的度均为2的连通图。

3 应用——最短路问题

3.1 两个指定顶点之间的最短路径

问题如下:给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找出一条最短的铁路线。

已知成熟算法：狄克斯特拉（$Dijkstra$）算法

基本思想是先取定一个顶点，从远到近做一个排序，依次求得该点到图的各个顶点的最短路和距离，直到遍历所有顶点，算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。

clc,clear
a=zeros(6);   %6*6阶的零矩阵
a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;
a(2,3)=15;a(2,4)=20;a(2,6)=25;
a(3,4)=10;a(3,5)=20;
a(4,5)=10;a(4,6)=25;
a(5,6)=55;  %构建路线图矩阵
a=a+a';     %用对称的方式构建矩阵
a(find(a==0))=inf;    %强制将0转为无穷小
pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));  %初始化p标号，选取第一个顶点写入标号顺序，初始化标号顶点索引数组
d(1:length(a))=inf;d(1)=0;temp=1;     %初始化最短路径距离数组（以便比较），选取第一个顶点的最短路径距离写入，给一个暂存变量
while sum(pb)<length(a)   %条件：当未遍历完所有顶点时执行
 tb=find(pb==0);          
 d(tb)=min(d(tb),d(temp)+a(temp,tb));    %找到最小的路径并存入
 tmpb=find(d(tb)==min(d(tb)));
 temp=tb(tmpb(1));
 pb(temp)=1;                             %p标号该顶点已经被遍历过
 index1=[index1,temp];                   %记录顶点标号顺序
 temp2=find(d(index1)==d(temp)-a(temp,index1));   
 index2(temp)=index1(temp2(1));          %记录索引标号顺序
end
d, index1, index2

该算法仅仅给出了第一个顶点到其他顶点的最短路径。

3.2 两个指定顶点之间最短路问题的数学表达式

假设有向图有$n$个顶点，现需要求从顶点1到顶点$n$的最短路。设$W=(w_{ij})_{n*n}$为赋权邻接矩阵，其分量为：

$$ w_{ij}= \begin{cases} w(v_iv_j),\quad v_iv_j{\in}E\\ \infty,\quad 其它\\ \end{cases} $$

决策变量为$x_{ij}$，当$x_{ij}=1$，说明弧$v_iv_j$位于顶点1到顶点n的路上；否则$x_ij=0$。（表示此路不通）其数学规划表达式为：

$$ \min\quad \sum_{v_iv_j {\in} E}w_{ij}x_{ij}\\ s.t. \sum^n_{j=1,v_ivj{\in}E}x_{ij}-\sum^n_{j=1,v_jvi{\in}E}x_{ji}=\begin{cases} 1,\quad i=1\\ -1, \quad i=n\\ 0, \quad i\not=1,n \end{cases}\\ x_{ij}=0或1 $$

3.3 每对顶点之间的最短路径

当然也可以对每个顶点调用$Dijkstra$算法，这样就可以查出每对顶点之间的最短路径。但是这种算法的时间复杂度为$O(n^3)$。而这里采用$Floyd$算法。

该算法的思想是：递推产生一个矩阵序列$A_0,A_1,\cdots,A_k,\cdots,A_n$,其中$A_k(i,j)$表示从顶点$v_i$到顶点$v_j$的路径上所经过的顶点序号不超过$k$的最短路径长度。

计算时用迭代公式：

$$ A_k(i,j)=\min(A_{k-1}(i,j),A_{k-1}(i,k)+A_{k-1}(k,j)) $$

$k$是迭代次数，$i,j,k=1,2,\cdots,n$。

最后，当$k=n$时，$A_n$就是各顶点之间的最短路径。

clear;clc;
n=6; a=zeros(n);
a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;
a(2,3)=15;a(2,4)=20;a(2,6)=25; a(3,4)=10;a(3,5)=20;
a(4,5)=10;a(4,6)=25; a(5,6)=55;
a=a+a'; M=max(max(a))*n^2; %M为充分大的正实数
a=a+((a==0)-eye(n))*M;
path=zeros(n);
for k=1:n     %进入迭代
 for i=1:n
 for j=1:n
 if a(i,j)>a(i,k)+a(k,j)    %迭代公式
 a(i,j)=a(i,k)+a(k,j);
 path(i,j)=k;   %记录最短路径
 end
 end
 end
end
a, path

4 树

4.1 基本概念

连通的无圈图叫做树，记为$T$。若图$G$满足$V(G)=V(T),E(T) \subset E(G)$,则称$T$为图$G$的生成树。图$G$连通的充分必要条件为$G$有生成树。一个连通图的生成树的个数有很多，用$\tau(G)$表示$G$的生成树的个数，则有公式

$$ 公式 \quad (Gaylay) \tau(K_n)=n^{n-2}\\ 公式 \quad \tau(G)=\tau(G-e)+\tau(G{\cdot}e)。 $$

其中$G-e$表示从$G$上删除边$e$,$G{\cdot}e$表示把$e$的长度收缩为0所得到的图。

树有下面常用的五个充要条件：

定理1：

$G$是树当且仅当$G$中任二顶点之间有且仅有一条轨道
$G$是树当且仅当$G$无圈，且$\epsilon=v-1$
$G$是树当且仅当$G$连通，且$\epsilon=v-1$
$G$是树当且仅当$G$连通，且$\forall e{\in} E(G)$,$G-e$不连通。
$G$是树当且仅当$G$无圈，$\forall e{\notin}E(G)$,$G+e$恰有一个圈。

4.2 应用——连线问题

欲修筑连接$n$个城市的铁路，已知$i$城与$j$城之间的铁路造价为 $C_{ij}$，设计一个线路图，使总造价最低。

连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生成树叫做最小生成树。

4.2.1 prim算法构造最小生成树

设置两个集合$P$和$Q$ ,其中$P$用于存放$G$的最小生成树中的顶点，集合$Q$存放$G$的最小生成树中的边。令集合$P$的值为$P={v_1}$(假设构造最小生成树时，从顶点$v_1$出发)，集合$Q$的初值为$Q=\Phi$。

该算法的思想是：从所有的$p{\in}P,v{\in}V-P$的边中，选取具有最小权值的边$pv$，将顶点$v$加入集合$P$中，将边$pv$加入集合$Q$中，如此不断重复，直到$P=V$时，最小生成树构造完毕，这时集合$Q$中包含了最小生成树的所有边。

clc;clear;
a=zeros(7);
a(1,2)=50; a(1,3)=60;
a(2,4)=65; a(2,5)=40;
a(3,4)=52;a(3,7)=45;
a(4,5)=50; a(4,6)=30;a(4,7)=42;
a(5,6)=70;
a=a+a';a(find(a==0))=inf;    %初始化权值矩阵
result=[];p=1;tb=2:length(a);   %最小生成树矩阵，取第一个顶点
while length(result)~=length(a)-1  %遍历所有
 temp=a(p,tb);temp=temp(:);
 d=min(temp);                        %取到最小权值边
 [jb,kb]=find(a(p,tb)==d);
 j=p(jb(1));k=tb(kb(1));      
 result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];   %塞入该矩阵
end
result

4.2.2 Kruskal算法构造最小生成树

该算法步骤如下：

选$e_1{\in}E(G),$使得$w(e_1)=\min$
若$e_1,e_2,\cdots,e_i$已经选好，则从$E(G)-\left\{e_1,e_2,\cdots,e_i\right\}$中选取$e_{i+1}$，使得
1. $G[\left\{e_1,e_2,\cdots,e_i,e_{i+1}\right\}]$中无圈，且
2. $w(e_{i+1})=\min$
直到选得$e_{v-1}$为止

clc;clear;
a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40;
a(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;
a(4,7)=42; a(5,6)=70;
[i,j,b]=find(a);
data=[i';j';b'];index=data(1:2,:);%index记录各边端点的信息，选中后，交换序号较大的一端，可以做到收敛
loop=max(size(a))-1;
result=[];
while length(result)<loop  %遍历各个顶点
 temp=min(data(3,:));
 flag=find(data(3,:)==temp);
 flag=flag(1);
 v1=data(1,flag);v2=data(2,flag);
 if index(1,flag)~=index(2,flag)
 result=[result,data(:,flag)];
 end
 index(find(index==v2))=v1;
 data(:,flag)=[];
 index(:,flag)=[];
end
result

Last modification：August 16th, 2019 at 02:13 pm

如果觉得我的文章对你有用，请随意赞赏

图论与其Matlab实现

怪使 • 2019 年 08 月 16 日

图与网络模型及方法

1 概论

首先举一些例子来了解什么叫网络优化问题：

例1：最短路问题（SPP）

例2：公路连接问题

例3：指派问题

例4：中国邮递员问题（CPP）

一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？

例5：旅行商问题（TSP）

一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？

例6：运输问题

上述问题有两个共同的特点：

它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化问题。
它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络。

与图和网络相关的最优化问题就是网络最优化称为网络优化问题。（也成为网络流或者网络流规划）

2 图与网络的基本概念

2.1 无向图

这里主要注意，无向图是一个无序对集合构成的二元组，且要注意顶点集，顶点，边集，边的概念，还有相邻概念。

边上赋权的无向图称为赋权无向图或无向网络

一个图称为有限图：它的顶点集和边集都有限。图$G$的顶点数用$v(G)$表示，而边数则用$\varepsilon(G)$表示

端点重合为一点的边称为环。

一个图称为简单图:既没有环也没有两条边连接同一对顶点。

2.2 有向图

这里主要注意，有向图是一个有序对集合构成的二元组，主要就是有序,这里由于有序，之前的边被称之为弧，且有弧尾和弧头之分，从尾部指向头部。

有向图和无向图的主要区别就在于方向，所以对边和弧这两个概念有所区分。

2.3 完全图，二分图

每一对不同的顶点都有一条边相连的简单图称之为完全图。$n$个顶点的完全图即为$K_n$。

完全二分图：在二分图的基础上，要求使得第一个集合中的所有顶点都与第二个集合中的所有顶点相连。

2.4 子图

图$G$的支撑子图(生成子图)：指的是满足子图条件下，且$V(G)=V(H)$:也就是满足了顶点集相同，边集包含于的关系。

2.5 顶点的度

$$ \sum_{v{\in}V}d(v)=2\varepsilon\\ 任意一个图的奇顶点的个数是偶数 $$

2.6 图与网络的数据结构

P.S：下面的讨论若没有特殊说明，均为简单有向图。

邻接矩阵表示法

优点是表示直接简单，缺点则是在网络比较稀疏的情况下，0元占比比较大，表示会浪费大量的存储空间，增加了在网络中查找弧的时间。

关联矩阵表示法

这里首先要筛选出总共有多少条对应弧，然后依次确定该点是否为该弧的起点还是终点还是没有关联。

优点是表示简单直接，但是同样浪费存储，但是有许多比较好的理论性质。

弧表表示法

弧表表示法，同样也需要把所有的对应弧找出来，然后记录好对应的起点和终点（以及权重）即可。

为了便于检索，一般按照起点、终点的字典序顺序存储弧表。

邻接表表示法

每个节点是一个单向链表，从起点指向终点，同一个起点的按照字典顺序排列存储并赋予指针，中间还可用开辟空间存储权重。

星形表示法

对于网络图的表示法：

2.7 轨与连通

这里给出了道路，起点和终点，内部顶点的概念。

两个顶点之间若存在道路，则称这两个顶点连通。顶点之间最短的轨的长度叫做两个顶点之间的距离，记为$d(u,v)$。

连通图：图的任意两个顶点都是连通的。

故而有以下的规律：
1，图$P$是一条轨的充要条件是$P$是连通的，且有两个一度的顶点，其余顶点的度为2。

2，图$C$是一个圈的充要条件是$C$是各顶点的度均为2的连通图。

3 应用——最短路问题

3.1 两个指定顶点之间的最短路径

问题如下:给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找出一条最短的铁路线。

已知成熟算法：狄克斯特拉（$Dijkstra$）算法

clc,clear
a=zeros(6);   %6*6阶的零矩阵
a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;
a(2,3)=15;a(2,4)=20;a(2,6)=25;
a(3,4)=10;a(3,5)=20;
a(4,5)=10;a(4,6)=25;
a(5,6)=55;  %构建路线图矩阵
a=a+a';     %用对称的方式构建矩阵
a(find(a==0))=inf;    %强制将0转为无穷小
pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));  %初始化p标号，选取第一个顶点写入标号顺序，初始化标号顶点索引数组
d(1:length(a))=inf;d(1)=0;temp=1;     %初始化最短路径距离数组（以便比较），选取第一个顶点的最短路径距离写入，给一个暂存变量
while sum(pb)<length(a)   %条件：当未遍历完所有顶点时执行
 tb=find(pb==0);          
 d(tb)=min(d(tb),d(temp)+a(temp,tb));    %找到最小的路径并存入
 tmpb=find(d(tb)==min(d(tb)));
 temp=tb(tmpb(1));
 pb(temp)=1;                             %p标号该顶点已经被遍历过
 index1=[index1,temp];                   %记录顶点标号顺序
 temp2=find(d(index1)==d(temp)-a(temp,index1));   
 index2(temp)=index1(temp2(1));          %记录索引标号顺序
end
d, index1, index2

该算法仅仅给出了第一个顶点到其他顶点的最短路径。

3.2 两个指定顶点之间最短路问题的数学表达式

假设有向图有$n$个顶点，现需要求从顶点1到顶点$n$的最短路。设$W=(w_{ij})_{n*n}$为赋权邻接矩阵，其分量为：

$$ w_{ij}= \begin{cases} w(v_iv_j),\quad v_iv_j{\in}E\\ \infty,\quad 其它\\ \end{cases} $$

决策变量为$x_{ij}$，当$x_{ij}=1$，说明弧$v_iv_j$位于顶点1到顶点n的路上；否则$x_ij=0$。（表示此路不通）其数学规划表达式为：

3.3 每对顶点之间的最短路径

当然也可以对每个顶点调用$Dijkstra$算法，这样就可以查出每对顶点之间的最短路径。但是这种算法的时间复杂度为$O(n^3)$。而这里采用$Floyd$算法。

计算时用迭代公式：

$$ A_k(i,j)=\min(A_{k-1}(i,j),A_{k-1}(i,k)+A_{k-1}(k,j)) $$

$k$是迭代次数，$i,j,k=1,2,\cdots,n$。

最后，当$k=n$时，$A_n$就是各顶点之间的最短路径。

clear;clc;
n=6; a=zeros(n);
a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;
a(2,3)=15;a(2,4)=20;a(2,6)=25; a(3,4)=10;a(3,5)=20;
a(4,5)=10;a(4,6)=25; a(5,6)=55;
a=a+a'; M=max(max(a))*n^2; %M为充分大的正实数
a=a+((a==0)-eye(n))*M;
path=zeros(n);
for k=1:n     %进入迭代
 for i=1:n
 for j=1:n
 if a(i,j)>a(i,k)+a(k,j)    %迭代公式
 a(i,j)=a(i,k)+a(k,j);
 path(i,j)=k;   %记录最短路径
 end
 end
 end
end
a, path

4 树

4.1 基本概念

$$ 公式 \quad (Gaylay) \tau(K_n)=n^{n-2}\\ 公式 \quad \tau(G)=\tau(G-e)+\tau(G{\cdot}e)。 $$

其中$G-e$表示从$G$上删除边$e$,$G{\cdot}e$表示把$e$的长度收缩为0所得到的图。

树有下面常用的五个充要条件：

定理1：

$G$是树当且仅当$G$中任二顶点之间有且仅有一条轨道
$G$是树当且仅当$G$无圈，且$\epsilon=v-1$
$G$是树当且仅当$G$连通，且$\epsilon=v-1$
$G$是树当且仅当$G$连通，且$\forall e{\in} E(G)$,$G-e$不连通。
$G$是树当且仅当$G$无圈，$\forall e{\notin}E(G)$,$G+e$恰有一个圈。

4.2 应用——连线问题

欲修筑连接$n$个城市的铁路，已知$i$城与$j$城之间的铁路造价为 $C_{ij}$，设计一个线路图，使总造价最低。

连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生成树叫做最小生成树。

4.2.1 prim算法构造最小生成树

clc;clear;
a=zeros(7);
a(1,2)=50; a(1,3)=60;
a(2,4)=65; a(2,5)=40;
a(3,4)=52;a(3,7)=45;
a(4,5)=50; a(4,6)=30;a(4,7)=42;
a(5,6)=70;
a=a+a';a(find(a==0))=inf;    %初始化权值矩阵
result=[];p=1;tb=2:length(a);   %最小生成树矩阵，取第一个顶点
while length(result)~=length(a)-1  %遍历所有
 temp=a(p,tb);temp=temp(:);
 d=min(temp);                        %取到最小权值边
 [jb,kb]=find(a(p,tb)==d);
 j=p(jb(1));k=tb(kb(1));      
 result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];   %塞入该矩阵
end
result

4.2.2 Kruskal算法构造最小生成树

该算法步骤如下：

选$e_1{\in}E(G),$使得$w(e_1)=\min$
若$e_1,e_2,\cdots,e_i$已经选好，则从$E(G)-\left\{e_1,e_2,\cdots,e_i\right\}$中选取$e_{i+1}$，使得
1. $G[\left\{e_1,e_2,\cdots,e_i,e_{i+1}\right\}]$中无圈，且
2. $w(e_{i+1})=\min$
直到选得$e_{v-1}$为止

clc;clear;
a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40;
a(3,4)=52;a(3,7)=45; a(4,5)=50; a(4,6)=30;
a(4,7)=42; a(5,6)=70;
[i,j,b]=find(a);
data=[i';j';b'];index=data(1:2,:);%index记录各边端点的信息，选中后，交换序号较大的一端，可以做到收敛
loop=max(size(a))-1;
result=[];
while length(result)<loop  %遍历各个顶点
 temp=min(data(3,:));
 flag=find(data(3,:)==temp);
 flag=flag(1);
 v1=data(1,flag);v2=data(2,flag);
 if index(1,flag)~=index(2,flag)
 result=[result,data(:,flag)];
 end
 index(find(index==v2))=v1;
 data(:,flag)=[];
 index(:,flag)=[];
end
result

图与网络模型及方法

1 概论

2 图与网络的基本概念

2.1 无向图

2.2 有向图

2.3 完全图，二分图

2.4 子图

2.5 顶点的度

2.6 图与网络的数据结构

2.7 轨与连通

3 应用——最短路问题

3.1 两个指定顶点之间的最短路径

3.2 两个指定顶点之间最短路问题的数学表达式

3.3 每对顶点之间的最短路径

4 树

4.1 基本概念

4.2 应用——连线问题

4.2.1 prim算法构造最小生成树

4.2.2 Kruskal算法构造最小生成树