关于路染色问题和Cerny猜想

摘要

该文的工作,主要有两点:第一,对路染色猜想和Cerny猜想做了一个综述,其中包括了数十年来的经典结论,和最近的一些新的进展.在路染色问题和Cerny猜想这两个问题上,世界各地的学者取得了许多各种各样的结论,而且所使用的描述语言各不相同,主要有基于纯粹图论的,和基于自动机理论的,以及在符号动力的基础上进行研究的.因此将这些结果用统一的描述方法进行归纳的工作,还是很有必要的,也是很有意义的.第二,在路染色猜想方面做出了一些自己的工作,将已有的一些结论进行了推广,得到了更为一般化的结论.

目录

文摘

英文文摘

声明及授权书

引言

第一章基本概念

1.1路染色猜想

1.2Cerny猜想

1.3一些约定

第二章一些已知结果

§2.1路染色猜想

2.1.1素环

2.1.2单环分解

2.1.3权重

2.1.4有向欧拉图

2.1.5路染色猜想的一些等价命题

2.1.6其它

§2.2Cerny猜想

2.2.1函数的深度和完全深度

2.2.2常函数：进一步的讨论

2.2.3结论

第三章主要成果

§3.1弱单环分解和图的权重

§3.2其它的一些结论

3.2.1整体与部分

3.2.2线图

参考文献

致谢