图论模型简介.doc

《图论模型简介.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论模型简介一、图及其矩阵表示1、起源：哥尼斯堡七桥问题：欧拉为了解决这个问题，建立数学模型：陆地——点，桥——边，得到一个有四个“点”，七条“边”的“图”。问题转化为能否从任一点出发一笔画出七条边再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画判定法则：图是连通的，且每个顶点都与偶数条边相关联（这种图称为欧拉图）。由此可以得出结论：七桥问题无解。2、基本概念：图（graph）：由顶点和边（又称线，边的两端必须是顶点）组成的一个结构。邻接：一条边的两个端点称是邻接的；关联：边与其两端的顶点称是关联的。无向图（graph）：边无方向的图；有向图（digraph）：边有方向的

2、图。路(path)：由相邻边组成的序列，其中中间顶点互不相同。圈(cycle)：首、尾顶点相同的路，即闭路。连通图（connectedgraph）：图中任意两顶点间都存在路的图。树（tree）：无圈连通图完全图（completegraph）：任意两个顶点之间都有边相连的无向图，记为Kn。竞赛图（tournament）：由完全图给每条边定向而得到的有向图。二部图（bipartitegraph）：图的顶点分成两部分，只有不同部分顶点之间才有边相连。图G的子图H（subgraph）：H是一个图，H的顶点（边）是图G的顶点（边）。网络（Network）：边上赋了权的有向图。3、图的矩阵表

3、示无向图有向图4、著名的图论问题例1最短路问题（shortestpathproblem）出租车司机要从城市甲地到乙地，在纵横交错的路中如何选择一条最短的路线？例2最小生成树问题（minimum-weightspanningtreeproblem）为了给小山村的居民送电，每户立了一根电杆，怎样连接可使连线最短？例3中国邮递员问题（chinesepostmanproblem）一名邮递员负责投递某个街区的邮件。如何为他设计一条最短的投递路线？例4（二部图的）最优匹配问题（optimummatching）在赋权二部图中找一个权最大（最小）的匹配。例5旅行推销员问题（travelingsa

4、lesmanproblem－TSP）一名推销员准备前往若干城市推销产品。如何为他设计一条最短的旅行路线？例6网络流问题（networkflowproblem）如何在一个有发点和收点的网络中确定具有最大容量的流。二、求最短路的迪克斯特拉（Dijkstra）算法基本思想是按距由近到远的顺序，依次确定到的各顶点的最短路和距离。为避免重复并保留每一步的计算信息，采用标号算法。Dijkstra算法如下：STEP1：，，，，;STEP2：（），<－,,计算，记达到这个最小值的一个顶点为，令;STEP3：若，停止；否则，转STEP2。例求右图中从顶点u1到其它各点的最短路及相应的路径.求解过程

5、列表如下：顶点前驱点序号123456781161253510¥¥¥¥¥¥¥2281¥¥¥¥328¥¥10¥483¥10¥58610126710127912812例1某公司在六个城市中有分公司，从到的直接航程票价记在下述矩阵的位置上。（表示无直接航路），请帮助该公司设计一张城市到其它城市间的票价最便宜的路线图。解第一个城市到其它城市的最短路径的Matlab程序如下：clear;clc;M=10000;a(1,:)=[0,50,M,40,25,10];a(2,:)=[zeros(1,2),15,20,M,25];a(3,:)=[zeros(1,3),10,20,M];a(4,:)=[

6、zeros(1,4),10,25];a(5,:)=[zeros(1,5),55];a(6,:)=zeros(1,6);a=a+a';pb(1:length(a))=0;pb(1)=1;%永久标号点index1=1;%标记确定为永久标记的次序index2=ones(1,length(a));%标记最短路上各点的先驱顶点d(1:length(a))=M;d(1)=0;%标记最短距离temp=1;%标记最近一个永久标号点whilesum(pb)

7、tmpb=find(d(tb)==min(d(tb)));%确定新最小距离点temp=tb(tmpb(1));%记录新永久标号点pb(temp)=1;%增加新永久标号点index1=[index1,temp];%记录新永久标号点index=index1(find(d(index1)==d(temp)-a(temp,index1)));%确定前驱顶点iflength(index)>=2%前驱顶点多于1个时取第一个index=index(1);endindex2(temp)=inde