1、 第一章第一章 图论图论模型模型引例引例1 1.哥尼斯堡哥尼斯堡七桥问七桥问题 一个步行者怎样才能不重复、不遗漏地一次走完七座桥最后回到出发点？该问题被认为是图论起源，被大数学家欧拉解决。问题的本质：人们分别在岸上和岛上行走的路线与距离，桥的形状长度与本问题无关我们只需要关注过桥的顺序。图的建立：用四个点来表示河的两岸和河中的岛屿而用点之间的连线表示连接它们之间的桥。观察分析：我们所要求的走法存在的 必要条件是图中每个点相关联的连线 数目是偶数。结论：所要求的走法是不存在的。引例引例2 2.过河过河问题问题 一只狼、一只羊、一筐菜位于河的同侧。一个摆渡人要将它们运过河去，由于船小运力有限，一次
2、只能载三者之一。很显然狼和羊，羊和菜都不能在无人监视的情况下留在一起，那么摆渡人应该怎样把它们运过河呢?问题分析：每次摆渡发生后，羊、狼、菜中最多一个以及人的位置会发生变化。而根据题意，其中一些位置的组合是不可以出现的。因此，整个摆渡过程可以看成是狼、羊、菜、人的位置的可行的变化过程。用长度为的0，1序列来表示人、羊、狼、菜摆渡前后的位置其中表示北岸，而0表示南岸。用平面上点来表示可能的10个状态，两点用一条线相连，当且仅当这两点所表示的位置状态可以通过一次摆渡转化。图中从点(,1)经过一些边到点(0,0,0,0)的每一种走法都对应一种可行的摆渡方案。图论模型的基本思路图论模型的基本思路 将实
3、际对象转化成“图”。实际问题对应成“图”上的问题。用“图”的研究方法来解决问题。将结果对应到实际问题，给出解释。本章结构本章结构1.11.1图论图论模型的基本模型的基本理论理论 所谓的图图就是由平面上的一些点以及这些点之间的连线构成的结构。图中的点在图论中称为图的顶点顶点，两点之间的连线称为图的边边。和某一点有边连接的点都称为它的邻邻点点。一点出发通过一些边经过不同的点到达另一点的路径我们称之为两点间的路路，所含边的数目称为路的长度。所有连接两点路的长度的最小值称为这两点之间的距离距离。图的表示图的表示 关联矩阵关联矩阵:当图 的顶点集和边集分别为 和 时，我们可以写出其对应关联矩阵 其中 如
4、果是的一个端点则 为1，否则为0。邻接矩阵邻接矩阵:当图 的顶点集为 时，我们可以定义它的邻接矩阵 其中 为连接顶点 与 的边的数目。注：图的邻接矩阵是对称的，我们往往计算机只存储对角线及以上部分。GG1,nvvL1,meeL()()ijMGmivjeijm1,nvvL()()ijA Gaijmjviv关联和邻接矩阵举例关联和邻接矩阵举例左图为关联矩阵，右图为邻接矩阵特殊图类特殊图类 赋赋权图权图：对图中的边赋予一定的权重。有向图有向图：对图的每一条边都规定方向。其它图类：其它图类：支撑树与完美匹配支撑树与完美匹配 包含所有顶点的子图叫支撑支撑子图子图。特别地，如果一个支撑子图是树时，我们称它
5、为图的支撑树。支撑树。所有由两两无公共端点的边组成的子图称为图的匹配匹配。如果该匹配涵盖图的所有顶点，则称其为图的完美匹配完美匹配。下图中右图为左图的完美匹配。1.1.1 1.1.1 图图的独立集的独立集 图的一个顶点子集如果其中任何两个顶点之间都没有边相连，那么我们称其为一个独立集独立集。在工程上也叫稳定集稳定集。所含顶点个数最多的独立集称为最大独立集最大独立集，而这一最大值称为图的独立独立数数。如果一个独立集不包含于任何其它独立集，我们称其为极大独立极大独立集集。独立集可以由贪婪算法直接得到，也可由图的覆盖得到。覆盖与独立集覆盖与独立集 图的一个顶点子集满足图中任意一条边都与其中某一点关联
6、，则称该子集为图的一个覆盖覆盖。所含点数最小的覆盖称为最小覆盖最小覆盖，如果一个点覆盖不包含其他覆盖，我们称其为图的极小极小覆盖覆盖。如果以顶点集为全集，每个独立集的补集为图的一个覆盖，而任何一个覆盖的补集为一个独立集。右图中5,7,8为一极大独立集，1,4,7,8为一最大独立集，1,23,4,6为一极小覆盖，2,3,5,6为一最小覆盖。1 1.1.2.1.2竞赛图竞赛图 竞赛图竞赛图是一种特殊的有向图，它的任何一对顶点之间都有一条唯一的有向边相连。换句话说竞赛图是由对完全图的每条边都赋上一个方向得到。性质1：任何竞赛图都含有一个有向哈密尔顿路。性质2：任何竞赛图都有一个唯一的双连通分支的线性
7、排序。注：如果图中任意两个顶点之间都有两条方向相反的有向路连接，则称其是双连通或强连通的。对于不是双连通的图，都可以分解成若干个极大的双连通分支，且任意两分支之间的边是同向的。举例：举例：右图所示竞赛图不是双连通的 为一条有向的哈密尔顿路。该图有个双连通分支且唯一线性排序为DABCE1 1.1.3.1.3DijkstraDijkstra算法算法 Dijkstra算法算法是一个用来计算给定赋权图中一点到其他各点之间距离的算法,也称为最短路算法。它的主要步骤如下：1.1.4 1.1.4 KruskalKruskal算法算法 Kruskal算法算法可以用来高效地求赋权图的最小支撑树，具体如下：1.1
8、.5 1.1.5 匹配算法匹配算法1.匈牙利算法匈牙利算法用来求已知二部图的最大匹配，如果二部图两部分顶点一样多，该算法可以确定完美匹配是否存在。2.Kuhn-Munkres算法算法是对匈牙利算法的一个改进可以用来找出赋权完全二部图的最优匹配。匈牙利算法匈牙利算法 饱和点：饱和点：是图的一个匹配，若中顶点是中某条边的端点，则称饱和,否则称是的非饱和点。可可扩扩路路：一条连接两个非饱和点x和y的由外的边和的边交错组成的路称为的(x,y)可扩路。算法基本步骤：Kuhn-Kuhn-MunkresMunkres算法准备算法准备 假设 是顶点集上的实函数,且满足对于所有的及,均有 ，其中 为边xy的权重
9、,则称 为的一个可行可行顶点顶点标号标号。记 为在标号 下，那些使得上式取等号的边组成的的子图。中与顶点集关联的点的集合记为 。l()()(,)l xl yw x y(,)w x ylGlG()lGNSKuhn-Kuhn-MunkresMunkres算法算法1.2 1.2 图图的独立集应用的独立集应用 问题描述：问题描述：各大学学期临近结束时，需要根据老师任课计划和学生选课情况，再结合教室资源情况安排下一学期的课程及上课时间和地点。下表所示是某大学电信学院的大三各专业部分课程情况。该学院每届学生按专业分班，统一选课。另外，学院只有一间普通机房和一间高级机房。那么应该如何合理地排这些课程呢?思路
10、分析思路分析 每学期任课老师都有一定工作量的要求往往可能要上不止一门课程。每位同学需要在学期内完成若干门课程的学习。某些对上课设施有特殊要求的课程，也不可以安排在同一时间。为了方便开展一些全校性的活动，有些时段不安排课程。受到教室数量的限制，在同一时段无法安排太多的课程。模型建立模型建立 以每个课程为顶点，任何两个顶点之间连一条边当且仅当两门课程的任课老师为同一人，或有学生同时选了这两门课或上课教室冲突。那么一个合理的课程安排就是将图中的点进行分化，使得每一个部分里的点为一个独立集。通过极小覆盖找出图中的极 大独立集，然后删去该极大 独立集，在剩下的图中找出 极大独立集，直到剩下的图 为一个独
11、立集。模型求解模型求解 为了构造图的覆盖，对于每一顶点，我们至少要么选取该点要么选取它的所有邻点。利用代数方法，首先把选择顶点这个指令简记为符号，指令“或”和“与”分别记为(逻辑和)和(逻辑积)。在本例中，我们的指令用于求极小覆盖时就是化简后为 故有四个极小覆盖：选取一个覆盖的补作为独立集，去除后再继续这一过程。最终得到课程安排为第一时间段b,d,f；第二时间段a,e,g；第三时间段c。,a c e gb c e g db d e fb c d f1.3 1.3 竞赛图应用竞赛图应用 问题描述：问题描述：某锦标赛采用循环赛制，若干选手两两互相竞赛。得出竞赛成绩后应该怎样排列参赛者的名次呢?下表
12、表所示是一次比赛成绩，我们用数字-来表示 这名选手，其中“胜”字所在行的选手战胜所在列的选手“负”字所在行的选手输给了所在列的选手。模型建立模型建立 用点来表示运动员，对于两名运动员比赛结果，用一条由胜者到负者的有向边表示，得到下图。按照哈密尔顿路给出排名或计算 获胜场数均不够合理。采用多级得分向量多级得分向量方法：模型求解模型求解 我们看到竞赛图的等级得分向量由 给出，这里是的邻接矩阵，是全1列向量。邻接矩阵 元素的取值满足如果连接点 和 的有向弧是从 指向 ,则 ，否则为.由于是本原的，根据Perron-Frobeinius定理设具有最大绝对值的特征值是正实数，则 这里S是对应于r的正特征
13、向量。本例中 用这个方法给出的选手的名次排列为1,3,2,5,4,6。()=()ijA Daivjvivjv=1ija一般情形一般情形 若竞赛图不是双连通的，它的各个双向连通分支可以按优胜顺序排列。于是在一般的循环赛中可以按下列程序排出名次。1.41.4.DijkstraDijkstra算法应用算法应用 在大城市里，乘坐公共交通工具出行是人们主要的出行方式，而在各种公共出行方式中，地铁无疑是最可靠的。事实上，在大中型城市，地铁建设正如火如荼地进行。尤其是特大城市，已经形成了较复杂的地铁网络。面对这样复杂的地铁网络，人们面临的首要问题就是如何选择最佳的搭乘线路。而对于地铁运行商来说，一个现实的问
14、题就是如何制定地铁票的价格标准。以南京部分线路为例以南京部分线路为例 讨论如何建立数学模型来解决以上两个问题。下图是南京地铁1-4号线部分主要站点线图草图。1.4.1.1.4.1.最佳乘车路线问题最佳乘车路线问题 问题描述：问题描述：乘地铁时，对于同一目的地，人们有多种乘车路线，选择那么究竟哪一种路线才是最佳的呢?思路思路分析：分析：影响乘坐时长主要因素：第一，各条线路的运行速度是不一样的。第二，换乘时可能会消耗一定时间。第三，所选择的线路的总运行距离不同。而这些因素都和出行所在时间段是否在高峰期相关。因此，我们可以根据出行时间段以及这三个因素的实际情况选择出行线路。模型建立模型建立 首先我们
15、根据已知地铁线路建立一张简图，对于每一条线路所经站点按顺序用一列点表示并且在相邻站点之间用一条线段连接.对于两不同线路共同的站点(即可更换线路的站点)用线段连接。其次根据出行所在时段的实时数据，给每段线段分别赋值：()对于同一线路上两个相邻站点之间的线段赋值为两点之间距离除以线路运行速度再加上站点停靠时间。()对于不同线路的换乘点之间的线段赋值为换乘时间。模型求解模型求解 下图为根据南京地铁草图绘制的简单图，如给出某时段的运行时间和换乘时间，就可对该图赋权并运Dijkstra算法计算甲、乙两站点间的最佳乘坐线路和所需时间。1.4.2.1.4.2.票价制定问题票价制定问题 问题描述问题描述：如何
16、制定合理的地铁票价?思路思路分析分析：从运行成本的角度票价应只与乘坐距离有关由于目前还无法全线跟踪每一乘客的详细乘坐线路故公平起见只能默认乘客所选线路是运行距离最短的。模型模型建立建立：由于列车停靠与线路换乘与运行距离无关。我们对上节中的简图和赋值做如下修改：()将两条线路的公共站点(换乘点)合成一个点，即将这两点之间的线段收缩掉。()对于两相邻站点之间的线段赋值为两点之间的距离或赋值为个单位。模型求解模型求解 下图即为用于制定票价的简图，边的赋值为两站之间经过的站点数量。运用Dijkstra算法可以计算出两站之间需经过最少站点数目，从而定价。1.5 1.5 KruskalKruskal算法算
17、法 问题描述：问题描述：为了改善某地区的交通，国家决定建设连接该地区的各个主要城镇的小型铁路网络。请设计经济、合理的铁路网络。思路分析：思路分析：建造铁路网络的主要目的是连接主要城镇，最基本的要求是居民可以在任意两个城镇之间通过该铁路网络通行。在保证满足这一基本要求的基础上我们要尽量节约建造成本，也就是总费用要少。模型建立模型建立 我们可以用点来表示乡镇，根据实际情况判定两个城镇之间建立直通铁路的可行性，以及所需成本。在可以建造铁路的两个乡镇所代表的点之间连上一条边并且赋上经过核算后的最低造价。这样我们就得到了一张赋权图。(下页a图)模型求解模型求解 显然在任何两城镇之间都建立直通铁路是相当浪
18、费的。因此我们只需在这张图中找到一最小支撑树。根据此最小支撑树在每条边所连接的城镇间施工建造即可。（图b就是一种方案）1.6 1.6 匹配算法匹配算法应用应用 问题描述问题描述：随着经济的快速发展城市规模日益膨胀，城市道路日趋复杂这就给应对突发事件带来了很大的困难。以罪犯逃逸为例，警方需要在短时间内封锁市区内各主要出口并抓捕逃犯但警力有限且分散在全市各地，如何安排出警？思路分析思路分析 当犯罪行为发生后犯罪分子的逃逸线路并无规律不易预测我们无法保证及时有警力到场因此封锁拦截是一个较有效的办法。而要做到及时封锁道路我们需要对城市道路通行情况非常熟悉了解每一路段的通行情况以及对应的有效封锁路口位置
19、。在安排警力出警时主要考量的是在尽量短的时间内到达各个封锁路口。封锁的成败在于每一个路口都要在规定时间警力到达。模型建立模型建立 当犯罪行为发生时根据当时的交通通行情况估算出犯罪分子到各个主要出口所需最短时间t。分别计算出各警点的警力到达这些主要路口的时间（见前面表格）。我们用顶点集表示所有的路口表示各出警点建立一个赋权完全二部图。分别以和作为二部图的两个部分。对于每一条由路口与出警点连接的边赋上出警点到达路口所需的时间。模型求解模型求解I I 在图中有找到一个饱和的匹配且匹配中的每一条边的权重都要不超过.因此需要删去赋权超过t的边。下图分别是t=20和15时的图。t=20 t=15模型求解模型求解II II 图确定后，只要是找到饱和X的匹配就是一个可行的封锁方案。如要求各出警点出警所需的总时间最短，则可以利用1.1.5节的Kuhn-Munkres算法求出最优匹配。
