迪布恩圖的直徑與寬直徑

Abstract

在圖形理論上，研究討論網路的容錯及傳輸延遲課題中，連通性及直徑是兩個很重要的參數；而迪布恩圖具有很小的直徑及很大的連通性，常久以來被視為很重要的網路模型。然而迪布恩圖有個很大的缺點，就是點的個數嚴重受限制，於是在1980年左右，由兩批的人，獨立的發展出迪布恩圖的一般化，它完全保留迪布恩圖的所有特性，卻又很技巧的讓點數個數不受限制，這個改良，大大的增進迪布恩圖的應用與重要性。 如果把有向迪布恩圖的方向性拿掉，迴圈也拿掉，同時也避免多邊的情況，那就可以得到無向的迪布恩圖。同理，從一般化的有向迪布圖，也可以得到無向的一般化迪布恩圖。在這篇論文中，我們主要討論這些迪布恩圖。 首先，在第一章中，我們介紹一些基本的圖論預備知識，這些在往後幾章中都會用到。第二章中，我們介紹迪布恩圖的已知結果，這些都是非常重要的結論；有些漂亮的定理，我們也適度的給予証明。在一般性的縱覽之後，就進入第三章；雖然無向迪布恩圖的連通性早就知道了，但是寬直徑卻一直不得而知，在這一章中，我們探討寬直徑，從而保証對任意兩點都有足夠多條的不同路徑，而這些路徑都不會太長。第四章，我們討論無向一般化迪布恩圖的直徑，對一部份的圖形的直徑，都有明確的答案，但也留下不少的難題，等待解答。最後一章，列出幾個重要而且急迫的問題，都是往後研究的重點所在。

In graph theory, the study of fault tolerance and transmission delay of networks, the connectivity and diameter of a graph are two very important parameters. Since the de Bruijn graphs and generalized de Bruijn graphs are known to have small diameters, and simple routing strategies, they have been widely used as models for communication networks and multiprocessor systems. Clearly, B(d; n) has dn vertices thus there is a restriction on the number of vertices. To conquer this disadvantage, a modication, generalized de Bruijn graphs, was obtained later by Imase and Itoh, and independently by Reddy, Pradhadn and Kuhl. The generalized directed de Bruijn graph GB(n;m) is a directed graph. Then, by replacing directed edges with undirected edges and omitting the loops and multi-edges of the directed de Bruijn graphs and generalized directed de Bruijn graphs, we have the undirected de Bruijn graphs and generalized undirected de Bruijn graphs respectively. In this thesis, we focus on these de Bruijn graphs. First, we have "introduction and preliminaries" in Chapter 1. Then, in Chapter 2, we have a survey of several important known properties and applications. After survey, we study the wide-diameters of undirected de Bruijn graphs in Chapter 3, and study the diameters of generalized undirected de Bruijn graphs in Chapter 4. Finally, in Chapter 5, we conclude this thesis with several concluding remarks.