《运筹学》课程教学资源（讲义）第二章 图论绪言

运筹学讲义 §2.0图论绪言 千言万语不及一张图( Thousands of words are infer ior to a graph) F· Herbart 山东运筹,两论起家.一为规划论,一为图论 管梅谷( Kuan Mei Ko) 图论( graph theory)是一个年青而活跃的运筹学分支,是网络( network)技术的理论基础 图论的起源:哥尼斯堡( KOnigsberg)七桥问题 L8世纪30年代,流经东普鲁士( Prussia)王国小城哥尼斯堡(现为俄罗斯加里宁格勒,在波罗 的海上,被波兰和立陶宛包围,与俄罗斯本土不接壤)的一条河流ˉ普雷格尔河( Pregel)中有两个 小岛,小岛与两岸有七座桥相连当地居民热衷于讨论如下问题:一个散步者能否从某处出发,依次 走过每座桥恰好一次,再回到原出发处?如下图示 1736年,瑞士数学家欧拉( Leonhard euler,1707-1783)研究了此问题并将其归结为一个“一笔 画”问题:将两个小岛和两岸分别用顶点A,B,C,D表示,顶点之间有边相连当且仅当岛、岸之间有 桥,得到一个图( graph)G A B D

运 筹 学 讲 义 1 §2.0 图论绪言 千言万语不及一张图（Thousands of words are inferior to a graph）. —— F·Herbart 山东运筹，两论起家.一为规划论，一为图论. —— 管梅谷（Kuan Mei Ko） 图论（graph theory）是一个年青而活跃的运筹学分支，是网络（network）技术的理论基础. 图论的起源：哥尼斯堡（K o  nigsberg）七桥问题 18 世纪 30 年代，流经东普鲁士（Prussia）王国小城哥尼斯堡（现为俄罗斯加里宁格勒，在波罗 的海上，被波兰和立陶宛包围，与俄罗斯本土不接壤）的一条河流－普雷格尔河（Pregel）中有两个 小岛，小岛与两岸有七座桥相连.当地居民热衷于讨论如下问题：一个散步者能否从某处出发，依次 走过每座桥恰好一次，再回到原出发处？如下图示. 1736 年，瑞士数学家欧拉（Leonhard Euler，1707-1783）研究了此问题并将其归结为一个“一笔 画”问题：将两个小岛和两岸分别用顶点 A, B,C, D 表示，顶点之间有边相连当且仅当岛、岸之间有 桥，得到一个图（graph） G

运筹学讲义 于是,哥尼斯堡七桥问题◇图G能“一笔画”吗?◇图G含有一条欧拉环游吗?◇图G是 欧拉图吗?为此,欧拉曾撰文《 Solutio Problematis ad geometrian Situs Pertinentis》(依据几何位置的解 题方法)( Comment. Academiae Sci.. Pertropolitanae,8,128-140),阐述了判定欧拉图的充分必要 条件,并据此判明图G是非欧拉图,即这样的散步路线不存在,是为历史上的第一篇图论论文.欧拉 因之而成为图论的创始人,被称为“图论之父”( father of graph theory) 欧拉一生曾发表886篇论文,出版近90本著作,其中很多是在双目失明的生命的最后20年完成 的 注: pertinent a.相关的 图论的主要内容 0.基本概念 握手问题:某次聚会,熟人互相握手,握手次数为奇数的人恰有偶数个 树(tree),森林( forest) 家谱( family tree) 2图的连通性( connectivity) 3.CPP和TSP 迷宫问题 4.染色( coloring) 四色问题 5.平面图( planar graph) 电路板的印刷问题,地图和地球仪的绘制问题 6.匹配( matching) 婚姻问题,排课表问题 7.独立集( independent set)和团( clique) 相识问题:任意6个人中,必有3个人或互相认识,或互相不认识 8.有向图( digraph) 9.网络( network) 最短路问题(船夫过河问题),最大流问题 10.其它( otherwise) 参考数目 1 Graph Theory with Applications, J. A. Bondy, U.S. R. Murty, the Macmill an Press Ltd.,1976 2《运筹学》.运筹学教材编写组.清华大学出版社.2002 3《运筹学通论》.魏权龄,胡显佑,严颖.中国人民大学出版社.2001 4《实用运筹学》.魏国华,傅家良,周仲良.高等教育出版社.1990

运 筹 学 讲 义 2 于是，哥尼斯堡七桥问题  图 G 能“一笔画”吗？  图 G 含有一条欧拉环游吗？  图 G 是 欧拉图吗？为此，欧拉曾撰文《Solutio Problematis ad geometrian Situs Pertinentis》（依据几何位置的解 题方法）(Comment. Academiae Sci. I. Pertropolitanae，8，128-140)，阐述了判定欧拉图的充分必要 条件，并据此判明图 G 是非欧拉图，即这样的散步路线不存在，是为历史上的第一篇图论论文.欧拉 因之而成为图论的创始人，被称为“图论之父”（father of graph theory）. 欧拉一生曾发表 886 篇论文，出版近 90 本著作，其中很多是在双目失明的生命的最后 20 年完成 的. 注：pertinent a.相关的. 图论的主要内容： 0.基本概念 握手问题：某次聚会，熟人互相握手，握手次数为奇数的人恰有偶数个. 1.树（tree），森林（forest） 家谱（family tree） 2 图的连通性（connectivity） 3.CPP 和 TSP 迷宫问题 4.染色（coloring） 四色问题 5.平面图（planar graph） 电路板的印刷问题，地图和地球仪的绘制问题 6.匹配（matching） 婚姻问题，排课表问题 7.独立集（independent set）和团（clique） 相识问题：任意 6 个人中，必有 3 个人或互相认识，或互相不认识. 8.有向图（digraph） 9.网络（network） 最短路问题（船夫过河问题），最大流问题 10.其它（otherwise） 参考数目： 1 Graph Theory with Applications， J. A. Bondy， U. S. R. Murty, the Macm ill an Pre s s , Ltd., 1976. 2《运筹学》.运筹学教材编写组.清华大学出版社.2002. 3《运筹学通论》.魏权龄，胡显佑，严颖.中国人民大学出版社.2001. 4《实用运筹学》.魏国华，傅家良，周仲良.高等教育出版社.1990