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

《图论中几个典型问题的求解》由会员分享，可在线阅读，更多相关《图论中几个典型问题的求解（161页珍藏版）》请在金锄头文库上搜索。

1、图论中几个典型 问题的求解1 图的基本概念图是一种直观形象地描述已知信息的方 式，它使事物之间的关系简洁明了，是分 析问题的有用工具，很多实际问题可以用 图来描述。一、图的定义 图论是以图为研究对象的数学分支，在图论中 ，图由一些点和点之间的连线所组成 称图中的点为顶点（节点），称连接顶点的没 有方向的线段为边，称有方向的线段为弧 用V=v1,v2,表示全体顶点的集合，用 E=e1,e2, 表示全体边的集合，如果对于E中的 任一条边ek，在V中都有一对顶点(vi,vj)和它对应 ，则称由V和E组成的集体为一个图，记为 G=V,E，简写为G二、基本概念 点与边相连接称为关联，与边e关联的顶点称为

2、 该边的端点，与同一条边关联的两个顶点称为相 邻顶点，与同一个顶点关联的边称为相邻边具 有相同顶点的边称为平行边，两个端点重合的边 称为环所有线段都没有方向的图称为无向图， 所有线段都有方向的图称为有向图，既有边也有 弧的图称为混合图在无向图中，没有环和平行 边的图称为简单图，任意两个顶点之间都有一条 边相连的简单图称为完全图任意两个顶点之间 有且只有一条弧相连的有向图称为竞赛图在无向图中与顶点v关联的边的数目（环算两 次）称为该顶点的度（或次数），记为d(v)。度 为奇数的顶点叫做奇点，度为偶数的顶点叫做偶 点。在有向图中，从顶点v引出的边的数目称为 该顶点的出度，记为d+(v)，从顶点v引

3、入的边的 数目称为该顶点的入度，记为d-(v)，而d(v) d+(v)+d-(v)称为v的次数。在图中，两个顶点u和v之间由顶点和边构成的 交错序列（使u和v相通）称为链（通道），没有 重复边的通道称为迹，起点与终点重合的通道称 为闭通道，不重合的称为开通道，没有重复顶点 （必然边也不重复）的开通道称为路，起点与终 点重合的路称为圈（回路）包含奇数个顶点（ 或边）的圈称为奇圈，包含偶数个顶点（或边） 的圈称为偶圈。如果顶点u和v之间存在一条路， 则称u和v是连通的，任意两个顶点都连通的图称 为连通图无圈的连通图称为树，如果一棵树T 包含了图G的所有顶点，称T为G的生成树如果图G的每条边e都对应

4、一个实数C(e)，称 C(e)为该边e的权，称图G为赋权图通常称赋权 的有向图为网络图中边e6和e7是平行边，e9是环，顶点v4是悬挂 点，边e4是悬挂边2 最短路问题最短路问题是图论应用的基础，很多实际问题 ，如线路的布设、运输规划、运输网络最小费用 流等问题，都可以通过建立最短路模型来求解。 有些有深度的图与网络优化问题，如旅行售货商 、中国邮递员等问题，需要在首先求出任意两点 之间最短路的基础上解决。一、最短路的概念给定一个连通的赋权图G=V,E，设R是连接 节点vi和vj的一条路，该路的权定义为路中所有 各边权之和，如果路R在所有连接节点vi和vj的路 中权最小，则称它为vi和vj间的

5、最短路。二、任意两点之间的最短路(Floyd算法) Floyd算法利用距离矩阵进行迭代运算，可以 一次性地求出任意两点之间的最短路，该方法的 思路有创意，计算量小，编程较简单，又称矩阵 求解法。 1算法原理 设A=aijmn是图的权矩阵（也称带权邻接矩阵 ），其中aij是图上连接顶点i和j的边的权，如果 两顶点之间没有直接相连的边（即两顶点不相邻 ），则aij=。令矩阵D(0)=A，作为迭代的初始矩阵，从它出 发按照一定规则求D(1)，又由D(1)按照类似的规则 求D(2)，依此类推进行迭代直至求出D(n)，设矩阵 D(m)的元素为dij(m)，迭代规则为： 上式表示dij(1)在dij(0)

6、以及从顶点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是初始矩阵 for i=1:nfor j=

7、1:nR(i,j)=j;end endfor k=1:nfor i=1:nfor j=1:nif D(i,k)+D(k,j)0 ! 定义7个城市;link( city, city): dist, x; !距离矩阵和决策变量; endsets n = size( city); data:!dist是距离矩阵;dist =0 3 4 7 100 100 1003 0 3 2 4 100 1004 3 0 100 5 7 1007 2 100 0 2 100 6100 4 5 2 0 1 4100 100 7 100 1 0 2 100 100 100 6 4 2 0; !这里可改为你要解决的问题的

8、数据; enddatamin = sum( link: dist * x); !目标函数;U(1)=0; for( link: bin( x); !定义X为01变量;FOR(city( K)|K #GT# 1:sum( city( I)| I #ne# K: x( I, K) = 1;for(city( J)| J#gt#1 #and# J #ne# K:u(J)=u(K)+X(K,J)-(N-2)*(1-X(K,J)+(N- 3)*X(J,K); ); ); sum( city( J)| J #GT# 1: x( 1, J) = 1;for(city(K) | K #gt# 1:U(K)=1

9、; U(K)1），可以用Edmonds算法解决，其基本思路为：首先将奇点配对，使配 对以后各对之间距离的总和（两点之间的距离按照 最短路计算）达到最小（称为最佳配对）,求最佳 配对的方法可以用匈牙利法或0-1规划法等方法（ 可以用Lingo实现）。然后把每一对点之间的最短 路作为边添加到原图中,使之成为欧拉图G *，找出 G *的欧拉巡回就是原图的最佳巡回。算法步骤如下： (1) 用Floyd算法求出所有奇点之间的最短路径和 距离矩阵。 (2) 用匈牙利法或0-1规划法求出所有奇点之间的 最佳配对。 (3) 在原图上添加最佳配对所包含的两两顶点之 间的最短路得到欧拉图G *。 (4) 用Fle

10、ury算法确定一个G *的欧拉巡回，这就 是G的最优巡回。 三、Fleury算法的Matlab程序 设图是连通无向图，如果所有顶点都是偶点， 则该图是欧拉图，必然存在欧拉巡回，如果恰好 有两个奇次顶点，则称该图为半欧拉图，必然存 在起点在奇点（两个奇点中的一个）且终点在另 一个奇点的欧拉道路。这两种情况下都可用 fleury算法确定一条欧拉巡回或者欧拉道路。按照fleury算法的思路编写Matlab程序。主要程 序arEuler根据图的边集确定是否为欧拉图、半欧 拉图或非欧拉图，如果是欧拉图则用fleury算法找 到一条欧拉巡回路线（欧拉图的欧拉巡回不止一条 ，输出的是其中的一条），如果是半欧

11、拉图则返回 一条欧拉道路，其起点在两个奇点之一，终点是另 一个奇点。function eu,cEu=arEuler(E) %输入参数E是图的边集（m行2列矩阵，每一行 的两个数字代表一条边的两个顶点，共有m条边） ，输出参数eu有三种结果：若为欧拉图则eu=1； 半欧拉图则eu=0.5；否则eu=0。输出参数cEu是m 行1列矩阵，表示欧拉巡回或欧拉道路中边的序列 。 eu = 0; % eu的初始值为0 cEu=; % cEu开始时为空集 ncV=arComp(E); % 调用函数arComp确定图的 分枝构成，判断是否连通 if max(ncV)1, % 表示有2个或以上互不连通的 部分r

12、eturn % 不是连通图就返回endn=max(max(E(:,1:2); % n是图的顶点总数m=size(E,1); % m是边的总数for i=1:nb(i)=0;for j=1:mif E(j,1)=i|E(j,2)=ib(i)=b(i)+1;endendend% b表示各顶点的度数rp=rem(b,2); % 各顶点的度数除2取余数，偶点 的余数为0，奇点的余数为1 srp=sum(rp); % srp是rp的总和 switch srpcase 0, % 若余数的总和为0，则所有顶点为偶 点，原图是欧拉图eu=1;case 2, % 恰好有两个奇点，原图是半欧拉图eu=0.5;ot

13、herwise, % 否则是非欧拉图returnend % 以下程序寻找一条欧拉巡回或欧拉道路if srp=0, % 对于欧拉图v1=1; % 把第一个顶点作为欧拉巡回的起点else % 对于半欧拉图v1=find(rp); %先找出奇点v1=v1(1); % 把第一个奇点作为欧拉道路的起 点endvc=v1; % vc是当前顶点m=size(E,1); % m是边的总数E1=E(:,1:2), 1:m; % E1代表候选边集，开 始时它的前两列与E相同，第三列表示边的顺序号 % 以下是Fleury算法 while isempty(E1), %若E1非空则循环evc=find(E1(:,1)=

14、vc)|(E1(:,2)=vc); % 找出 与当前顶点vc关联的边levc=length(evc); % 统计与当前顶点vc关联的边 的总数if levc=1, % 只有一条路cEu=cEu;E1(evc,3); % 把新的边加入欧拉 巡回或欧拉道路中vcold=vc;vc=sum(E1(evc,1:2)-vc; % vc为新的当前点E1=E1(setdiff(1:size(E1,1),evc),:); % 删除孤 立顶点E2=E1(:,1:2);E2gv=E2vcold;E2(E2gv)=E2(E2gv)-1;E1(:,1:2)=E2;if vcvcold,vc=vc-1;endif v1

15、vcold,v1=v1-1;endelse % 从顶点vc出发有若干条路可供选择for k=1:levc,E2=E1(setdiff(1:size(E1,1),evc(k),:);ncv=arComp(E2); % 确定E2的互不相连的 分枝数目nco=max(ncv);if (max(ncv)=1), % 此时E2为连通图，即选 中的边不是割边（桥）cEu=cEu;E1(evc(k),3); % 把该边加入欧 拉巡回或欧拉道路中vc=sum(E1(evc(k),1:2)-vc; % vc为新的当前点E1=E2;break;endendendend return在fleury算法过程中，每次预选一条边，需要判 断它是否为当前子图的割边，为此先假定把该边从 当前边集中删去，然后判断余下的子图是否连通， 若不连通，则选中的边是当前子图的割边，若仍然 连通，则不是割边，可以把该边加入巡回中。 在程序arEuler中，通过调用函数arComp来确定 图的互不连通的分枝数，根据它的返回结果判定图 的连通性。function ncV=arComp(E,n) %功能是确定图的互不连通的分枝数目。输入参 数E是图的边集，它使m行2列矩阵，每一行的两个 数字代表一条边的两个顶点，共有m条边，n是图 的顶点数，该参数不是必须的，可以省略，此时默 认n=max(max(E)，但