第五章图论筒介 创始人 E Euler(瑞士数学家) 创立时间 18世纪 问题的提 歌尼斯堡七桥难题
E.Euler（瑞士数学家） 18世纪 创始人 创立时间 问题的提 出 歌尼斯堡七桥难题
※歌尼斯堡七桥难题 普莱格尔河
※歌尼斯堡七桥难题 普莱格尔河
七桥问题的数学模型: 用A、B表示两座小岛,C、D表示两岸, 连线AB表示A、B之间有一座桥。 C A B 问题简化为: 在该图中,从任一点出发,能否通过每条线段 次且仅仅一次后又回到原来的出发点 结论:不存在这样一种走法
结论：不存在这样一种走法。 用A、B表示两座小岛，C、D表示两岸， 连线AB表示A、B之间有一座桥。 问题简化为： A • • B • C • D 在该图中，从任一点出发，能否通过每条线段 一次且仅仅一次后又回到原来的出发点 七桥问题的数学模型：
类似的问题:一笔画问题 图的一笔画:可一笔画 不可一笔画 凶 字的一笔画:如“中、日、口、串”等可一笔画 而:“田、目”等不能一笔画
类似的问题：一笔画问题 字的一笔画：如“中、日、口、串”等可一笔画 而：“田、目”等不能一笔画 图的一笔画： 可一笔画 不可一笔画
图论的应用范围: 1、中国邮路问题: 邮递员如何选择适当的投递路线,使每条街道至 少走过一次且所走的总路程最短 2、最短路问题: 个乡有9个自然村,其间道路如下图所示, 要以村为中心ν建有线广播网,如要求沿道路 架设广播线,应如何架设使所用电线最短
图论的应用范围： 1、中国邮路问题： 邮递员如何选择适当的投递路线，使每条街道至 少走过一次且所走的总路程最短？ 2、最短路问题： 一个乡有9个自然村，其间道路如下图所示， 要以村为中心 建有线广播网，如要求沿道路 架设广播线，应如何架设使所用电线最短 0 v • • • • • • • • • 0 v 4 1 1 5 2 4 4 3 1 2 3 5 5 1 4 2 1 • • • • • • • • • 0 v 1 2 1 2 3 1 2