北京交通大学经济管理学院SchoollofEicsandManagomentBoijingJiaotong University图论是应用十分广泛的运筹学分支它已经广泛地应用在物理学、化学、控制论、信息论、经营管理、电子计算机等各个领域。北京交通大学
图论是应用十分广泛的运筹学分支, 它已经广泛地应用在物理学、化学、 控制论、信息论、经营管理、电子计 算机等各个领域
北京交通大学经济管理学院哥尼斯堡七桥问题SchoolIofEconnics andManagomentBoijingJiaotongUniversityB问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点题:能否从某一点开始一笔画出这个图形,最后回到原点.而不重复北京交通大学
哥尼斯堡七桥问题 问题:一个散步者能否从任一块陆地出发, 走过 七座桥, 且每座桥只走过一次, 最后回到出发 点? B A C D 问题:能否从某一点开始一笔画出这个图形, 最后回 到原点,而不重复
BB1736年，欧拉将这个问题抽象成一笔画问题，即能否从某一点开始不重复地一笔画出这个图形，最终回到原点欧拉在他的论文中证明了这是不可能的，这就是古典图论中的第一个著名问题为什么？怎样判断任意一个图形能否一笔画出？北京交通大学
1736年,欧拉将这个问题抽象成一笔画问题,即能否从某 一点开始不重复地一笔画出这个图形,最终回到原点. 欧拉在他的论文中证明了这是不可能的,这就是古典图 论中的第一个著名问题. 为什么?怎样判断任意一个图形能否一笔画出? B A C D A B C D
北京交通大学例：中国邮路问题经济管理学院SchoollofEoicsandMarsagementBoijing Jiaotong University一个邮递员送信，要走完他所负责的全部街道分送信件，最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。问题：他如何走？点：路口;边：两路口之间道路，第道路长e;。问题：求一个圈，过每边至少一次，并使圈的长度最短.北京交通大学
例：中国邮路问题 一个邮递员送信，要走完他所负责的全部街道分送 信件，最后返回邮局。邮递员都会本能地以尽可能少的 行程完成送信任务。 问题：他如何走？ 点：路口； 边：两路口之间道路，第i条道路长ei。 问题：求一个圈, 过每边至少一次, 并使圈的长度最 短
北京交通大学例：四色猜想经济管理学院SchoollofEoics and ManagomentBoijingJiaotongUniversity能否用四种颜色给地图染色，使相邻的国家有不同的颜色。点：国家;边：两个国家有公共边界。问题：能否用四种颜色给平面图的点染色，使有公共边的点有不同的颜色。北京交通大学
例：四色猜想 能否用四种颜色给地图染色，使相邻的国家有不 同的颜色。 点：国家； 边：两个国家有公共边界。 问题：能否用四种颜色给平面图的点染色，使有公共 边的点有不同的颜色