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

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