F623b968528866386df639ccb4df6200
欧拉回路

1 七桥问题

  当时东普鲁士科尼斯堡(今日俄罗斯加里宁格勒)市区跨普列戈利亚河两岸,河中心有两个小岛。小岛与河的两岸有七条桥连接。在所有桥都只能走一遍的前提下,如何才能把这个地方所有的桥都走遍?
图1.1

图1.1

2 问题解决

  著名数学家欧拉用A,B,C,D四个字母代表陆地,作为图的4个顶点,将连接两块陆地的桥作为边,将七桥问题转为数据结构中的图问题。由此得到的图如下:
图2.1

图2.1

  通过将实际问题转为数据结构图论问题,将问题转换为:是否存在每条边只经过一次,且经过所有顶点的回路问题。对于此问题采用欧拉回路的思想去求解。

3 重要概念

  通路:图G(v,e)中顶点与边交替出现的序列称为通路,记作:
  L = v0,e1,v1,e2,···en,vn
  通路L中边e的数目记作L的长度。
  回路:在通路中,若v0=vn,则此通路称为回路。
  简单通路:在通路L中,所有的边e1,e2···,en互不相同。
图3.1 简单通路

图3.1 简单通路

  简单回路:在回路中,所有的边e1,e2···,en互不相同。

图3.2 简单回路

图3.2 简单回路

  初级通路:所有顶点v0,v1,v2···,vn互不相同的通路

图3.3 初级通路

图3.3 初级通路

  初级回路:所有顶点v0,v1,v2···,vn互不相同的回路

图3.4 初级回路

图3.4 初级回路

top Created with Sketch.