1958年6-7月号美国《数学月刊》上登载了这 样一个有趣的问题：“任何6个人的聚会，其中总 会有3个人互相认识或3个人互不认识．”这就是 著名的Ramsey问题。
问题描述： 任给一个人群，要么该人群中有k个人互相认 识，要么有l个人互相不认识，问满足这种要求的 人群至少有多少人？用r(k,l)表示该然群中的人数。
经典问题
许多图论问题都是从智力难题和游戏中提 炼出来的，有些问题在本质上是初等的，但其 中也有大量的问题可以难倒最老练的数学家。 图论问题的解决需要巧妙的方法，没有可循的 程式，问题外表的简单朴素和本质上的难以解 决，使每个从事图论研究的人在图论问题面前 都必须谨慎、严肃、深入地思考。因而学习图 论可以锻炼思维，借助图论的思维方法可以提 高解决问题的能力 。
b(n) (n 1)[b(n 1) b(n 2)],
n3
经计算，知
b(10) 1334961
指派问题：也称人员分配问题
问能否给每人恰好分配一项工作，且每项 工作至多分配给一名胜任该项工作的人员？
基本定理
可增广轨
问题拓展
谢 谢！
2012.6.5
Euler 问题
Hamilton问题
十二面体 二十个城市
货郎担问题（TSP）
Hamilton问题派生的价值连城的问题 一个货郎担了百货到各村去卖货，为他设计一个售 货路线，使他耗时最少？
例如 20个城市 穷举法——
1 20! 2
按每秒千万次的运算的计算机，需百年以上。
Ramsey问题
条边，这样得到了一个n阶简单图G。上述飞行员 搭配问ห้องสมุดไป่ตู้就相当于求G的最大匹配。
最小覆盖
在主要街道的交叉路口安装监控摄像头，要 使所有街道都在监控之下，问至少需要安装多少 个摄像头？
二、图论方法
Bernoulli-Euler错插信笺问题
给n位同学各写好一封信的信笺，又写好了给 这n位同学的信封，问有多少种可能把信笺都插错 了信封？ 用 b(n) 表示所求的答数，显然有 b(1) 0 ， b(2) 1 。
Graph Method and Its Application
图论方法及其应用
田双亮
一、背景
图论中的图指的是一些点以及连接这些点的线 的总体。通常用点代表事物，用连接两点的线代 表事物间的关系，图论则是研究事物对象在上述 表示法中具有的特征与性质的学科 。
图论是研究图的拓扑结构的学科。
图例
现实中的问题
最大独立集 假设在某种信号传输中，基本信号集为 B {v1 , v2 , , v m } 。巳知线路失真和其他异常 情况会导致有些信号发生错乱。聪明的做法 是不用整个基本信号集B，而是从B中选择具 有某种特性的一个最大子集。 例如 B {v1 , v2 , v3 , v4 , v5 , v6 }
最大匹配 第二次世界大战时，英国某飞行大队由来 自世界各地的 n 名飞行员组成，飞行大队的每 架飞机必须由两名飞行员驾驶．但由于语言和 训练方式等诸种原因，某些飞行员适合同机飞 行，另一些飞行员则不能同机飞行。问应怎样 搭配飞行员，才能使尽可能多的飞机同时飞行?
每个飞行员用一个顶点表示，当且仅当两个 飞行员适合同机飞行时，在相应的顶点间连一