图论-数学奥林匹克命题人讲座 目录

**讲 图的基本概念／1第二讲 图的连通性／23§2.1 图的连通性、点割集、边割集／24§2.2 关于图的连通性的一些基本结果／26§2.3 连通图的结构问题／33第三讲 组合理论中的树结构／36§3.1 树的定义、基本性质／37§3.2 图中的树与反圈之间的关系／38§3.3 *小支撑树问题／40§3.4 与树有关的几个重要算法／42§3.5 边不交支撑树问题／52§3.6 树在代数结构方面的应用／56第四讲 图的子图问题／61第五讲 对集问题／84§5.1 一般图中的对集问题／84§5.2 二部图中的对集问题／92第六讲 图中的遍历性问题／107§6.1 欧拉图问题／108§6.2 中国邮递员问题／120§6.3 哈密顿问题／124第七讲 拉姆齐问题／139§7.1 一维拉姆齐数／139§7.2 广义拉姆齐数及其应用／149§7.3 单色子图问题／164第八讲 图的染色问题／175§8.1 图的两种染色概念／175§8.2 图的节点染色／177§8.3 图的边染色／193§8.4 图的色多项式／201§8.5 群论方法／204§8.6 其他染色问题／213第九讲 平面图与多面体问题／215§9.1 平面图与图的平面嵌入／215§9.2 平面嵌入图的染色问题／225§9.3 与平面图有关的图论问题／233第十讲 有向图／247参考答案及提示／263

图论-数学奥林匹克命题人讲座 节选

《图论》主要阐述网络*优化问题中运用的一些重要的图论方法和用图论方法解决的实际问题，如*小连接问题、*优线路问题、工作分派问题、网络流问题，以及图的染色和标号在实际中的应用等。书中附有大量的例子说明图论在自然科学和社会科学中的应用。对于图论中的某些重要结论和著名定理，《图论》给出了简要而精彩的证明，使得读者能够体会到图论方法的精妙之处。同时，我们也提出一些没有解决的问题。

图论-数学奥林匹克命题人讲座 作者简介

任韩，华东师范大学教授，博士生导师，研究方向：拓扑图论与组合数学理论、1999年10月毕业于北京交通大学数学系，获运筹学与控制论专业博士学位．从事图论与组合数学理论研究，先后在国内外各类学术刊物上发表专业论文50余篇（其中大多数是以第一作者身份完成）。包括发表在具有国际影响力的专业学术刊物（SCI与EI检索）上的论文数十篇；主持并完成国家自然科学基金项目两项，并作为主要人员参与两项上海市自然科学基金项目。受聘于上海多所名校担任奥数教师，主要讲授图论和组合数学。

自然科学 数学 代数数论组合理论

在线阅读