图论与几何模型

第七讲:图论与几何模型---水鹏朗数学建模理论与实验7.1哥尼斯堡七桥问题Euler时代的哥尼斯堡城区(18世纪)

现在的俄罗斯加里宁格勒市(俄罗斯“飞地”)Euler问题能否找到一条路径:从一个地方出发穿过每座桥仅一次再回到出发地。几何抽象几何抽象的目的在于提纯与问题相关的因素(河流、桥、区域），剔除与问题无关的因素(城区的地面景观等)，以便简化问题描述。7.1哥尼斯堡七桥问题ABCDABCDGraph(图,无向图),图论(GraphTheory)7.1哥尼斯堡七桥问题图的描述abcdefghi一个图G由两个集合构成，顶点(vertex)集合V(G)和边(Edge)集合E(G).V(G)={a,b,c,d,e,f,g,h,i}E(G)={ac,ad,af,bd,bg,ch,di,ef,ei,fg,gh,hi}连接矩阵表示7.1哥尼斯堡七桥问题abcdefghi基本术语与概念如果边e的一个顶点是j,那么称作边e与顶点j是关联的(incident).如果顶点i，j有边相连,那么称作顶点i和j是邻接的(adjacent).顶点i的度(阶数)是指与顶点i关联的边（或者邻接的顶点）的数目，记作degree(i).例如degree(a)=3;degree(b)=2;degree(i)=3.简单图--每对顶点之间至多只有一条边相连。给定一个顶点序列{i,…,j

},如果相邻两个顶点都有边相连，那么，该顶点序列定义了一条以i,j为端点的路径(path).如果两个顶点有路径相连，称作两个顶点是连通的。7.1哥尼斯堡七桥问题ABCD七桥问题中顶点的阶数Euler问题的图论表述：给定一个图G,什么条件下通过每条边仅一次的封闭路径是存在的？直观的必要条件：

图G必须是连通的，即任意两个顶点都有路径相连(连通图)；

图G的所有顶点的阶数是偶数-进入和离开每个顶点的次数相同7.1哥尼斯堡七桥问题Euler问题有解

图G是连通的；

图G所有顶点的阶数是偶数哥尼斯堡七桥问题是无解的：没有一条路径经过每座桥各一次，再回到出发地。松弛Euler问题：经过每座桥各一次，但不要求回到出发点回路开路Euler图：图论中的重要类型和基础松弛Euler问题:什么条件下，在一个图G中能够找到一条路径经过每条边各一次？

图G是连通的；

图G仅有两个顶点阶数是奇数。7.1哥尼斯堡七桥问题8桥情况：松弛Euler问题有解4354ADCBDCAABDBACDABDC7.1哥尼斯堡七桥问题9桥情况：松弛Euler问题有解4455ACBDBABDBCACDAABDC如果9桥情况下想让Euler问题有解，第九座桥应如何建？44467.1哥尼斯堡七桥问题10桥情况：Euler问题有解4466ACBDBDBCAACDAB从任意一个顶点出发都可以经过所有桥一次再回到出发顶点。7.2地图着色问题(四色猜想-问题)什么是四色猜想？图中复杂的平面图形中，可以用四种颜色(红、黄、绿、蓝）把不同区域清楚标识，相邻区域颜色不同。该结论具有普适性吗？美国地图也可以用四种颜色标识不同的州。看来该结论似乎具有普适性---四色猜想。再看10000幅地图，也不能证明结论—数学从来不相信有限归纳。给定任意一个平面地图，“用四种颜色着色地图以便于任何两个具有共同边界(长度大于0)的区域用不同的颜色”是可能的吗?7.2地图着色问题(四色猜想-问题)从猜想到定理还留下什么？1852年，地图着色问题第一次被FrancisGuthrie正式提出，拉开了100多年的“四色猜想”证明历程。1890年，Heawood证明了“五色定理”，也就是任何的平面地图可以用五种颜色着色，相邻区域具有不同颜色。“百年转身”艰难但不完美，从1976年起，质疑从未平息。引发哲学级的思考：

计算机证明的正确性如何人工验证？

机器证明的理论基础和局限性何在？AI过热的时候，更需要冷静的脑袋—哲学思考KennethAppel

和

WolfgangHaken在1976年给出了“四色定理”的证明，但第一个主要定理的证明是通过计算机完成的。该证明被普遍认为是正确的，从而实现了从“四色猜想”到“四色定理”的艰难转身。7.2地图着色问题(四色猜想-问题)四色问题的图论建模我国行政区域的五色着色问题的解；非专业拼图业余爱好者作品。数学问题的难点不在于个例处理，而在于一个结论的“真理性”---边界条件内没有例外的普适性。。四色问题的图论描述：仅用四种颜色，能够对任意平面图的顶点进行着色以便相邻顶点具有不同颜色吗？7.2地图着色问题(工程应用)通信网络基站配置问题如右图所示，在西安市城区布置了很多手机基站，各基站覆盖范围相互重叠，为了减少基站间的信号相互干扰，各基站采用不同的正交码组(正交码组之间即使区域重叠也互不干扰)，这样的码组至少需要多少个？正交码组在基站间如何配置？试建立数学模型并给出解决问题的思路。7.2地图着色问题(工程应用)图论建模方法用每个基站作为图的顶点；

如果两个基站覆盖区域相互重叠，基站对应的顶点用一条边相连(表示这两个顶点是邻接的)；

按照“四色定理”，平面图可用四种不同颜色着色，相邻顶点颜色不同；颜色对应正交码组；因此，理论上四个正交码组就足够了！

正交码组配置问题转化为平面图的着色问题！四个正交码组7.2地图着色问题(工程应用)平面图：存在一种顶点配置模式，使得图在该顶点配置下边是互不相交的，或者边把平面分割为以图的顶点为顶点的互不重叠的多边形区域。顶点位置移动7.2地图着色问题(工程应用)衍生问题

网络中出现少量三小区交叠区域和四小区交叠区域情况下，牵扯到更复杂的图的四色着色问题。

对于涉及三或四小区交叠的基站必须采用不同的正交码组；在这些着色确定的情况下，再对其它顶点进行着色---残图着色问题。

如果出现五小区交叠情况，四个正交码组是不够的，至少需要5个正交码组。四小区交叠区域7.3旅行商问题(TSP问题)-赋值图给定一个城市列表以及每两个城市之间的距离，找出一条最短的行程，经过每个城市各一次并最终返回出发城市。(TravellingSalesmanProblem---19世纪由以色列数学家W.R.Hamilton和英国数学家ThomasKirkman首次作为数学问题正是提出，该问题的研究一直持续到今天。从中衍生出了许多求解算法和实际应用问题：邮递员问题、电子线路布线问题、DNA序列分析等)。西安银川兰州西宁拉萨成都400km900km乌鲁木齐600km800km500km1200km2000km1500km1300km1000km1200km

部分城市间航线由于航班数目太少而忽略；

各城市可以看成一个平面图G的顶点，城市间的航线看成连接顶点的边；航线里程可以看成边的赋值。从而产生了一个赋值平面图。

图必须是连通的，任意两个顶点有路径相连；否则问题无解。7.3旅行商问题(TSP问题)-赋值图123567400km1000km4600km800km500km1200km2000km1500km1300km1000km1200km赋值图的表示V(G)={1,2,…,7}-顶点集E(G)={…}---边集合关联矩阵C赋值矩阵W7.3旅行商问题求解大多数旅行商问题的应用中，节点之间的距离满足三角不等式,意味着城际间没有捷径可走(绕道总比直达远）。

如果城际旅行中，城市间边的赋值是旅行时间，三角不等式将不再成立(由于各城市间旅行交通工具上的差异，例如：如果通过铁路旅行，合肥-北京花费的时间肯定比合肥-南京-北京花费的时间长)。这时的TSP问题变成：找出化费时间最少且经过每个城市各一次的旅行路线。欧几里德TSP问题很多实际问题中，经过每个城市仅一次的要求可以放松为“经过每个城市至少一次”，这样可对问题求解带来一些方便。

赋值图不满足三角不等式情况下旅行商问题:非欧几里德TSP问题7.3旅行商问题求解TSP问题的求解被证明是NP-hard的，意味着：“随着城市数目增加，任何求最优路径算法的计算时间随着城市数目至少是指数增长的”。因此，各种求“次最优，suboptimal”解的算法应运而生：

神经网络方法；

遗传算法；

线性规划；

马尔科夫链方法；

蚁群算法。。。。。。越是疑难杂症，“能治”的医生就越多！7.3旅行商问题求解来自生物启发的蚁群算法

群体智慧和体验的优势；在大群体和大时间跨度下，走的人多的常常是某种意义下的“最优路线”。7.3旅行商问题求解上面提到的各种方法都用到了高深的数学理论，如果没有现成软件可利用，很难自己实现，数学建模中碰到类似问题，如何解决？！最近邻算法(NearestNeighborhood算法)=贪婪策略：旅行商总是选择最近的没有访问的城市作为下一个访问城市。大量的随机分布城市实验表明：算法得到的平均路径长度比最短路径长25%。星际旅行路线寻优7.3旅行商问题求解最近邻算法介绍连通赋值图的最短路径问题：在一个连通赋值图G中，求任意两点之间的最短路径。123450.150.10.120.090.50.20.10.251-5的路径：1-4-5(0.3),1-3-5(0.35),1-3-4-5(0.32),1-2-5(0.65),1-2-3-5(0.49),1-2-3-4-5(0.46)最短路径是：1-4-5===0.3.

类似地，在图G中可以求出任意两点之间的最短路径，所有最短路径作为两个顶点之间连接的边构成了一个完全图(任意两个顶点之间都有边相连）。

连通图中最短路径的求法已经有成熟的算法Matlab2012中的库函数[dist,path]=graphshortestpath(G,S)细节看库函数的说明。7.3旅行商问题求解3450.150.10.120.090.50.20.10.25123450.150.10.120.090.310.20.10.220.30.2112最短路径构成的完全图13245选择从1出发到其他城市的最短路径可选择顶点{4,5}可选择顶点{2,4,5}7.3旅行商问题求解3450.150.10.120.090.310.20.10.220.30.2112最短路径：1:2----{1,2}1:3---{1,3}1:4---{1,4}1:5---{1,4,5}2:3---{2,3}2:4---{2,3,4}2:5---{2,3,4,5}3:4---{3,4}3:5---{3,4,5}4:5---{4,5}最近邻算法{1,3},0.1{3,2},0.09{2,3,4},0.21{4,5},0.1最优行程：132345410.1+0.09+0.21+0.1+0.3=0.8

7.4交通问题-有向赋值图随着家庭用小汽车在大城市中的日益普及，交通拥堵问题变成了大城市的“难治顽疾”。“限号出行”，“单行线”等应急措施的出台虽有所缓解，但北京城区的上班族亦然把一天1/8的时间消耗在路上。“单行线”也使得交通网络更为复杂，很多路段难以实现“原路返”。交通网络描述从“无向赋值图”变成了“有向赋值图”。道路四通八达，人“四不通”“八不达”“自行车”笑傲“宝马”，我走了，你等着7.4交通问题-有向赋值图0.99全是单行道的6个十字路口的交通线路图赋值矩阵表示:非零元素稀疏矩阵非对称列表表示7.4交通问题-有向赋值图库函数使用交通问题中，更多关心的是从一个顶点到另一个顶点的最短路径问题：

在交通不很拥堵的时期，主要考虑的是最短路程的路径；边的赋值是距离。

今天城市交通中，更多考虑的是花费最短时间的路径；边的赋值是时间。[dist,path]=graphshortestpath(DG,1,6)最短路径长度最短路径连接赋值列表出发节点到达节点动态交通问题：实际交通网络中，各交通线路上拥堵情况随时间周期性变化，图的赋值用时间的函数代替，这样导致了动态交通问题。在赋值函数连续变化的情况下如何根据现在的最优路径微调得到下一时段的最优路径是经常考虑的问题。7.5有障碍最短路径几何建模设有一个半径为r的圆形湖，圆心为O。A、B

位于湖的两侧，AB连线过O，见图。现拟从A点步行到B点，在不得进入湖中的限制下，问怎样的路径最近。ABOrEFE′F′将湖想象成凸出地面的圆木，在AB间拉一根软线，当线被拉紧时将得到最短路径。根据这样的想象，猜测可以如下得到最短路径：过A作圆的切线切圆于E，过B作圆的切线切圆于F。最短路径为由线段AE、弧EF和线段FB连接而成的连续曲线（根据对称性，AE′，弧E′F′，F′B连接而成的连续曲线也是）

切线AE,BF,AE’,BF’和弧EF和E’F’围成的平面图形有何特点？7.5有障碍最短路径几何建模定义2.1（凸集）称集合R为凸集，若x1、x2∈R及λ∈[0，1]，总有λx1+（1+λ）x2∈R。即若x1、x2∈R，则x1、x2的连线必整个地落在R中。凸集非凸集凸多边形非凸多边形平面凸集的定义7.5有障碍最短路径几何建模对平面凸集R与R外的一点K，存在直线l,l

分离R与K，即R与K分别位于l的两侧（注：对高维空间的凸集R与R外的一点K，则存在超平面分离R与K），见图。凸集分离定理KlRKRp7.5有障碍最短路径几何建模由AE、EF、FB及AE′，E′F′，F′B围成的区域

是凸集；设Γ为最短路径，Γ过

外的一点M，则必存在直线l分离M与

，由于路径Γ是连续曲线，由A沿Γ到M，必交l于M1，由M沿Γ到B又必交l于M2。直线段M1M2的长度必小于路径M1MM2的长度，与Γ是A到B的最短路径相矛盾；因此最短路径必然在凸集

内。最短路径证明ABOrEFE′F′M1M2MΓl设路径经湖的上方到达B点，则弧EF必在路径上，又直线段AE是由A至E的最短路径，直线FB是由F到B的最短路径。7.5有障碍最短路径几何建模最短路径的证明ABOrEFE′F′

如图所示：E,F是过A,B点圆的切线的切点，E’和F’是圆上的另外两个非切点。我们需要证明：路径:线段AE+圆弧EF+线段BF<路径：线段AE’+圆弧E’F’+线段BF’注意：点E’和F’必然在圆弧EF之外的弧段上。线段AE’+弧段E’E>线段AE(两点之间的路径直线段最短)7.5有障碍最短路径几何建模如果障碍区域是一个被封闭曲线包围的平面凸集

，A,B是凸集外的两点，那么最短路径必然是包含,A和B的最小凸集的边界线被A和B分割的两段曲线中短的一条。

推而广之-I-凸障碍区域

AB

AB7.5有障碍最短路径几何建模如果障碍区域是一个被封闭曲线包围的平面非凸集

，A,B是在包含的最小凸集外的两点，那么最短路径必然是包含,A和B的最小凸集的边界线被A和B分割的两段曲线中短的一条。

推而广之-II-非凸障碍区域问题ABl1l2DAB

7.5有障碍最短路径几何建模若可行区域的边界是光滑曲面。则最短路径必由下列弧组成，它们或者是空间中的自然最短曲线，或者是可行区域的边界弧。而且，组成最短路径的各段弧在连接点处必定相切。注：在平面上可行区域是指障碍区域的补集。注：该定理在1973年被J.W.Craggs证明。推而广之-III-多障碍区域问题障碍区域障碍区域ABC1C27.5有障碍最短路径几何建模实际应用-小汽车移库问题一辆汽车停于A处并垂直于AB方向，此汽车可转的最小圆半径为R，求不倒车而由A到B的最短路径。情况1：AB>2RABR7.5有障碍最短路径几何建模实际应用-小汽车移库问题一辆汽车停于A处并垂直于AB方向，此汽车可转的最小圆半径为R，求不倒车而由A到B的最短路径。情况2：AB<2RABAB两条路径中较短的一条7.5有障碍最短路径几何建模实际应用-小汽车移库问题假设一辆停于A处与AB成θ1角度的汽车到B处去，已知B处要求的停车方向必须与AB成θ2角，试找出最短路径(除可转的最小圆半径为R外，不受其它限止)。

1

2C1C2两条路径中较短的一条AB7.6岛礁巡航问题近百年来，民族的屈辱史从海上开始。今天，从陆地大国走向海洋大国的路途漫长而曲折，海权维护仍旧是我们心中的痛！美丽的黄岩岛钓鱼岛南海诸岛造岛神器"天鲸"号自航绞吸式挖泥船总长127.5m，型宽22m，吃水6m，设计航速12节，总装机功率为19200KW，最大挖深-30m，最大排泥距离6000m