许多优化问题都等价于在一个图中寻 找最短路。例如，管道的铺设、线路的安 排、厂址的选取和布局、设备的更新等。 最短路问题一般归为两类：一类是求 从某个顶点到其他顶点的最短路径，可用 Dijkstra算法求解; 另一类是求图中每一对 顶点间的最短路径，可用Floyd算法求解。 Dijkstra 算法和Floyd 算法既适用于无 向图，也适用于有向图。
例1 已知图Leabharlann 的邻接矩阵为0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0
求图G的关联矩阵。 结果为
1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1
0 0 1 1
例2 已知图G的关联矩阵为
间的区别？ 14. 如何利用程序判定Euler图以及Hamilton 图？ 15. 如何理解网络流、网络最大流、最小费 用最大流？ 16. 如何应用Ford - Fulkerson算法、Dinic算 法及 Busacker- Gowan算法求解最大流、最 小费用最大流？
图论模型及其Matlab程序
3.3 用程序incToadj.m 和 diincToadj.m实现 上题中邻接矩阵和关联矩阵的相互转化。
3.4 写出下列网络的邻接矩阵：
二、最短路问题
最短路问题是计算机、运筹学、地理 信息科学等领域的研究热点之一。在数学 建模中，时常出现各类最短路问题。 最短路问题是指：若从图中的某一顶 点(源点) 到达另一顶点 (终点) 的路径不止 一条，如何寻找一条路径，使得沿此路径 各边上的权值总和 (源点到终点的距离) 最 小，这条路径称为最短路径。
1.5 路径 路径是图论中一个很重要的概念。 在图G(V,E)中, 若从vi出发，沿着一些 边经过顶点vp1,vp2,…,vpm，到达顶点vj，则 称顶点序列(vi,vp1,vp2,…, vpm,vj)为从顶点vi 到vj的一条路径或通路。 路径中边的数量称为路径的长度。 若路径中各顶点vi,vp1,vp2,…,vpm,vj均互 相不重复，则称之为简单路径。
容
8. Dijkstra算法和Floyd算法各适用于哪一类 最短路问题？ 9. 如何应用程序实现Dijkstra算法和Floyd算 法，怎样理解、改进输出结果？ 10. 如何理解树、生成树、最小生成树？ 11. 如何应用程序求解最小生成树？ 12. 什么叫环游、最优环游、Euler环游、 Hamilton环游、Euler图、Hamilton图？ 13. 如何理解中国邮递员问题和旅行商问题
若路径中第一个顶点 vi 与最后一个顶 点vj重合，则称此路径为回路。 除第一个和最后一个顶点外，没有顶 点重复的路径称为简单回路。 例如，
在G1中，(0,1,4,3)为0到3的一条路径， 且为简单路径, 长度为3；在G2中, (2,4,1,5) 为2到5的一条路径, 长度也为3, 而(4,3,2,4) 为一简单回路。
图论是数学的一个分支，以图为研究 对象。图论中的图是由若干个给定顶点及 若干条连接两个顶点的边所构成的图形， 这种图形通常用来描述某些事物之间的某 种特定关系，用顶点代表事物，用连接两 个顶点的边表示相应两个事物间具有这种 关系。这种图提供了一个很自然的数据结 构，可以对自然科学和社会科学中许多领 域的问题进行恰当的描述或建模，因此图
2.3 网络的邻接矩阵 对于网络G(V,E)，邻接矩阵A=(aij)n的 定义为
w i, j , i ! j i , j or (i , j ) E , aij , i ! j i , j or (i , j ) E , 0, i j,
1.6 权值与网络 某些图的边具有与之相关的数，称为 权值。这些权值可以表示从一个顶点到另 一个顶点的距离、时间、代价等。 若一个图的所有边都具有权值，则称 之为加权图或网络。 根据图中的边是否有向，网络又可以 分为有向网和无向网。 网络也可以用G(V,E)表示，其中边集
E中的每个元素有3个分量：边的两个顶点 和权值。 例如，下面两图分别为无向网和有向 网：
论研究越来越得到这些领域的专家和学者 的重视。 图论最早的研究起源于瑞士数学家欧 拉，他在1736年成功地解决了哥尼斯堡七 桥问题，从而开创了图论的先河。
在此后的200多年时间内, 图论的研究 从萌芽阶段，逐渐发展成为数学的一个新 分支。20世纪70年代以后，由于高性能计 算机的出现，使大规模图论问题的求解成 为可能。目前，图论理论已广泛应用于运 筹学、计算机科学、电子学、信息论、控 制论、网络理论、经济管理等领域。
由于图论有着丰富的算法和广泛的应 用，所以一直以来图论问题在信息类竞赛 中占有较大比重。例如，在著名的ACM/ ICPC程序设计竞赛中, 图的遍历、最小生 成树、最短路径、网络流、匹配问题、图 的连通性、图着色等都是常见问题。 数学建模竞赛中的图论问题不及ICPC 中的普遍，难度也不大。
本讲主要介绍图的一些基本概念及存 储方法、最短路问题、最小生成树问题、 可行遍性问题、网络流问题及其Matlab程 序。 本讲要求学生理解图论的基本概念； 掌握图的邻接矩阵表示方法；能较为熟练 地根据实际问题正确地建立图论模型，并 利用相应的Matlab程序求解；不要求理解 算法，编写程序。
1, vi 是e j的始点, mij 1, vi 是e j的终点, 0, vi 与e j 不关联,
1 1 0 A 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0
1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1
求图G的邻接矩阵。 结果为
0 1 1 1 1 0 1 1 1 1 0 1
1 1 1 0
3. 作业与上机练习
3.1 理解图的基本概念及存储方法； 3.2 写出下列两图的邻接矩阵和关联矩阵：
2012数学建模培训
第6讲 图论模型及Matlab程序
“图论模型及其Matlab程序”学习内
1. 如何理解图、无向图、有向图？ 2. 如何理解顶点与顶点及边的关系？ 3. 如何理解加权图？ 4. 如何确定图的邻接矩阵和关联矩阵？ 5. 如何确定网络的邻接矩阵？ 6. 如何应用程序实现邻接矩阵和关联矩阵 的转化？ 7.什么是最短路径问题，通常有几类？
例如，左图为完全图，右图为完全有 向图。
1.4 顶点与顶点、顶点与边的关系 在图论中，顶点与顶点、顶点与边的
关系是通过“邻接(Adjacency)”这个概念来 表示的。 在无向图G(V,E)中，若(u,v)是图中的 一条边，则称u和v互为邻接顶点，边(u,v) 依附于u,v，或称(u,v)与u,v相关联。 在有向图G(V,E)中, 若<u,v>是图中的 一条边，则称u邻接到v，v邻接自u，(u,v) 与u,v相关联。
(1) 设置两个顶点集合T和S； ① S中存放已找到最短路径的顶点， 初始时，S中只有u0； ② T中存放当前尚未找到最短路径的 顶点； (2) 在T中选取当前长度最短的一条最 短路径(u0,…,uk)，从而将uk加入S，并修改 u0到T中各顶点的最短路径长度。重复这一 步骤，直到所有顶点都加入到S中。
1 1 0 A 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 0
对有向图G(V,E)，类似地定义
2. 图的存储方法
图的存储方法有多种，最常用的存储 方法是邻接矩阵和关联矩阵。 2.1 邻接矩阵 设无向或有向图G(V,E)，V={v1,v2,…, vn}，E={e1,e2,…, em}。用aij表示vi,vj间的边 数，即
1, v , v E 或 v , v E , i j i j aij 否则, 0,
一、图的基本概念与图的存储
1. 图的基本概念
图论的一个特点就是概念特别多。 这里只介绍一些基本的概念，其它概 念在后面用到时再补充介绍。
1.1 图 图是由顶点集合和边的集合组成的数 据结构，通常用G(V,E)来表示，其顶点集 合和边的集合分别用V(G)和E(G)表示。
例如，右图所示的图 可表示为G(V,E)。其中， V(G)={0,1,2,3,4,5}， E(G)={(0,1),(0,2),(1,2),(1,3), (1,4),(1,5),(2,3),(2,4),(3,4)}。 1.2 无向图与有向图 所有边都没有方向的图称为无向图， 如1.1中的图；每条边都有方向的图称为有 向图，通常用<u,v>表示从u到v的有向边。
当顶点数较大时, 经典Dijkstra算法的 运行效率较低。为此，研究人员陆续提出 了两个改进算法：DijkstraI和DijkstraII。 1.3 Dijkstra算法程序及实例 Dijkstra算法及其两个改进算法的程序 分别见Dijkf.m，dij1.m和dij2.m。 在Dijkf 中，输入为问题的邻接矩阵， 输出为3个向量：d, index1, index2。其中di 为由源点到第i个顶点的最短距离；index1
例如，对于右图所示 的有向图G(V,E)，V(G)= {0, 1, 2, 3, 4, 5, 6}, E(G)= {<0,1>,<1,2>,<1,4>,<1,5>, <2,4>,<3,2>,<4,1>,<4,3>,<5,6>}。 1.3 完全图 任何一对顶点都有一条边的图称为完 全图；任何一对顶点u,v都有<u,v>和<v,u> 两条有向边的图称为完全有向图。