论文摘要
网络的拓扑结构可以用图来表示，称为网络拓扑图。可以通过研究图的性质来研究网络的结构。研究图的性质的理论就是图论，图的染色是图论的一个重要内容。一般来说，图的染色分为顶点染色和边染色，而边染色又有严格边染色和f-染色等。图的染色具有广泛的应用，如在全光网络的波长分配问题中的应用等。本文所考虑的图都是有限简单无向图，用G来表示一个图，V（G）表示它的顶点集，E（G）表示边集，顶点v在图G中的度记为dG（v），在不至引起混淆的情况下简记为d（v）。图G的最大度记为Δ（G），即Δ（G）=（?）{d（v）}。f为定义在顶点集V（G）上的正整数函数，它给V（G）中的每个顶点v分配一个正整数f（v）。图G的一个f-染色是一个边染色，满足每个顶点v处至多有f（u）条边染相同的颜色。我们称f-染色图G所需要的最少颜色数为G的f-色数，记为χ′f（G）。如果对所有的v∈V（G）都有f（v）=1成立，则f-染色问题就归结为严格边染色问题。f-染色在网络设计、计算机网络中的文件传输，时间表等问题中有很强的应用背景。例如，在一个计算机网络中，令图G的一个顶点代表一台计算机，假定传输的文件都是同等长度的，每一条边表示两个顶点之间传输的一个文件，f（v）表示顶点v对应的计算机一次可同时传输的最大文件数。若求在最短的时间内完成传输任务，这就要求对图G进行f-染色，求其所用的最少的f-色数。在严格的边染色中，一个著名的结果是Vizing于1964年给出的：对任意简单图，有χ′（G）=Δ（G）或χ′（G）=△（G）+1，其中Δ（G）表示图G的最大度。同样，在f-染色中简单图的f-色数具有类似的性质，即对任意简单图，有χ′f（G）=Δf（G）或χ′f（G）=Δf（G）+1，其中Δf（G）=（?）{（?）}。由此，χ′f（G）=Δf（G）的图被称为Cf1类的，χ′f（G）=Δf（G）+1的图被称为Cf2类的。本文研究了图的f-染色，并得到了一些结果。共分为五章。在本论文的第一章绪论中说明了文章研究的背景及问题的提出，论文的工作及文章的组织结构；第二章介绍了图的严格边染色和f-染色若干进展；第三章讨论了图的f-染色的分类问题，证明了扇图、轮图、系列平行图、一般Petersen图、定义在圈C上的Petersen图的f-染色分类定理；第四章研究了f-染色中f-临界图的性质；第五章给出总结并展望下一步要做的工作。