运筹学讲义 于是,哥尼斯堡七桥问题◇图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