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

《图论概念和一笔画问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论概念和一笔画问题数学建模简明教程第八章图论概念和一笔画问题§1图的基本概念为了表示对象以及对象之间的关系，我们可以在纸上画一些点和线。每一点代表一个对象，称这些点为顶点，简称点；如果两个对象之间有所讨论的关系，我们就在相应的两点之间用线连接，称这些线为边。这样就构成了一个几何图形，这种由若干种不同的顶点与连接其中某些顶点的边所组成的图形，称为图。图有两个要素：点，边点表示对象，边反映对象之间的关系顶点组成的集合称为顶点集，记作V，边组成的集合称为边集，记作E。图由（V，E）组成，记作G=(V，E)。若给出一个图G，G的顶点集可用V(G)，G的边集可用E(

2、G)表示，G的顶点数可用∣G∣表示。如果对图G的每条边赋一个相应的数（称为边的权），G连通边上的权称为赋权图。如果对图中的顶点和边赋以具体的含义和权，这样的图称为网络。若边e表示为，这时称和是边e的端点，便e与点或关联。两点相邻：如果两个点与同一条边关联。两边邻接：如果两条边有一个公共端点。环：两个端点重合的边。重边：具有两个公共端点的两条边。孤立点：不与任何边关联的点。简单图：一个既没有换也没有重边的图。空图：没有任何边的图。平凡图：只有一点的图。点的次：与关联的边的条数，记作或＊注意：在计算点的次时，环作两条边计算，孤立点的次为0奇点：次为奇数的点；偶点

3、：次为偶数的点。和分别表示图G的最大次和最小次。链：设图G中有一个点边交错的序列，如果，且互不相同，则称这个序列是从到的链。和称为这条链的两个端点。闭链：如果和相同，则称这条链是闭链路：各顶点互不相同的链圈：除初始顶点外，各顶点互不相同的闭链点连通:图G中存在点u到点v的路分图：图G中连通的顶点连同边构成的图连通图：只有一个分图的图完全图：任意两点之间均有边连接的简单图偶图（二分图）：顶点集是两个互不相交的非空集合，并且同一个集合中任意两顶点均不相邻的简单图完全偶图：两顶点集中每一对不同集合的顶点之间都有一条边相连的偶图子图：若图G1的顶点集包含于图G2的顶

4、点集，图G1的边集包含于图G2的边集，则称图G1是图G2的子图生成子图：若图G1、图G2的顶点集相同，图G1的边集包含于图G2的边集，则称图G1是图G2的生成子图§2一笔画问题与中国邮递员问题邮递员从邮局中取出邮件，递送到不同地点，然后再返回邮局。假设要求他至少一次走过他投递范围内的每一条街道，我们希望选择一条尽可能短的路线。这个问题称为中国邮递员问题，因为他是由我国数学家管梅谷首先研究的。欧拉链：在一个网络N中，经过它的每条边的链N的环游：经过N中每条边至少一次的闭链欧拉环游：经过N中每条边恰好一次的环游一个图能一笔画就是该图就有欧拉环游若N有欧拉环游，则

5、它的每一条欧拉环游具有相同的权，它也必然是最优环游。对有欧拉环游的网络，我们可以用弗莱里算法求得N的最优环游弗莱里算法计算步骤如下：⑴任意取N的一个顶点，置于Z=⑵假设链已选定，从中按下述方法选取：①和相关联；尽量不选（是G中去掉边而得到的图）的割边（即去掉此边后，图变为不连通），除非没有非割边可选择。⑶设另一关联点。若，重复步骤⑵；否则即为N的一条欧拉环游若网络N没有欧拉环游，此时最优环游通过的某些边将超过一次。例如图8.4(a)的图中xuywvzwyxuwvxzyx是最优环游，此时四条边ux,xy,yw和wv都被这环游通过两次。图8.4下面是一种有关引进

6、重复边的算法。将边e的两个端点再用一条权为w(e)的新边连接时，称为边e的重复边。因此，中国邮递员问题可以重新叙述如下：给定一个具有非负权的网络N，①用添重复边的方法求得N的一个欧拉赋权母图N+，使得尽可能小；②求N+的欧拉环游。解②可用弗莱里算法；解①可用爱德蒙斯和约翰逊算法,这里不作介绍。当点数较少时，可用奇偶点图上作业法。结论1网络N有欧拉环游当且仅当N中每一点的次数为偶数。结论2最优环游具有这样的性质：⑴每条边至多重复重复一次；⑵每一圈上重复边的长度不超过该圈总长的一半。当某一圈上重复边的长度超过该圈总长的一半时，将该圈中所有重复边去掉，该圈中未重复

7、的边重复，从而的奇偶点作图法如下：⑴若N每一点的次均为偶数，则用弗莱里算法求得其欧拉环游，此即为N的最优环游。⑵若不然，则用添重复边的办法得到N的欧拉赋权母图N*。求得N*的欧拉环游。（用弗拉里算法）⑶若某一条边在欧拉赋权母图N*中重复多次，只要去掉该边的偶数次重复边，总可以使得该边至多重复一次，这样的图仍为欧拉赋权母图。⑷然后逐一检查N*的每一圈，当某一圈上重复边的长度超过该圈总长的一半时，将该圈中的所有重复边去掉，该圈中的未重复的边重复，所得到的图也是欧拉赋权母图。例设某邮递员负责投递邮件的街道如图8.5(a)所示，求出该邮递员的最短投递路线。解该网络中

8、有8个奇点：用添重复边的办法得到图8.5(b)按结论