欧拉一笔画问题

哥尼斯堡七桥问题

• 度数
  • 每个点连接的线段数
• 奇点
  • 该点连接的线段数为奇数就称为奇点
  • 落笔或者收笔的点
• 偶点
  • 该点连接的线段数为偶点称为偶点
  • 经过的点

欧拉提出可一笔画的图形（1736年29岁的欧拉）

• 如果奇点的个数为0个或者2两个则这样的图形可以一笔画
  • 0个奇点可以形成==欧拉回路==
  • 2个奇点可以形成==欧拉路径==
• 一张图可以通过K笔画出,则奇点的个数必须为偶数(2K个)
  • K笔画数
  • 增加k-1条线,形成欧拉路径
  • 增加k条线,形成欧拉回路
• 开拓了一个数学分支==图论==

弗勒里算法

如果一张图可以一笔画画出,那弗勒里算法可以找出正确画图的方法

• 画一条线,删除一条线
• 不要把图断开

类似一笔画问题

• 汉密尔顿环游问题
• 中国邮递员问题
• 四色问题
• 旅行者推销问题

思考问题

有五个紧贴在一起的房间,相邻房间以及房间与外界的墙都有门,能否从从某一点出发穿越所有的门,而且每扇门只走一次