实验数学时空第八讲图论概念和一笔画问题.doc

《实验数学时空第八讲图论概念和一笔画问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验数学时空第八讲图论概念和一笔画问题（教材：第八章图论概念和一笔画问题） 一．图的基本概念二．欧拉环游及弗莱里算法三．中国邮递员问题四．实际问题应用举例一．图的基本概念图现实生活中，我们经常碰到一些现象，如：在一群人中有些人互相认识，有些人互相不认识。又如：某航空公司在100个城市之间建立若干航线，某些城市间有直达航班，而另一些城市间没有直达航班等等。以上现象都有共同内容：一是有研究的“对象”，如人，城市等；二是这些对象之间存在着某种关系：如互相认识，有直达航班等。为了表示这些对象以及对象之间

2、的关系，我们将“点”代表“对象”，“边”表示“对象之间的关系”，引出了“图”这个概念。图：由若干个不同的点与连接其中某些顶点的边所组成的图形，称为图。由此可见，图有二要素：“点”和“边”：“点”表示对象，“边”反映对象之间的关系。图由顶点集和边集构成，我们记为G(V,E)。注解：这里点和边并不是通常的欧氏空间内的对象，例如，这里边没有“长度”的概念，边不是由点构成等等。因而我们用纸上的几何图形来表示图时，点的位置、边的长度、曲直都无关紧要，但是点和点是否有边连接是一定的。 网络：对图中的顶点和边

3、赋以具体的含义和权，这样的图称为网络。边e可以表示为e＝（），称和是边e的端点，边e与点和关联。次：与某一点关联的边的数目称为点的次。奇点：次为奇数的点。偶点：次为偶数的点。对于图G中一个点、边交错的序列链：如果，且互不相同，称这个序列是到的链。闭链：如与相同，称这条链为闭链。路：如果链中的各点也不同，称这样的链为路。圈：如互不相同的闭链称为圈。连通：若G中两点u和v之间存在路，则称u和v是连通的。连通关系是一种等价关系，可以把图中的点分成若干部分，使得同一部分的点总是连通的，不同的部分总是不连

4、通的。每个部分连同连接它们的边（两个端点都在同一部分的边）称为组成G的一个分图。注解：要说明连通关系是等价关系，只要说明连通关系具有下面三个性质：1、每一个点自己总是和自己连通的；如果u和v连通，则v和u也是连通的；如果u和v连通，v和w连通，则u和w也连通。）若G只有一个分图，则G是连通的。在一个网络N=(V,E,W)中，环游：经过N中每一边至少一次的闭链称为N的环游。欧拉环游：经过N中每一边恰好一次的环游称为欧拉环游。可见，“能一笔画”的图即该图“有欧拉环游”。注意：若N有欧拉环游，则它的每

5、个欧拉环游具有相同的权，也是最优环游。 二．欧拉环游及弗莱里算法这里看一个著名的“七桥问题”：流经哥尼斯堡的普雷格河的河湾有两个小岛，七座桥连接了两岸和小岛（如图1），当地流传一个游戏：要求在一次散步中恰好通过每座桥一次图1              图2              图3                 图4在这个问题中，我们可以将“两个小岛和两岸”看成“点”。连接他们之间的“七座桥”看成“边”，得到图2。  “七桥问题”可以归结为“一笔画”问题：即能否用一支笔不离开纸面地画出经

6、过所有桥一次的路线。用图论的术语，就是一个图是否存在欧拉环游？如果有，如何找出来？ 一个图存在欧拉环游的条件是：网络N有欧拉环游当且仅当N中每一点的次为偶数。一般地，一个图能“一笔画”（不要求回到起点），当且仅当该图或没有奇点，或只有2个奇点。利用上述结论，我们判定“七桥问题”不能实现“一笔画”，因为七桥问题中的图有4个奇点。    但是要注意，一个图存在欧拉环游，如果方法不对，仍然可能找不到具体的欧拉环游。如图3：如果从A出发我们沿ABCA取一条路，则就不可能再继续从A出发，走遍余下的边。上面

7、的例子说明找欧拉环游必须要遵循一定的准则。这就是求一个图的欧拉环游的弗莱里算法。弗莱里算法可求得N的最优环游。计算步骤：1)任意选取N的一个顶点，置。2)假设链已选定，从中按下述方法选取:(1)和相关联。(2)尽量不选（是中去掉边而得到的图）的割边（即去掉此边后，图变为不连通），除非没有非割边可选择。3)设另一关联点。若,重复步骤2);否则即为N的一条欧拉环游。〔例1〕：已知N（图G）有欧拉环游，求N的欧拉环游。图G解答（例题解答：(1)选取N的一个顶点;(2)B,C,D都与A相邻，取;(3)从

8、中选取，A,C,E都与B相邻，图G去掉得到图图根据弗莱里算法，要求不能是图的割边，与B相关的三条边中都不是图的割边，可任选一条，不妨就选。(4)从选取，C,D都与A相邻，图G去掉,得到图图,都不是图的割边，可任选一条，不妨就选(5)从选取，B,D,E都与C相邻，图G去掉，得到图图都不是图的割边，可任选一条，不妨就选(6)从选取，A,D都与D相邻，图G去掉，得到图图两条边中，是图的割边，如果我们选,就找不出欧拉环游。所以我们应选。重复以上步骤，最后得到N的欧拉环游为。）三．中国邮递员问题问题提出：