历史上运筹学的运用 ◆我国:战国时代 齐王与田忌赛互 国外:1736年欧拉解决 哥尼斯堡七桥问题
6 历史上运筹学的运用 我国：战国时代 齐王与田忌赛马 国外：1736年欧拉解决 哥尼斯堡七桥问题
哥尼斯堡七桥问题 濒临蓝色的波罗的海,有一座古老而美丽的城市, 叫做哥尼斯堡(今俄罗斯加里宁格勒)。布勒格尔河 的两条支流在这里汇合,然后横贯全城,流入大海。 河心有一个小岛。河水把城市分成了4块,于是,人 Y们建造了7座各具特色的桥,把哥尼斯堡连成一体。 天又一天,7座桥上走过了无数的行人。不知从什 么时候起,脚下的桥梁触发了人们的灵感,一个有趣 的问题在居民中传开了:谁能够一次走遍所有的7座 桥,而且每座桥都只通过一次?这个问题似乎不难, 谁都乐意用它来测试一下自己的智力。可是,谁也没 有找到一条这样的路线。连以博学著称的大学教授们, 也感到一筹莫展。“七桥问题”难住了哥尼斯堡的所 有居民。哥尼斯堡也因“七桥问题”而出了名
7 哥尼斯堡七桥问题 濒临蓝色的波罗的海，有一座古老而美丽的城市， 叫做哥尼斯堡（今俄罗斯加里宁格勒）。 布勒格尔河 的两条支流在这里汇合，然后横贯全城，流入大海。 河心有一个小岛。河水把城市分成了４块，于是，人 们建造了７座各具特色的桥，把哥尼斯堡连成一体。 一天又一天，７座桥上走过了无数的行人。不知从什 么时候起，脚下的桥梁触发了人们的灵感，一个有趣 的问题在居民中传开了： 谁能够一次走遍所有的７座 桥，而且每座桥都只通过一次？ 这个问题似乎不难， 谁都乐意用它来测试一下自己的智力。可是，谁也没 有找到一条这样的路线。连以博学著称的大学教授们， 也感到一筹莫展。“七桥问题”难住了哥尼斯堡的所 有居民。哥尼斯堡也因“七桥问题”而出了名
七桥问题的形象描述 城市分割成4个区域: 河的两岸(A和B),河 中的岛(C)和两条支流 之间的半岛(D)。七座 桥横跨普勒格尔河及其支 流,把河岸、半岛和河 e岛连接起来
8 七桥问题的形象描述 城市分割成4个区域： 河的两岸（A和B），河 中的岛（C）和两条支流 之间的半岛（D）。七座 桥横跨普勒格尔河及其支 流，把河岸、半岛和河心 岛连接起来
欧拉的解题思路 当时的大数学家欧拉没有亲自去哥尼 斯堡测试可能的路线。事实上,如果 沿着所有可能的路线都走一次的话, 共要走5040次。就算是一天走一次,也 需要13年多的时间,而实际上.欧拉只 用了几天的时间就解决了七桥问题
9 欧拉的解题思路 当时的大数学家欧拉没有亲自去哥尼 斯堡 测试可能的路线 。事实上，如果 沿着所有可能的路线都走一次的话，一 共要走5040次。就算是一天走一次，也 需要13年多的时间，而实际上．欧拉只 用了几天的时间就解决了七桥问题
欧拉的解题思路 1、建立模型: 首先把哥尼斯堡的4个 区域分别用点A、B、C、DQ 表示,每座连接两个区域的 桥用相应两点的连线a、b c、d、e、f、g表示,即把哥 尼斯堡七桥的情景转化为 个图
10 欧拉的解题思路 1、建立模型： 首先把哥尼斯堡的4个 区域分别用点A、B、C、D 表示，每座连接两个区域的 桥用相应两点的连线a、b、 c、d、e、f、g表示，即把哥 尼斯堡七桥的情景转化为一 个图