《图论导论》前言与导论

书籍内容分布

该书一共可分为四个部分：

• 第1-3章：基础知识，包括图、有向图、连通性、欧拉和哈密顿路径、循环、树
• 第4-5章：平面和着色，重点介绍四色定理
• 第6章：横向理论和连通性
• 第7章：拟阵

图(graph)的介绍

图的要素

• 节点(verticle)，边(edge)，度(degree)
• 环(loop)，重边(multiple edges)
• 游走(walk)，路径(path)，循环(cycle)
• 连通(connected)，非连通(disconnected)

图的变式与性质

图的变式

• 简单图(simple graph)：无重边和环的图
• 树(tree)：简单无循环图
• 平面图(planar graph)：不同边可互不交叠的图

图的性质

• 欧拉路径(Eulerian)：即一笔画，不重复过节点地走完全部边
• 哈密顿路径(Hamiltonian)：过所有节点的循环
• 四色原理(four-color theorrm)：对简单图，只用四种颜色便可保证邻节点异色
• 横向理论(transversal theory)与稳定婚姻问题(marriage problem)