任韩，华东师范大学教授，博士生导师，研究方向：拓扑图论与组合数学理论。1999年10月毕业于北京交通大学数学系，获运筹学与控制论专业博士学位，从事图论与组合数学理论研究，先后在 外各类学术刊物上发表专业论文50余篇（其中大多数是以 作者身份完成），包括发表在 上具有影响力的专业学术刊物的（SCI与EI检索）论文数十篇；主持并完成 自然科学基金两项，并作为主要人员参与两项上海市自然科学基金项目。受聘于上海多所名校，任奥数教师，主要讲授图论。 ???????????????
本书是“数学奥林匹克命题人讲座”（升级版）中的一本，主要讲述图论的内容。各章节从高考难题、全国联赛一试试题的难度入手，充分考虑了参加数学竞赛的高中学生的实际需要。升级版书稿保留了 版中具有典型性的问题，在此基础上删减了部分老题目，并将近年来的高校自招、全国联赛、冬令营、IMO、中国女子数学奥林匹克、中国西部数学邀请赛及国外的数学竞赛中的新题好题充实进来，既有一定的新鲜度，又充分考虑到合理性。 ???????????????
讲 ?图的基本概念／1第二讲 ?图的连通性／192.1 ?图的连通性、点割集、边割集／ 202.2 ?关于图的连通性的一些基本结果／222.3 ?连通图的结构问题／28第三讲 ?组合理论中的树结构／313.1 ?树的定义、基本性质／ 313.2 ?图中的树与反圈之间的关系／333.3 ??小支撑树问题／353.4 ?与树有关的几个重要算法／373.5 ?边不交支撑树问题／463.6 ?树在代数结构方面的应用／50第四讲 ?图的子图问题／54第五讲 ?对集问题／785.1 ?一般图中的对集问题／785.2 ?二部图中的对集问题／85第六讲 ?图中的遍历性问题／946.1 ?欧拉图问题／946.2 ?中国邮递员问题／1056.3 ?哈密顿问题／108第七讲 ?拉姆齐问题／1217.1 ?2_维拉姆齐数／1217.2 ?广义拉姆齐数及其应用／1307.3 ?单色子图问题／141第八讲 ?图的染色问题／1508.1 ?图的两种染色概念／1508.2 ?图的节点染色／1528.3 ?图的边染色／1668.4 ?图的色多项式／1738.5 ?其他染色问题／175第九讲 ?平面图与多面体问题／1779.1 ?平面图与图的平面嵌入／1779.2 ?平面嵌入图的染色问题／1869.3 ?与平面图有关的图论问题／193第十讲 ?有向图／205第十一讲 ?有限集合上的组合数学问题／21911.1 ?偏序集上的组合问题／21911.2 ?施佩纳定理／22611.3 ?集合的相交族问题／23211.4 ?有限集合系统的霍尔定理／23811.5 ?共同代表系理论／24211.6 ?霍尔定理的其他形式／245第十二讲 线性代数方法与组合结构／25312.1 ?3_连通图的圈空间／25312.2 ?连通图的结构与图的子空间／25512.3 ?特征值方法的使用／25812.4 ?图的矩阵理论／26112.5 ?代数结构与集合的相交族问题——维数组合学／27112.6 ?多项式空间理论在组合几何中的应用／276第十三讲 组合数学中的概率论方法／27813. 1 ?概率方法的背景和出发点／27813.2 ?随机图／28113.3 ?数学期望方法／28313.4 ?洛瓦斯的局部引理／29513.5 ?相互独立性原理／29813.6 ?洛瓦斯局部引理的一般形式／301第十四讲 ?覆盖与划分问题／30714.1 ?相交凸集问题／30714.2 ?贪婪划分问题／30914.3 ?边不交支撑树问题／31314.4 一些典型问题／321第十五讲 ?有限群与组合结构／33315.1 ?伯恩赛德引理／33315.2 ?波利亚计数定理／34215.3 ?赋权形式的伯恩赛德引理／35115.4 ?关于圆形排列问题的讨论／353参考答案及提示／360
