對一類最小圖的研究

對一個與并行結(jié)構(gòu)和通信網(wǎng)絡(luò)設(shè)計密切相關(guān)的圖論公開性問題進行了研究。討論了圖的結(jié)點數(shù)為n，連通度至少為k，k-直徑至多為d的條件下的最小圖問題，給出了一般條件下最小圖邊數(shù)條數(shù)的上、下界，在此基礎(chǔ)上，得到了兩種條件下最小圖邊數(shù)的計算公式，結(jié)合已有的圖論結(jié)果，對文中所提到的最小圖進行了構(gòu)造。
關(guān) 鍵 詞 圖; 公開性問題; 連通度; k-直徑; 直徑

在并行結(jié)構(gòu)和通信網(wǎng)絡(luò)的設(shè)計中，往往希望構(gòu)造一個滿足一定條件的最小網(wǎng)絡(luò)，即滿足條件鏈路最少的網(wǎng)絡(luò)，以減少網(wǎng)絡(luò)材料開銷。若把網(wǎng)絡(luò)結(jié)點看著圖的頂點，鏈路看著圖的邊，一個網(wǎng)絡(luò)可以模型于一個圖。本文將對圖的頂點數(shù)為n，連通度至少為k，k-直徑至多為d的條件下的最小圖的邊數(shù)問題進行分析研究。
1 有關(guān)定義
在文獻[1]中介紹了有關(guān)圖的容器(Container)理論和它的發(fā)展現(xiàn)狀。容器是對單路徑的擴充，在此基礎(chǔ)上，擴充了圖的連通度和直徑的概念，提出了圖的寬距離和寬直徑的概念。設(shè)G表示一無向簡單圖(圖中無自環(huán)、無平行邊)，u、v表示圖G中的頂點(也稱為結(jié)點)，V(G)表示圖G中的頂點集，概念定義如下[1]。
定義 1 圖G的兩頂點間的一個容器C(u,v)是u、v間所有頂點不重合的路集合；容器C(u,v)的寬度是指該集合的勢，記為w(C(u,v))；容器C(u,v)的長度是指這個路集合中最長路的長度，記為l(C(u,v))。
定義 2 圖G中的兩頂點u、v之間的w-寬距離是指u、v之間所有寬為w的容器長度的最小值，記為dw(u,v)，即：dw(u,v)=min{l(Cw(u,v)), u≠v}，其中Cw(u,v)表示u、v之間寬度為w的容器。