文档介绍：第二讲图论模型
第一页，共98页
1. 问题引入与分析
1) 98年全国大学生数学建模竞赛B题“最佳灾
今年(1998年)夏天某县遭受水灾. 为考察灾情、
组织自救，县领导决定，带领有关部门负责人到
全县各乡（镇）、村巡视. 巡视路线指从县政府
所在地出发，走遍各乡（镇）、村，又回到县政
府所在地的路线.
情巡视路线”中的前两个问题是这样的：
第二页，共98页
1）若分三组（路）巡视，试设计总路程最
短且各组尽可能均衡的巡视路线.
2）假定巡视人员在各乡（镇）停留时间T=2
小时，在各村停留时间t=1小时，汽车行驶速度V
=35公里/小时. 要在24小时内完成巡视，至少应分
几组；给出这种分组下最佳的巡视路线.
第三页，共98页
第四页，共98页
2) 问题分析：
本题给出了某县的公路网络图，要求的是在不
同的条件下，灾情巡视的最佳分组方案和路线.
将每个乡（镇）或村看作一个图的顶点，各乡
镇、村之间的公路看作此图对应顶点间的边，各条
再回到点O，使得总权（路程或时间）最小.
公路的长度（或行驶时间）看作对应边上的权，所
给公路网就转化为加权网络图，问题就转化图论中
一类称之为旅行售货员问题，即在给定的加权网络
图中寻找从给定点O出发，行遍所有顶点至少一次
第五页，共98页
如第一问是三个旅行售货员问题，第二问是四
本题是旅行售货员问题的延伸
－多旅行售货员问题.
本题所求的分组巡视的最佳路线，也就是m条
众所周知，旅行售货员问题属于NP完全问题，
显然本问题更应属于NP完全问题. 有鉴于此，
经过同一点并覆盖所有其他顶点又使边权之和达到
最小的闭链（闭迹）.
个旅行售货员问题.
即求解没有多项式时间算法.
一定要针对问题的实际特点寻找简便方法，想找到
解决此类问题的一般方法是不现实的，对于规模较大
的问题可使用近似算法来求得近似最优解.
第六页，共98页
1) 图的概念
2) 赋权图与子图
3) 图的矩阵表示
4) 图的顶点度
5) 路和连通
第七页，共98页
1) 图的概念
定义 一个图G是指一个二元组(V(G),E(G))，其中:
其中元素称为图G的顶点.
组成的集合，即称为边集,其中元素称为边.
定义 图G的阶是指图的顶点数|V(G)|, 用
来表示；
图的边的数目|E(G)|用
来表示.
也用
来表示边
是非空有限集，称为顶点集，
1)
2) E(G)是顶点集V(G)中的无序或有序的元素偶对
表示图，简记
用
第八页，共98页
定义 若一个图的顶点集和边集都是有限集，则称
其为有限图. 只有一个顶点的图称为平凡图，其他的
所有图都称为非平凡图.
第九页，共98页
定义若图G中的边均为有序偶对
,称G为有向
边 为无向边，称e连接 和 ，顶点 和 称
图. 称边
为有向边或弧,称
是从
连接
，称 为e的尾，称 为e的头.
若图G中的边均为无序偶对 ，
为e的端点.
既有无向边又有有向边的图称为混合图.
第十页，共98页