§2.0 图论绪言
千言万语不及一张图（Thousands of words are inferior to a graph）.
—— F·Herbart
山东运筹，两论起家.一为规划论，一为图论.
—— 管梅谷（Kuan Mei Ko）
图论（graph theory）是一个年青而活跃的运筹学分支，是网络（network）技术的理论基础.
图论的起源：哥尼斯堡（Knigsberg）七桥问题
18世纪30年代，流经东普鲁士（Prussia）王国小城哥尼斯堡（现为俄罗斯加里宁格勒，在波罗的海上，被波兰和立陶宛包围，与俄罗斯本土不接壤）的一条河流－普雷格尔河（Pregel）中有两个小岛，小岛与两岸有七座桥相连.当地居民热衷于讨论如下问题：一个散步者能否从某处出发，依次走过每座桥恰好一次，再回到原出发处？如下图示.
1736年，瑞士数学家欧拉（Leonhard Euler，1707-1783）研究了此问题并将其归结为一个“一笔画”问题：将两个小岛和两岸分别用顶点表示，顶点之间有边相连当且仅当岛、岸之间有桥，得到一个图（graph）.
于是，哥尼斯堡七桥问题图能“一笔画”吗？图含有一条欧拉环游吗？图是欧拉图吗？为此，欧拉曾撰文《Solutio Problematis ad geometrian Situs Pertinentis》（依据几何位置的解题方法）(Comment,Academiae Sci,I,Pertropolitanae，8，128-140)，阐述了判定欧拉图的充分必要条件，并据此判明图是非欧拉图，即这样的散步路线不存在，是为历史上的第一篇图论论文.欧拉因之而成为图论的创始人，被称为“图论之父”（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 Macmillan Press,Ltd.,1976.
2《运筹学》.运筹学教材编写组.清华大学出版社.2002.
3《运筹学通论》.魏权龄，胡显佑，严颖.中国人民大学出版社.2001.
4《实用运筹学》.魏国华，傅家良，周仲良.高等教育出版社.1990.
千言万语不及一张图（Thousands of words are inferior to a graph）.
—— F·Herbart
山东运筹，两论起家.一为规划论，一为图论.
—— 管梅谷（Kuan Mei Ko）
图论（graph theory）是一个年青而活跃的运筹学分支，是网络（network）技术的理论基础.
图论的起源：哥尼斯堡（Knigsberg）七桥问题
18世纪30年代，流经东普鲁士（Prussia）王国小城哥尼斯堡（现为俄罗斯加里宁格勒，在波罗的海上，被波兰和立陶宛包围，与俄罗斯本土不接壤）的一条河流－普雷格尔河（Pregel）中有两个小岛，小岛与两岸有七座桥相连.当地居民热衷于讨论如下问题：一个散步者能否从某处出发，依次走过每座桥恰好一次，再回到原出发处？如下图示.
1736年，瑞士数学家欧拉（Leonhard Euler，1707-1783）研究了此问题并将其归结为一个“一笔画”问题：将两个小岛和两岸分别用顶点表示，顶点之间有边相连当且仅当岛、岸之间有桥，得到一个图（graph）.
于是，哥尼斯堡七桥问题图能“一笔画”吗？图含有一条欧拉环游吗？图是欧拉图吗？为此，欧拉曾撰文《Solutio Problematis ad geometrian Situs Pertinentis》（依据几何位置的解题方法）(Comment,Academiae Sci,I,Pertropolitanae，8，128-140)，阐述了判定欧拉图的充分必要条件，并据此判明图是非欧拉图，即这样的散步路线不存在，是为历史上的第一篇图论论文.欧拉因之而成为图论的创始人，被称为“图论之父”（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 Macmillan Press,Ltd.,1976.
2《运筹学》.运筹学教材编写组.清华大学出版社.2002.
3《运筹学通论》.魏权龄，胡显佑，严颖.中国人民大学出版社.2001.
4《实用运筹学》.魏国华，傅家良，周仲良.高等教育出版社.1990.
