图论中几个典型问题的求解.ppt

图论中几个典型问题的求解§1图的基本概念图是一种直观形象地描述已知信息的方式，它使事物之间的关系简洁明了，是分析问题的有用工具，很多实际问题可以用图来描述。一、图的定义二、基本概念在无向图中与顶点v关联的边的数目（环算两次）称为该顶点的度（或次数），记为d(v)。度为奇数的顶点叫做奇点，度为偶数的顶点叫做偶点。在有向图中，从顶点v引出的边的数目称为该顶点的出度，记为d+(v)，从顶点v引入的边的数目称为该顶点的入度，记为d-(v)，而d(v)＝d+(v)+d-(v)称为v的次数。在图中，两个顶点u和v之间由顶点和边构成的交错序列（使u和v相通）称为链（通道），没有重复边的通道称为迹，起点与终点重合的通道称为闭通道，不重合的称为开通道，没有重复顶点（必然边也不重复）的开通道称为路，起点与终点重合的路称为圈（回路）．包含奇数个顶点（或边）的圈称为奇圈，包含偶数个顶点（或边）的圈称为偶圈。如果顶点u和v之间存在一条路，则称u和v是连通的，任意两个顶点都连通的图称为连通图．无圈的连通图称为树，如果一棵树T包含了图G的所有顶点，称T为G的生成树．如果图G的每条边e都对应一个实数C(e)，称C(e)为该边e的权，称图G为赋权图．通常称赋权的有向图为网络．

图中边e6和e7是平行边，e9是环，顶点v4是悬挂点，边e4是悬挂边．§2最短路问题最短路问题是图论应用的基础，很多实际问题，如线路的布设、运输规划、运输网络最小费用流等问题，都可以通过建立最短路模型来求解。有些有深度的图与网络优化问题，如旅行售货商、中国邮递员等问题，需要在首先求出任意两点之间最短路的基础上解决。
一、最短路的概念
给定一个连通的赋权图G={V,E}，设R是连接节点vi和vj的一条路，该路的权定义为路中所有各边权之和，如果路R在所有连接节点vi和vj的路中权最小，则称它为vi和vj间的最短路。二、任意两点之间的最短路(Floyd算法)
Floyd算法利用距离矩阵进行迭代运算，可以一次性地求出任意两点之间的最短路，该方法的思路有创意，计算量小，编程较简单，又称矩阵求解法。
1．算法原理
设A=[aij]m×n是图的权矩阵（也称带权邻接矩阵），其中aij是图上连接顶点i和j的边的权，如果两顶点之间没有直接相连的边（即两顶点不相邻），则aij=∞。令矩阵D(0)=A，作为迭代的初始矩阵，从它出发按照一定规则求D(1)，又由D(1)按照类似的规则求D(2)，依此类推进行迭代直至求出D(n)，设矩阵D(m)的元素为dij(m)，迭代规则为：

上式表示dij(1)在dij(0)以及从顶点vi经过顶点v1到vj的权之和di1(0)+d1j(0)两者之中选择最短长度。依此规则迭代。上式表示dij(2)在dij(1)以及从顶点vi经过顶点v2到vj的权之和di2(1)+d2j(1)两者之中选择最短长度。依此类推，迭代公式为：

上式表示dij(m)在dij(m-1)以及从顶点vi经过顶点vm到vj的权之和dim(m-1)+dmj(m-1)两者之中选择最短长度。当m=n时结束迭代。2．程序设计
先编写Flody算法的子程序（函数）如下：
Function[D,R]=floyd(a)
n=size(a,1);D=a;%D是初始矩阵
fori=1:n
forj=1:n
R(i,j)=j;
end
endfork=1:n
fori=1:n
forj=1:n
ifD(i,k)+D(k,j)<D(i,j)
D(i,j)=D(i,k)+D(k,j);%在循环中进行矩阵迭代
R(i,j)=R(i,k);%R是路径矩阵
end
end
end
end
D,R%输出最短路矩阵和最短路的路径矩阵。以上程序是通用程序，只需输入初始距离矩阵，就能输出最短路矩阵以及最短路的路径矩阵，将程序以文件名floyd.m存盘。
例1以2007年研究生数学建模竞赛C题为例，已知16个邮政支局的初始距离矩阵，求任意两个节点之间的最短路。
解：编写主程序如下：
a=[0,27,44,17,11,27,42,inf,inf,inf,20,25,21,21,18,27,inf;
…………………………………………
inf,inf,inf,inf,30,inf,inf,inf,21,13,20,inf,inf,inf,inf,9,0];[D,R]=floyd(a);输入数据中的inf表示无穷大（两个顶点之间没有边直接相连）。
运行以上程序，求得最短路矩阵D和最短路的路径矩阵。此处省略结果。§3最小生成树一、最小生成树的概念
树是图论中的一种简单而重要的图，连通并且无圈的无向图称为树，常用T表示。树有以下性质：
(1)树中任意两点之间有唯一路径；
(2)树的边数等于顶点数减1；
(3)在树中删去任意一条边就不连通；
(4)