|
《代数图论》教学大纲
(
2008
年02月24日---
2008年07月12日)
本课程大纲以《Algebraic Graph Theory》（C.Godsi,
G.Royle）第1－7章为依据（作者给出了一些勘误，见Errata）。以下是个大致安排，根据内容和进度可能会做些适当调整。
第1章：图的基本概念。用2个单元时间。主要是本课程用到图的基本概念，图的同构和同态概念。4类特殊的图：循环图，Johnson图，线图和平面图。
第2章：群的基本概念。用3个单元时间。内容是：置换群，计数，反对称图，轨道和稳定子群，群的本原性，本原性与连通性。
第3章：可迁图。用3个单元时间。1.点可迁和边可迁图，可迁图的边连通度和点连通度（因为这部分内容已经比较熟悉，可在一个单元时间内完成）。2.可迁图的匹配和圈长。3.
Cayley图的Hamilton性，收缩核和对换。
第4章：弧可迁图。用2个单元时间。1.
弧可迁概念和弧可迁图，弄清与点、边可迁的区别和联系，两个特殊的图（3次弧可迁图和Petersen图）。2.
距离可迁图（两个特殊图:Coxeter图和Tutte 8－Cage可以不讲，自习之）。
第5章：广义多边形和Moore图。用4个单元时间。1.关联图的概念，射影平面。2.广义4边形。3.广义多边形（5.7节可以不讲，自习之）。4.
Moore图和设计。
第6章：同态。用5个单元时间。1.图同态概念，存在性的两个必要条件，柱心（Core）的概念和基本结果，图乘积和基本性质。2.映射图和乘积图的关系，图同态的计数，乘积图的染色以及唯一可染色图。3.Folding
and Covers, Cores with no triangles。 4. Andrasfai图及其染色和特征。5.点可迁图的柱心。
第7章：Kneser图。用5个单元时间。1.分式(fractional)染色和分式点团的概念以及分式色数。2.同态与分式染色，对偶性。3.非完备图，循环区间图和Erdos-Ko-Rado定理。4.Kneser图的同态，导出同态和色数。5.Gale和Welzl定理，笛卡尔乘积和强乘积。
|
