图论概念和一笔画问题.ppt

图论概念和一笔画问题,数学建模简明教程,第八章图论概念和一笔画问题,1图的基本概念为了表示对象以及对象之间的关系，我们可以在纸上画一些点和线。每一点代表一个对象，称这些点为顶点，简称点；如果两个对象之间有所讨论的关系，我们就在相应的两点之间用线连接，称这些线为边。这样就构成了一个几何图形，这种由若干种不同的顶点与连接其中某些顶点的边所组成的图形，称为图。,图有两个要素：点，边点表示对象，边反映对象之间的关系顶点组成的集合称为顶点集，记作V，边组成的集合称为边集，记作E。图由（V，E）组成，记作G=(V，E)。若给出一个图G，G的顶点集可用V(G)，G的边集可用E(G)表示，G的顶点数可用G表示。如果对图G的每条边赋一个相应的数（称为边的权），G连通边上的权称为赋权图。如果对图中的顶点和边赋以具体的含义和权，这样的图称为网络。,若边e表示为，这时称和是边e的端点，便e与点或关联。两点相邻：如果两个点与同一条边关联。,两边邻接：如果两条边有一个公共端点。环：两个端点重合的边。重边：具有两个公共端点的两条边。孤立点：不与任何边关联的点。简单图：一个既没有换也没有重边的图。空图：没有任何边的图。平凡图：只有一点的图。点的次：与关联的边的条数，记作或注意：在计算点的次时，环作两条边计算，孤立点的次为0奇点：次为奇数的点；偶点：次为偶数的点。和分别表示图G的最大次和最小次。,链：设图G中有一个点边交错的序列，如果，且互不相同，则称这个序列是从到的链。和称为这条链的两个端点。闭链：如果和相同，则称这条链是闭链路：各顶点互不相同的链圈：除初始顶点外，各顶点互不相同的闭链点连通:图G中存在点u到点v的路分图：图G中连通的顶点连同边构成的图连通图：只有一个分图的图完全图：任意两点之间均有边连接的简单图偶图（二分图）：顶点集是两个互不相交的非空集合，并且同一个集合中任意两顶点均不相邻的简单图,完全偶图：两顶点集中每一对不同集合的顶点之间都有一条边相连的偶图子图：若图G1的顶点集包含于图G2的顶点集，图G1的边集包含于图G2的边集，则称图G1是图G2的子图生成子图：若图G1、图G2的顶点集相同，图G1的边集包含于图G2的边集，则称图G1是图G2的生成子图,2一笔画问题与中国邮递员问题邮递员从邮局中取出邮件，递送到不同地点，然后再返回邮局。假设要求他至少一次走过他投递范围内的每一条街道，我们希望选择一条尽可能短的路线。这个问题称为中国邮递员问题，因为他是由我国数学家管梅谷首先研究的。欧拉链：在一个网络N中，经过它的每条边的链N的环游：经过N中每条边至少一次的闭链欧拉环游：经过N中每条边恰好一次的环游一个图能一笔画就是该图就有欧拉环游若N有欧拉环游，则它的每一条欧拉环游具有相同的权，它也必然是最优环游。对有欧拉环游的网络，我们可以用弗莱里算法求得N的最优环游,弗莱里算法计算步骤如下：任意取N的一个顶点，置于Z=假设链已选定，从中按下述方法选取：和相关联；尽量不选（是G中去掉边而得到的图）的割边（即去掉此边后，图变为不连通），除非没有非割边可选择。设另一关联点。若，重复步骤；否则即为N的一条欧拉环游,若网络N没有欧拉环游，此时最优环游通过的某些边将超过一次。例如图8.4(a)的图中xuywvzwyxuwvxzyx是最优环游，此时四条边ux,xy,yw和wv都被这环游通过两次。图8.4,下面是一种有关引进重复边的算法。将边e的两个端点再用一条权为w(e)的新边连接时，称为边e的重复边。因此，中国邮递员问题可以重新叙述如下：给定一个具有非负权的网络N，用添重复边的方法求得N的一个欧拉赋权母图N+，使得尽可能小；求N+的欧拉环游。解可用弗莱里算法；解可用爱德蒙斯和约翰逊算法,这里不作介绍。当点数较少时，可用奇偶点图上作业法。结论1网络N有欧拉环游当且仅当N中每一点的次数为偶数。,结论2最优环游具有这样的性质：每条边至多重复重复一次；每一圈上重复边的长度不超过该圈总长的一半。当某一圈上重复边的长度超过该圈总长的一半时，将该圈中所有重复边去掉，该圈中未重复的边重复，从而的奇偶点作图法如下：若N每一点的次均为偶数，则用弗莱里算法求得其欧拉环游，此即为N的最优环游。若不然，则用添重复边的办法得到N的欧拉赋权母图N*。求得N*的欧拉环游。（用弗拉里算法）若某一条边在欧拉赋权母图N*中重复多次，只要去掉该边的偶数次重复边，总可以使得该边至多重复一次，这样的图仍为欧拉赋权母图。然后逐一检查N*的每一圈，当某一圈上重复边的长,度超过该圈总长的一半时，将该圈中的所有重复边去掉，该圈中的未重复的边重复，所得到的图也是欧拉赋权母图。例设某邮递员负责投递邮件的街道如图8.5(a)所示，求出该邮递员的最短投递路线。解该网络中有8个奇点：用添重复边的办法得到图8.5(b)按结论2进行调整，圈总长为12，而重复边长为11，此时去掉重复边添加重复边。同样在圈中其总长为21，重复边长为12也超过一半。经调整后得新的网络图8.5(c)。检查8.5(c)的每一个圈，其重复边的长度均不大于该圈长的一半，因此用弗拉里算法求得8.5(c)中网络的欧拉环游即为要求的最优环游。,图8.5(a),图8.5(b),图8.5(c),3城镇道路扫学模型教材第104页上，图8.6（a）中的实线表示美国马里兰州威克尔米市需要清除积雪的双向行车道路，虚线是州高速公路。雪后两辆扫雪车分别从地图*号标出的两点以西约4英里处出发清扫道路上的积雪。扫雪车可以通过高速公路进入市内道路。假定扫雪过程中扫雪车不会损坏或停止，并且道路交叉处不需要另外附加的扫雪程序。试为两车找出有效的路径。1.问题的分析我们的目的是寻求一个有效的办法用两台扫雪车清除威克米尔市内道路（不包括州高速公路）的积雪。,这个问题的有效解法有以下特点：(1)扫完全部路面所花的时间尽量少。(2)扫雪完毕后，两车应尽快回到出发点。(3)两车工作时间大致相同。对于(1)，我们认为，如果扫雪车没有重复走某一条路，或重复走的路径和最小，则扫雪所花时间少。在(1)和(2)的情况下，如果只有一辆扫雪车，即可归结为中国邮递员问题。对于(3)，两车工作时间大致相同，即要求两车走过的路程和大致相同，这也是要求（1）的自然结论。因此可将该图划为两个子图，使这两个子网络的权尽可能的相等。,2模型的假设可作如下的假设：(1)扫雪过程中没有下雪，所有室内道路都有积雪需要清除。(2)两辆扫雪车性能相同，都能正常工作。(3)两辆扫雪车司机驾驶技术相同，扫雪时，车速相同。(4)在所有交叉路口，包括室内道路与高速公路的接口，扫雪车可不减速地转弯。(5)两辆车出发的时间相同。(6)每条路面的积雪范围、厚度相同。3模型的建立(1)双行道问题假设：每条道路有两条相反的行车道。,A可将地图中每个交叉路口看成点，每条市内道路看成边，道路的长度看成该边对应的权，这样就将地图变成一个网络N（V,E,W）B由假设，每条道路均是双行道，即网络N上的点均为偶点，由上一节的结论1可知，该网络N是一个欧拉有向图，可用弗莱里算法求得N的欧拉环游。C若只有一辆扫雪车，该问题转化为中国邮递员问题。现在有两辆扫雪车，工作性能完全相等，要使工作时间尽量少，我们可将网络N分成两个子网络和和均连通，且两网络的权尽可能相同。可用如下方法实现网络的分割：把网络N分成两个连通子网络，分别算出两个子网络中所有边的总长度。由于N,的总边长已知，在总长较大的子网络中划出一些与另一子网络相连的边，添加到总长较小的子网络中。(2)单行道问题先加对应的网络N分成两个子网络和。要求和子网络边总长度相等，再利用中国邮递员问题的解法，可以分别求得和的欧拉环游，得到近似解。注解4进一步讨论(1)不管双行道问题还是单行道问题，都须对原网络进行划分。可测量图中各路径的长度，并将数据输入计算机，由计算机划分网络。,(2)若两扫雪车性能不同，或出发时间不同等造成两车的差异，可将网络按比例划分。(3)若首先应该清扫主干道积雪，这就要考虑如何规定主干道。(4)若遇到大风，就要考虑顺风与逆风时车速不同等因素。,