de Bruijn圖與Kautz圖的k元控制數(shù)和特殊圈.pdf

1、當前VLSI技術(shù)的進步，使得建造具有數(shù)千甚至數(shù)萬個處理器的超大型并行分布式系統(tǒng)已經(jīng)可以實現(xiàn)了.而在這些并行分布式系統(tǒng)中，最重要的一個步驟就是決定各個處理器之間連接的拓撲結(jié)構(gòu)，即互聯(lián)網(wǎng)絡(luò)（簡稱網(wǎng)絡(luò)）.這是因為網(wǎng)絡(luò)的拓撲性質(zhì)直接影響到并行分布式系統(tǒng)的硬件和軟件兩個層面的各種設(shè)計.de Bruijn圖與Kautz圖是應用比較廣泛的兩類互聯(lián)網(wǎng)絡(luò).
　　出于多方面的考慮，人們期望通過一定數(shù)量的處理器來控制整個網(wǎng)絡(luò)系統(tǒng).對于無向圖上控制問題的

2、研究是近年來的一個研究熱點.在一個無向圖G中，稱一個點控制它本身及其相鄰的所有點.對于正整數(shù)k≥1，圖G的一個k元控制集D是頂點集V(G)的一個子集，使得G中的每一個頂點被D中至少k個點控制.圖G的最小k元控制集的基數(shù)稱為k元控制數(shù)，記為(γ)k(G).
　　在并行處理系統(tǒng)中，由于圈的結(jié)構(gòu)可被用于模擬網(wǎng)絡(luò)的穩(wěn)定性，所以在圖中我們經(jīng)常選擇圈來作為考察對象.一個有向圈C的逆，記作(C)，是指一個滿足V((C))=V(C)且A((C))

3、={（v，w）|(w，v)∈A(C)}的圈.若存在一個同構(gòu)映射σ，使得σ(C)=C，則稱C是自逆的或σ自逆的.
　　在本文中，我們主要研究de Bruijn圖與Kautz圖的k元控制數(shù)和特殊自逆圈問題.本文分為四章.
　　在第一章，我們介紹了一些本文將要用到的有關(guān)圖論方面的基本概念.
　　在第二章，我們研究了無向de Bruijn圖（記為UB(d，n)）與無向Kautz圖（記為UK(d，n)）的k元控制問題，主要結(jié)果如

4、下:
　　(1)當d≥2，2d-1≥k≥2時，(γ)k(UB(d，n))≥「kdn/2d+1(]).
　　(2)當d≥2，2d≥k＞1時，(γ)k(UK(d，n))≥「k(dn+dn-1/2d+1(]).
　　在第三章，我們研究了在有向de Bruijn圖（記為B(d，n)）中，當d為偶數(shù)時的特殊圈問題，主要結(jié)果如下:
　　(1)設(shè)n＞2為偶數(shù)，那么在B（d，n）中不存在自逆的Hamilton圈.
　　(2

5、)設(shè)n≥2，在B(d，n)中至少存在d/2個長度為2n的σ自逆圈.
　　(3)當n為奇數(shù)時，在B(d，n)中存在長度至少為4的σ自逆圈當且僅當在B(d，n)中存在一條不包含交錯弧和σ不動點的路P=v1v2…vk，使得(σ(v1)，v1)與(vk，σ(vk))是交錯弧，其中k≤dn/2.
　　(4)當n為偶數(shù)時，在B(d，n)中存在長度至少為4的σ自逆圈當且僅當在B(d，n)中存在一條不包含交錯弧的路P=v1 v2…vk，并且

6、路P上存在2個不動點v1與vk，其中k≤dn/2+1.
　　(5)當n為奇數(shù)時，在B(d，n)中至少存在d/2個長為2n的σ自逆圈.
　　(6)在B(d，n)中至少存在d/2個長為4的σ自逆圈.
　　(7)若C是B(d，n)中的σ自逆圈，那么L(C)是B(d，n+1)中的σ自逆圈.
　　在第四章，我們研究了在有向Kautz圖中(記為K(d，n))，當d為奇數(shù)時的特殊圈問題.主要結(jié)果如下:
　　(1)對于d≥

7、3，并且n≥2為偶數(shù)，那么在K(d，n)中不存在σ自逆的Hamilton圈.
　　(2)當n為奇數(shù)時，在K(d，n)中存在長度至少為4的σ自逆圈當且僅當在K（d,n）中存在一條不包含交錯弧和σ不動點的路P=v1v2…vk，使得（σ（v1），v1）與(vk，σ(vk))是交錯弧，其中k≤dn+dn-1/2.
　　(3)當n為偶數(shù)時，在K（d，n）中存在長度至少為4的σ自逆圈當且僅當在K(d，n)中存在一條不包含交錯弧的路P=v