论文部分内容阅读
组合网络理论是数学和计算机科学交叉形成的一个新的研究领域,是互联网络研究的重要工具。而作为组合网络理论重要组成部分的添加边问题,在互联网络的实际应用中更是发挥着重大作用。添加边问题的解决是相当困难的,Schoone等人已经证明了它是一个NPC问题。 对给定的正整数t和图H,在图H中添加t条边后得到图G(称为变更图),求解所有添边方式下产生的变更图的最小直径,这就是本文重点研究的“添加边问题”的一个变型情况。此类变型情况的研究对“添加边问题”的最终解决具有相当重要的意义。 对于两类简单的基本图——n个节点的无向路径P_n和无向回路C_n,令P(n,t)和C(n,t)分别表示在P_n和C_n中分别添加t条边后得到的变更图的最小直径。Schoone等人已证明:当n≥5时。对于t≥3且n≥5,Chung和Garey证明了:当t为偶数时,当t为奇数时。 本文研究了在无向回路C_n中添加t(t=3,4)条边后得到的变更图的最小直径问题,通过构造出一类变更图计算得到上界,以及对所有添边方式下产生的变更图分情形进行理论证明给出下界,最终得到:当n≥9时,当n≥30时。 同时,本文还对在无向路径P_n中添加t(t≥4)条边后得到的变更图的最小直径问题作了进一步的研究,通过构造出一类变更图,改进了P(n,t)的上界。令θ=n mod 2(t+1),我们证明得到:当n≥5时, 如果θ=t+1,t+2,t+3; 如果θ=t+4,t+5,t+6或者0≤θ≤t。