|
《代数图论》教学大纲
(
2003
年08月25日---
2004年01月09日)
本课程大纲以《Algebraic Graph Theory》（C.Godsi,
G.Royle）第1－8章为依据（作者给出了一些勘误，见Errata）。按学校教学日历表安排，本课程从第二周开始。本课程为博士生必修和硕士生选修课程。讲授以讨论班形式。后4章由博士生主讲，旨在提高学习效果，培养研究生的课堂讲授和语言表达等综合能力。以下是个大致安排，根据内容和进度可能会做些适当调整。
第1章：图的基本概念（由徐俊明主讲）。用2个单元时间（第2周五到第3周三）。主要是本课程用到图的基本概念，图的同构和同态概念。4类特殊的图：循环图，Johnson图，线图和平面图。
第2章：群的基本概念（由徐俊明主讲）。用3个单元时间（第3周五，第4周）。内容是：置换群，计数，反对称图，轨道和稳定子群，群的本原性，本原性与连通性。
第3章：可迁图（由徐俊明主讲）。用3个单元时间（第5周和第6周）。1.点可迁和边可迁图，可迁图的边连通度和点连通度（因为这部分内容已经比较熟悉，可在一个单元时间内完成）。2.可迁图的匹配和圈长。3.
Cayley图的Hamilton性，收缩核和对换。
第4章：弧可迁图（由徐俊明主讲）。用2个单元时间（第7周）。1.
弧可迁概念和弧可迁图，弄清与点、边可迁的区别和联系，两个特殊的图（3次弧可迁图和Petersen图）。2.
距离可迁图（两个特殊图:Coxeter图和Tutte 8－Cage可以不讲，自习之）。
第5章：广义多边形和Moore图（由杜正中主讲，周敏杰辅之）。用4个单元时间（第8周到第9周）。1.关联图的概念，射影平面。2.广义4边形。3.广义多边形（5.7节可以不讲，自习之）。4.
Moore图和设计。
第6章：同态（由朱
强和马美杰主讲，经紟辅之）。用5个单元时间（第10周到第12周三）。1.图同态概念，存在性的两个必要条件，柱心（Core）的概念和基本结果，图乘积和基本性质。2.映射图和乘积图的关系，图同态的计数，乘积图的染色以及唯一可染色图。3.Folding
and Covers, Cores with no triangles。 4. Andrasfai图及其染色和特征。5.点可迁图的柱心。
第7章：Kneser图（由吕
敏和田方主讲，孙犁辅之）。用5个单元时间（第12周五到第14周）。1.分式(fractional)染色和分式点团的概念以及分式色数。2.同态与分式染色，对偶性。3.非完备图，循环区间图和Erdos-Ko-Rado定理。4.Kneser图的同态，导出同态和色数。5.Gale和Welzl定理，笛卡尔乘积和强乘积。
第8章：矩阵论（由徐
敏和潘向峰主讲，王彦辉辅之）。用4个单元时间（第15周到第16周）。1.邻接矩阵，关联矩阵和对称矩阵；2.特征向量，半正定矩阵，次调和函数；3.对称阵的秩，邻接矩阵的2元秩；4.辛图，普分解和有理函数。
|
