第七讲-图论与几何模型

第七讲:图论与几何模型---水鹏朗雷达信号处理国防科技重点实验室数学建模实验(数学建模基础之续)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.简单图--每对顶点之间至多只有一条边相连。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问题有解4455ACBDBABDBCACDAABDC7.1哥尼斯堡七桥问题10桥情况：Euler问题有解4466ACBDBDBCAACDAB从任意一个顶点出发都可以经过所有桥一次再回到出发顶点。7.2地图着色问题(四色猜想-问题)什么是四色猜想？图中复杂的平面图形中，可以用四种颜色(红、黄、绿、蓝）把不同区域清楚标识，相邻区域颜色不同。该结论具有普适性吗？美国地图也可以用四种颜色标识不同的州。看来该结论具有普适性---四色猜想。再看10000幅地图，也不能证明结论—数学从来不相信有限归纳。给定任意一个平面地图，“用四种颜色着色地图以便于任何两个具有共同边界(长度大于0)的区域用不同的颜色”是可能的吗?7.2地图着色问题(四色猜想-问题)从猜想到定理还留下什么？1852年，地图着色问题第一次被FrancisGuthrie正式提出，拉开了100多年的“四色猜想”证明历程。1890年，Heawood证明了“五色定理”，也就是任何的平面地图可以用五种颜色着色，相邻区域具有不同颜色。“百年转身”艰难但不完美，从1976年起，质疑从未平息。引发了哲学级的思考：

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

机器证明的理论基础和局限性何在？KennethAppel

和

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

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

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

正交码组分配问题转化为平面图四色着色问题！四个正交码组7.2地图着色问题(工程应用)衍生问题

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

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

如果出现五小区交汇情况，四个正交码组是不够的。四小区交汇区域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问题在很多实际问题中，经过每个城市仅一次的要求可以放松为“经过每个城市至少一次”，这样可以对问题的求解带来一些方便。7.3旅行商问题求解TSP问题的求解被证明是NP-hard的，意味着：“随着城市数目的增加，任何求最优路径的算法的计算时间随着城市数目至少是指数增加的”。因此，各种求解“次最优，suboptimal”解的大量的算法应运而生：

神经网络方法；

遗传算法方法；

线性规划方法；

马尔科夫链方法；…….越是疑难杂症，“能治”的医生越多！上述提到的各种方法都用到了很高深的数学理论，如果没有现成软件可利用，很难自己实现，数学建模中碰到类似问题，如何解决？！最近邻算法(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围成的区域R是一凸集；设Γ为最短路径，Γ过R外的一点M，则必存在直线l分离M与R，由于路径Γ是连续曲线，由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有障碍最短路径几何建模如果障碍区域是一个被封闭曲线包围的平面凸集，A,B是凸集外的两点，那么最短路径必然是包含,A和B的最小凸集的边界线被A和B分割的两段曲线中短的一条。

推而广之-IABAB7.5有障碍最短路径几何建模如果障碍区域是一个被封闭曲线包围的平面非凸集，A,B是在包含的最小的凸集外的两点，那么最短路径必然是包含,A和B的最小凸集的边界线被A和B分割的两段曲线中短的一条。

推而广之-IIABl1l2DAB7.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外，不受其他限止)。12C1C2两条路径中较短的一条7.6