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

实验数学时空第八讲图论概念和一笔画问题 （教材：第八章图论概念和一笔画问题） ? 一．图的基本概念 二．欧拉环游及弗莱里算法 三．中国邮递员问题 四．实际问题应用举例 一．图的基本概念 图 现实生活中，我们经常碰到一些现象，如：在一群人中有些人互相认识，有些人互相不认识。又如：某航空公司在100个城市之间建立若干航线，某些城市间有直达航班，而另一些城市间没有直达航班等等。以上现象都有共同内容：一是有研究的“对象”，如人，城市等；二是这些对象之间存在着某种关系：如互相认识，有直达航班等。为了表示这些对象以及对象之间的关系，我们将“点”代表“对象”，“边”表示“对象之间的关系”，引出了“图”这个概念。 图：由若干个不同的点与连接其中某些顶点的边所组成的图形，称为图。 由此可见，图有二要素：“点”和“边”：“点”表示对象，“边”反映对象之间的关系。图由顶点集和边集构成，我们记为G(V,E)。 注解：这里点和边并不是通常的欧氏空间内的对象，例如，这里边没有“长度”的概念，边不是由点构成等等。因而我们用纸上的几何图形来表示图时，点的位置、边的长度、曲直都无关紧要，但是点和点是否有边连接是一定的。 ? 网络：对图中的顶点和边赋以具体的含义和权，这样的图称为网络。 边e可以表示为e＝（），称和是边e的端点，边e与点和关联。 次：与某一点关联的边的数目称为点的次。 奇点：次为奇数的点。 偶点：次为偶数的点。 对于图G中一个点、边交错的序列 链：如果，且互不相同，称这个序列是到的链。 闭链：如与相同，称这条链为闭链。 路：如果链中的各点也不同，称这样的链为路。 圈：如互不相同的闭链称为圈。 连通：若G中两点u和v之间存在路，则称u和v是连通的。连通关系是一种等价关系，可以把图中的点分成若干部分，使得同一部分的点总是连通的，不同的部分总是不连通的。每个部分连同连接它们的边（两个端点都在同一部分的边）称为组成G的一个分图。 注解：要说明连通关系是等价关系，只要说明连通关系具有下面三个性质： 1、每一个点自己总是和自己连通的； 如果u和v连通，则v和u也是连通的；如果u和v连通，v和w连通，则u和w也连通。） 若G只有一个分图，则G是连通的。 在一个网络N=(V,E,W)中， 环游：经过N中每一边至少一次的闭链称为N的环游。 欧拉环游：经过N中每一边恰好一次的环游称为欧拉环游。可见，“能一笔画”的图即该图“有欧拉环游”。 注意：若N有欧拉环游，则它的每个欧拉环游具有相同的权，也是最优环游。 ? 二．欧拉环游及弗莱里算法 这里看一个著名的“七桥问题”：流经哥尼斯堡的普雷格河的河湾有两个小岛，七座桥连接了两岸和小岛（如图1），当地流传一个游戏：要求在一次散步中恰好通过每座桥一次 图1?????????? ????图2?????????????? 图3????????????????? 图4 在这个问题中，我们可以将“两个小岛和两岸”看成“点”。连接他们之间的“七座桥”看成“边”，得到图2。 ?? “七桥问题”可以归结为“一笔画”问题：即能否用一支笔不离开纸面地画出经过所有桥一次的路线。用图论的术语，就是一个图是否存在欧拉环游？如果有，如何找出来？ ? 一个图存在欧拉环游的条件是： 网络N有欧拉环游当且仅当N中每一点的次为偶数。 一般地，一个图能“一笔画”（不要求回到起点），当且仅当该图或没有奇点，或只有2个奇点。 利用上述结论，我们判定“七桥问题”不能实现“一笔画”，因为七桥问题中的图有4个奇点。 ? ???但是要注意，一个图存在欧拉环游，如果方法不对，仍然可能找不到具体的欧拉环游。如图3： 如果从A出发我们沿ABCA取一条路，则就不可能再继续从A出发，走遍余下的边。 上面的例子说明找欧拉环游必须要遵循一定的准则。这就是求一个图的欧拉环游的弗莱里算法。 弗莱里算法可求得N的最优环游。 计算步骤： 1)任意选取N的一个顶点，置。 2)假设链已选定，从中按下述方法选取: (1)和相关联。 (2)尽量不选（是中去掉边而得到的图）的割边（即去掉此边后，图变为不连通），除非没有非割边可选择。 3)设另一关联点。若,重复步骤2);否则即为N的一条欧拉环游。 〔例1〕：已知N（图G）有欧拉环游，求N的欧拉环游。 图G  HYPERLINK /zsb/zsx/zsx07/zsx078/MAIN8/zsx078009.htm \t _blank 解答（例题解答： (1)选取N的一个顶点; (2)B,C,D都与A相邻，取; (3)从中选取，A,C,E都与B相邻，图G去掉得到图 图 根据弗莱里算法，要求不能是图的割边，与B相关的三条边中都不是图的割边，可任选一条，不妨就选。 (4)从选取，C,D都与A相邻，图G去掉,得到图 图 ,都不是图的割边，可任选一条，不妨就选