英国南安普顿大学研究生图论课程概述

图论是数学的一个独立分支，与整个数学领域都有联系，从抽象代数和拓扑学等纯数学部分，到运筹学和计算等应用数学部分，再到化学、生物学和电子学等其他科学领域。英国南安普顿大学研究生图论课程介绍了图论的基本概念，主要关注有限图。课程内容涉及图的数值不变量和计算它们的方法；如何浏览图；图的点和边着色以及图的其他数值不变量；图是平面的条件；以及随机图理论的基础知识。课程概述如下。

一、内容摘要

1、图的基本数值的定义，包括直径和半径、最小和最大度、围长和周长、色数和色指数、团数和独立数；除此之外，还可以包括其他不变量。

2、欧拉图，以及图是欧拉图的充要条件。

3、哈密尔顿图，以及图是哈密尔顿图的充分条件，包括Ore定理。

4、树，包括普鲁弗序列和完全图的生成树数的凯莱定理。

5、平面图形，包括欧拉公式的陈述、证明和应用；库拉托夫斯基定理的陈述(但不是证明)。

6、图的顶点着色，包括产生顶点着色的贪婪算法和Brooks定理的陈述。

7、平面图的顶点着色，包括五色定理的陈述和证明，以及四色定理的陈述。

8、图的边着色，包括二部图的边着色，以及Vizing定理和Koenig定理的陈述。

9、随机图的基本定义和性质；关于大围长和大色数图存在性的Erdos定理。

二、学习目标

1、陈述和应用教学大纲中描述的图形性质的定义和基本结果，并确定这些性质是否适用于特定的图的例子和类别，以及图的构造。

2、陈述教学大纲中描述的与图形相关的数值不变量的定义，在证明中使用这些定义，并且计算特定例子和图类以及图构造的这些不变量。

同学可以根据上述内容摘要来规划学习安排，无论是课前预习还是课后复习，都有助于达成学习目标，从而在南安普顿大学图论课程评估中取得好成绩。