《运筹学》课程PPT教学课件（Operations Research）第六章 图论（6.0）绪言

运筹学 Operations Research §6.0图论绪言 山东运筹,两论起家.一为规划论,一为图论 管梅谷( Kuan mei Ko) 图论的起源:哥尼斯堡( Konigsberg)七桥问题 18世纪30年代,流经东普鲁士小城哥尼斯堡的 Pregel河中有 两个小岛,小岛与两岸有七座桥相连.当地居民热衷于讨论 如下问题:一个散步者能否从某处出发,依次走过每座桥恰 好一次,再回到原出发处? 2021/2/20 D

2021/2/20 1 运 筹 学 Operations Research §6.0 图论绪言 山东运筹，两论起家.一为规划论，一为图论. —— 管梅谷（Kuan Mei Ko） 图论的起源：哥尼斯堡（Konigsberg）七桥问题 18世纪30年代，流经东普鲁士小城哥尼斯堡的Pregel河中有 两个小岛，小岛与两岸有七座桥相连.当地居民热衷于讨论 如下问题：一个散步者能否从某处出发，依次走过每座桥恰 好一次，再回到原出发处？

运筹学 Operations Research 1736年,瑞士数学家欧拉( Leonhard euler,1707-1783) 研究了此问题并将其归结为一个“一笔画”问题: A B D G 为此,欧拉曾撰文《 Solutio problematis ad geometrian Situs Pertinentis》(依据几何位置的解题 方法),是为历史上的第一篇图论论文.欧拉因之而成为 图论的创始人 2021/2/20 2

2021/2/20 2 运 筹 学 Operations Research 1736年，瑞士数学家欧拉（Leonhard Euler，1707-1783） 研究了此问题并将其归结为一个“一笔画”问题： 为此，欧拉曾撰文《Solutio Problematis ad geometrian Situs Pertinentis》（依据几何位置的解题 方法），是为历史上的第一篇图论论文.欧拉因之而成为 图论的创始人

运筹学 Operations Research 主要内容: 0.基本概念 1.树(tree),森林( forest) 2CPP和TSP 3.染色( coloring) 4.平面图( planar graph) 5.匹配( matching) 6.网络流( network flow)问题:最短路问题,最大流问 题 7.其它( otherwise) 2021/2/20 3

2021/2/20 3 运 筹 学 Operations Research 主要内容： 0.基本概念 1.树（tree），森林（forest） 2 CPP和TSP 3.染色（coloring） 4.平面图（planar graph） 5.匹配（matching） 6.网络流（network flow）问题：最短路问题，最大流问 题 7.其它（otherwise）

运筹学 Operations Research $6.0 over 2021/2/20 4

2021/2/20 4 运 筹 学 Operations Research §6.0 over