admin 管理员组

文章数量: 888299

欧拉回路问题

文章目录

  • 欧拉回路
  • 程序设计
  • 程序分析

欧拉回路

有一条名为Pregel的河流经过Konigsberg城。城中有7座桥，把河中的两个岛与河岸连接起来。当地居民热衷于一个难题：是否存在一条路线，可以不重复地走遍7座桥。这就是著名的七桥问题。它由大数学家欧拉首先提出，并给出了完美的解答，如图所示。

欧拉首先把图(a)中的七桥问题用图论的语言改写成图(b)，则问题变成了：能否从无向图中的一个结点出发走出一条道路，每条边恰好经过一次。这样的路线称为欧拉道路（enlerian path），可以形象地称为“一笔画”。
不难发现，在欧拉道路中，“进”和“出”是对应的——除了起点和终点外，其他点的“进出”次数应该相等，换句话说，除了起点和终点外，其他点的度数应该有偶数。很可惜，在七桥问题中，所有4个点的度数均是奇数（这样的点也称为奇点），因此不可能存在欧拉道路。上述条件也是充分条件——如果一个无向图是连通的，且最多只有两上奇点，则一定存在欧拉道路。如果有两个奇点，则必须从其中一个奇点出发，另一个奇点终止；如果奇点不存在，则可以从任意点出发，最终一定会回到该点（称为欧拉回路࿰

本文标签： 欧拉回路问题

版权声明：本文标题：欧拉回路问题 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1686635453h20015.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。