论文部分内容阅读
网络的拓扑结构可以用图来表示，称为网络拓扑图。可以通过研究图的性质来研究网络的结构。研究图的性质的理论就是图论，图的染色是图论的一个重要内容。一般来说，图的染色分为顶点染色和边染色，而边染色又有严格边染色和f-染色等。图的染色具有广泛的应用，如在全光网络的波长分配问题中的应用等。本文所考虑的图都是有限简单无向图，用G来表示一个图，V(G)表示它的顶点集，E(G)表示边集，顶点v在图G中的度记为d_G(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)的图被称为C_f 1类的，χ′_f(G)=Δ_f(G)+1的图被称为C_f 2类的。本文研究了图的f-染色，并得到了一些结果。共分为五章。在本论文的第一章绪论中说明了文章研究的背景及问题的提出，论文的工作及文章的组织结构；第二章介绍了图的严格边染色和f-染色若干进展；第三章讨论了图的f-染色的分类问题，证明了扇图、轮图、系列平行图、一般Petersen图、定义在圈C上的Petersen图的f-染色分类定理；第四章研究了f-染色中f-临界图的性质；第五章给出总结并展望下一步要做的工作。