图与网络模型及方法学习心得.doc

图与网络模型及方法学习心得
摘要：图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的《哥尼斯堡的七座桥》。1847年，克西霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计算烷烃的同分异构体时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈。近几十年来，计算机技术和科学的飞速发展，大大促进了凸轮的研究和应用，凸轮的理论和方法已经渗透到物理、化学、通信科学、建筑学、运筹学、生物遗传学、心理学、经济学、社会学等学科中。
图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点来表示这些具体的事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来，问题是要从这块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。
当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”、七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。
正文：在寒假中，学习了图论这一章以后，对于此类问题的解决方法就是构造一个模型图，再根据图来完成题目的要求。
如page40的例题4.1，某超市在六个城市C1...C6中有分公司，从Ci到Cj的直接航程票价记在下述矩阵的（i,j）位置上。请帮助该公司设计一张城市C1到其他城市间的票价最便宜的路线图。

用矩阵
a n×n（ n 为顶点个数） 存放各边权的邻接矩阵， 行向量 pb 、 index1 、 index2 、
d 分别用来存放 P 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分
量
pb(i) = ⎩⎨⎧10 当第当第ii顶点已标号顶点未标号 ；
index2 (i) 存放始点到第 i 点最短通路中第 i 顶点前一顶点的序号；
d(i) 存放由始点到第 i 点最短通路的值。
求第一个城市到其它城市的最短路径的 Matlab 程序如下：
clc,clear
a=zeros(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;
pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));
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;
index1=[index1,temp];
temp2=find(d(index1)==d(temp)-a(temp,index1));
index2(temp)=index1(temp2(1));
end
d, index1, index2
我们编写的从起点sb到终点db通用的Dijkstra标号算法程序如下：
function [mydistance,mypath]=mydijkstra(a,sb,db);
% 输入： a—邻接矩阵(aij) 是指i到j 之间的距离，可以是有向的
% sb—起点的标号, db—终点的标号
% 输出： mydistance—最短路的距离, mypath—最短路的路径
n=size(a,1); visited(1:n) = 0;
distance(1:n) = inf; % 保存起点到各顶点的最短距离
distance(sb) = 0; parent(1:n) = 0;
for i = 1: n-1
temp=distance;
id1=find(visited==1); %查找已经标号的点
temp(id1)=inf; %已标号点的距离换成无穷
[t, u] = min(temp); %找标号值最小的顶点
visited(u) = 1; %标记已经标号的顶点
id2=find(visited==0); %查找未标号的顶点
for v = id2
if a(u, v) + distance(u) < distance(v)
distance(v) = distance(u) + a(u, v); %修改标号值
parent(v) = u;
end
end
end
mypath = [];
if parent(db) ~= 0 %如果存在路!
t = db; mypath = [db];
while t ~= sb
p = parent(t);
mypath = [p mypath];
t = p;
end
end
mydistance = distance(db);
return