《第十五章欧拉图.pptVIP

欧拉图 相关应用 例 一个邮递员投递信件要走的街道如下左图所示，图中的数字表示各条街道的千米数，他从邮局出发，要走遍各街道，最后回到邮局。怎样走才能使所走的行程最短？全程多少千米？ 哈密尔顿图 四、应 用：带权图与货郎担问题  定义15.3 给定图G = V, E(G为无向图或有向图), 设W: E→R(R为实数集), 对?e = (vi, vj)(vi, vj)?E(G), 设W(e) = wij, 称实数wij为边e上的权(Weight) 在G上, 将权wij标注在边e上, 称G为带权图 通常将带权图G记作V, E, W 称?e?E(G)W(e)为G的权, 记作W(G) Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 货郎担问题 设有n个城市, 城市之间有道路, 道路的长度均大于或等于0, 可能是∞(城市之间无交通线)。 一个旅行商从某个城市出发, 要经过每个城市一次且仅一次, 最后回到出发的城市, 问如何才能使他所走的路线最短？这就是著名的旅行商问题或货郎担问题。 这个问题可化归为图论问题。 设G = V, E, W为一个n阶完全带权图Kn, 各边的权非负, 且有些边的权可能为∞。求G中一条最短的哈密顿回路, 这就是货郎担问题的数学模型。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. * 定义 通过图G的每条边一次且仅一次的回路称为欧拉回路。存在欧拉回路的图，称为欧拉图。通过图G的每条边一次且仅一次的开路称为欧拉路，对应的有半欧拉图。 例1 下图所给出的四个图，哪些是欧拉图、半欧拉图？ Y N Y N 怎么样判断一个图是欧拉图或半欧拉图？ Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 定理15.1　 无向图G为欧拉图的充要条件G是连通图且没有奇度顶点。 定理15.2 无向图G是半欧拉图的充要条件G是连通的且恰有两个奇度的顶点。 或半欧拉图有且仅有两个奇点，一个为欧拉路的起点一个为欧拉路的终点。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 　 例2　　 下图中的各图是否可以一笔画出？ N Y Y N Y 一笔画问题？P296定理15.1 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 定理15.3　 有向图D为欧拉图的充要条件D是强连通图且每个顶点的入度等于出度。 定理15.4 有向图D是半欧拉图的充要条件D是单向连通的且恰有两个奇度的顶点，其中一个顶点的入度比出度大1，另一个顶点出度比入度大1，而其余顶点的入度等于出度。 定理15.5 G是非平凡的欧拉图的充要条件G是连通的且是若干个边不重的圈的并。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Y Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 哥尼斯堡七桥问题??? 18世纪哥尼斯堡（后来的加里宁格勒）位于立陶宛的普雷格尔上有7座桥，将河中的两个岛和河岸连结，如图1所示。城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。 瑞士数学家欧拉（Euler）解决 抽象出的图应该是？ Evaluation only.