制 約 の あ る ス ノ ヾ ン ニ ン グ プ リ 問 題 とこ つ と ヽ て
大 川 知*
On the Spanning Tree Prob■ ems with Restrictions
Satoshi OKAWA Abstract
Many probrems concerning network design are very important and considered to be diffdicult combinatorial problems to solve. In fact, most of them are kROWn tO be NP― complete.
We define a new network design problem ( and its subproblems ),the sapanning caterpillar problem, that is,the problem to decide whether or not, for a graph C ( with the degree at most d ) given as input, there exists a spanning caterpillar in Go Ve show this problem is
NP―
complete even if d≦ 3. It is a trivial problem for d≡
≦2 because a connected graph with the degree at most 2 is a cycle or a path. So our result is best for the degree constraint.
1.ィよじめ に
多数 の計 算 機 を相 互 に接続 し、分散 的 な環 境 で各 種 の処 理 を行 な うことの 利点 が あ き らか にな り、計算機 ネ ッ トワー クが構築 されて い る。特 に最近 は、
エ ンジニア リング ワー クステー シ ョン
(EWS)やパー ソナル コン ピュー タ
(Pc)を
も含 めて、 ネ ッ トワー クを構 成 した り、 それ らを中心 と した構 内 ネ ッ トワー クを構 築 した りす ることが多 くな って い る。 資源 の少 な い小型 計 算機 の利用者 は、 ネ ッ トワー クを介 して大型機 や他 の資源 を利 用 で きるので、
恩恵 は きわ めて大 きい。
この よ うな ネ ッ トワー クは計 画 的 に構 築 された場 合 も含 め、次 々 と新 しい 計算 機 が ネ ッ トワー クに加 わ って 、乱雑 な ネ ッ トワー クにな りが ちで あ る。
昭和
63年 12月 15日受理
*
電 気工 学科助 教授
そ こで 、既 存 のネ ッ トヮー クを見 直 し、 あ る意味で最適 なネ ッ トヮー クに改 造 す る とい う問題 が生 じる。 本稿 で は、 この よ うな ネ ッ トヮー クの問題 を、
グ ラフ の問題 と して定 式化 して考察 し、最適 なネ ッ トヮー クを得 るのは困難 で あ る ことをあ き らか にす る。
2.準備
本節 で は、 グ ラ フ、 問題 、計算量 な ど基本 的な事 項 について簡単 に説明す る (詳細 は文献 (1)(2)な どを参照
)。
次 に、本稿 で考察 す る問題 に関 して必 要 な定義等 を与 え、最 後 に問題 の定義 をす る。グ ラ フ とは有 限集合Vと, vの元 の対 (u, v)(u≠ v)の有 限集 合E か らな る組G=(V, E)で あ る。Vの元 を点 、Eの元 を枝 とい う。Gに お いて、枝 (u,v)と 枝 (v,u)を 区別 す る とき有 向 グラフ、区別 しな い とき無 向 グ ラフとい う。本稿 で は、無 向 グラフだけを考 え、無 向 グ ラフの意 味 で グ ラフ とい う ことにす る。
問題 とは、通常 、値 が不定 にな ってい るパ ラメー タゃ変数 を含む一般 的 な 形 を した問題 の こ とで あ る。不定 にな ってい るパ ラメー タゃ変数 に具体的 な 値 を入 れた ものを 問題 の実例 (instance)と い う。例 えば、2次方 程式 を解
く問題 といえば 、不 定 のパ ラメー タa,b, cを 含 むax2+bx+c=0
を解 く問題 を意 味 し、a=1, b=2, c=1と したx2+2x+1=oは
その実 例 で あ る。 あ る問題 を解 くアルゴ リズムとは、上述 の意 味の一般的な 形 の問題 につ いて 、 どのよ うな実例 が入 力 されて も解 くことが で きる解法 を 意 味 し、特定 の実 例 を解 くとい うもので はない ことに注意す る。
あ る問題 を解 くのに要 す る計算 時間を考 え るとき、実例 の大 きさに依存 す る と考 え るのが 自然 で あ るか ら、長 さnの実 例 に対 してt(■)ス テ ップ以下 で
計算 で きる とき、 その問題 の時間計算量 はt(■)であ る とい う。基本 ステ ップ と して何 を とるか は計算機 モデル に依存 す る。本稿 では計算機 モデルとして
(非決 定性)Turing機械 を考 え る。
問題 を解 くの に要す る時間 によ って問題 の難 しさを測 ることがで きる。非 決定性 TuriRg機 械 によ って多項式 時間で解 くことので きる問題 の クラスをN
Pと表 わす 。 あ る問題PがNPに属 して お り、 しか もNPに属 す る他 のす べ て の問題P'が決 定性 Turing機 械 で多項 式時 間でPに変 換 可能 であ るとき、
PはNP完全 な問題 で あ るとい う。NP完全 な問題 とは、NPの中 で最 も難
しい問題 で、現実 的 な時間 (決 定性多項式時 間)で解 くアル ゴ リズムが存 在 しない 問題 と考 え られてい る。
次 に本稿 で考察 す る問題 につ いて述 べ る。前節 で述 べたよ うに、 ネ ッ トヮ ー クは次第 に乱雑 な ものにな りが ちであ るので、それを編成 しなおす必要 が 生 じる。 この とき、幹線 と支 線 とが生 じるのはやむ を得 ない と して も、末端 か らで も十分速 く幹線 に入 れ るよ うに しなければ、 ネ ッ トヮー クの利用者 か
ら不満 が出 ることはあ き らか であ る。 この よ うな こ とを考慮 して、末端 か ら 長 さ 1の 道 で幹線 に入 ることので きるよ うに幹線 を決定 す る問題 を以下 に定 式化 す る。
まず 、末端 か ら長 さ 1で 幹 線 に入 るよ うな グ ラフ、キ ャタ ピラ (caterpil
lar)を
定 義 す る。す なわ ち、 キ ャタ ピラとは、次数 1の 点 を除去 して得 ら れ る グ ラ フが道 とな る木
Tc=(V, E)のこ とで あ る。 この とき、残 った 道 をキ ャタ ピラの幹 といい、 ネ ッ トワー クの幹線 に対応 す る。 あ き らか に、
道 、 ス ター グ ラフ もキ ャタ ピラで あ る。 グラフ
Gのスパ ンニ ングキ ャタ ピラ (spanning caterpi H ar, SC)と は、
Gのす べて の点 を連結 す るキ ャタ ピ ラの こ とで あ る。本稿 で扱 う問題 は、
SCを用 いて 次 の よ うに定義 され る。
スパ ン エ ン グキ ャ タ ピ ラ問題SC:グ ラ フGが与 え られ た と き、Gに SCが
存 在 す るか ど うか を判 定 せ よ。
次 数 制 限 スパ ンニ グキ ャタ ピ ラ問 題SC(d):次 数 がd以下 の グ ラフGが
与 え られ た と き、Gに SCが存 在 す るか ど うか を判 定 せ よ。
最 後 に、 次 節 で 必 要 な こ と を命 題 と して あ げ て お く。
[命 題 1]問題 PがNPに属 して お り、 しか も、既 にNP完全 で あ る こ とが 知 られ て い る問題 P'が
Pに
多 項 式 時 間 で変 換 可 能 な らば 、Pも
NP完全 で あ る。[命
題
2]i)グラフに対 す るハ ミル トン道 問題
HP・は
NP完全 で あ る。
ii)次 数
3以下 の グ ラフに制 限 した ときハ ミル トン道 問題
HP(3)も NP完全 で あ る。
3。
結 果
前節 で定 義 した 問題 につ いて考 察す る。問題
SC(d)が NP完全 で あ る ことが示 されれば 、問題
SCも NP完全 で あ る ことにな るか ら、前者 だ けを 考 えれ ば十分 で あ るが 、後者 は証 明の基 本 的 な考 え方 を よ く表 わ してい る と 考 え るので 、本稿 で は両者 につ いて証 明 を与 え る。 グラフ
Gのハ ミル トン道
(HP)は SCで
あ るが、
SCは一般 に は
HPでは ないか ら、
SCから
HPを得 る ことがで きるよ うにす るのが本節 の証 明の基 本 的 な考 え方 で ある。
問題
HPは次 の よ うな問題 で あ る。 グ ラフ
Gが与 え られた とき、
Gのす べて の点 を 1回 だ け通 るよ うな道 が存 在す るか を判定 せ よ。
*
[定理1]問題SCは NP完全 で あ る。
(証明)問題SCが NPに属 す る ことは あ き らかで あ るか ら、 問題HPが問 題SCに多項式 時 間で変換 可 能 で あ るこ とを示 して 、問題SCがNP完全 で あ る こ とを証 明す る。
問題HPの実例 をG=(V,E)と す る。Gにお いて 、d(v)=1の点 は存 在 しない もの とす る。 ここで、了=v∪ (v' lv∈V)、 こ=E∪
((v,
v')lv∈ V)と し、6=(V,百 )を構 成 す る。 この6を構成 す るの に
要 す る時 間 は、klVI(k:定 数)以下 、す なわ ち多項式時間以下 であ る。
この と き、次 の命題 が成立す る。
[命題] Gに HPが存在 す る必 要 十分 条件 は、6に SCが存 在 す ることで あ る。
(⇒)Gに ハ ミル トン道H=(V,EH)が 存 在 す る とす る。Cの構 成 法 か らT=(▼ , EH∪ {(v, v')lv∈ V})と す る と、 あ き らか にTは Gの Scであ る。
(← )6に SC=(V, Ec)が 存 在 す る とす る。 あ き らか に 、 (V, Ec―
{(v, v')lv∈ V))は Gのハ ミル トン道 で あ る。
よ って 問題HPが 問題 SCに多 項 式 時 間 で変 換 され る こ とが示 され た。
[定理2]問題SC(3)は NP完全 で あ る。
(証明)定理1の証 明 と同様 に して問題HP(3)を 問題SC(3)に 多 項
式 時 間 で変 換可能 であ ることを示 す。G=(V,E), d(v)≦ 3を問題
HP(3)の 実例 とす る。
Gに次数2の点 が あ る ときは、簡単 な変形 で解消 で きるか ら、Gは次数
3
の正規 グ ラフで あるとす る。 この とき、次 の操作 によってG'三 (V',E')を構 成 す る。 (図 1参照)
X(3)
X(5)X
X(4)
⇒
V(0)
z(1)
V(2)
V(5)
V(4)
y(3)
y(1) V(1)
y
Z(0)
V(3)
Z(5)
図l Gの 点vと vに G'の G(v)
y(2)
V'=∪ V(V)、 こ こ で 、
V∈
V
V(v)=(V(1)十
二
=0,1,・・ ・
,5}とす る。加算 は
6を法 とす る加算 を表 わ す もの と し、
E(v)=((V(1),V(1+1))li=0,1,2,
・
,5}と し、
G(v)=(V(V),E(v))とす る。 さ らに、
Eの各 枝
(u,v)に
対応 させて 、 あ る
j, kにつ いて
(u(2j), v(2k))なる枝
をつ け る。 この と き、
vに接 続 して い る
3本の枝 に対応 す る枝 をす べて異 な る点 につ け るよ うに
kを選 ぶ。 この
Eの枝 に対 応 した枝 の集 合 を
EOとし、
E'=∪ E(v)∪
E。 とす る。 この と き、次 の命題 が成立す る。
V∈V
[命
題
] Gにハ ミル トン道 が存在す る必要十分条件 は、
G'に SCが存在 す ることで ある。
(⇒)Gの ハ ミル ト ン 道H=(V,EH)が 存 在 す る と す る 。 そ れ が 、
で あ る とす る。
Hの各 枝
(vl, Vl+1)∈ EH⊂ Eに対 応 す る
G'の枝 が 、
(vi(2 ki),vi+1(2ji+1))∈
E。 で あ る とす る。
G(v)=(V (v), E(v))において 、
v(2j)と v(2k)とを結 ぶ長 さ 4の 道 を
v(2j)→ v(2k)とす る。 この とき
vl(2kl+1)vl(2kl+2)→ vl(2kl)v2(2j2)→ v2(2k2)‐ ・ ・
…Ⅲ Vi̲1(2kn‑1)vl(2jl)→
vi(2kl)vI+生 (2k)v(2j i+1)・・ ・ 中●
vn 1(2kn‑1)vn(2j n)―→ v(2j n+2)v(2i n+3)
は、
G'の道 とな り、 この道 に入 って い ない点 は、
G'及び、道 の構成法 か ら、道 か ら距離
1で道 に至 る点 で あ る。
従 って、 この道 に入 って い ない全 て の点
qに対 して
qに隣接 して い る道 の 点 の うちの
1つ pにつ いて 、
(p, q)をこの道 に付加 した グ ラフは
G'のSCで
あ る。
(←)G'に SCが
存 在 す る とす る。
C'の構成法 か ら
SCの幹 は、各
v∈Vに
つ いて、
V(v)の元 が一 団 にな って い るか ら、 その ブ ッロクを
B(v)と表 わ す こ とにす ると、
B(vl)B(V2)°
中
B(vn)と な っ て い る。 そ こで 、
V lV2… Vnを とる と、 これ は あ き らか に
Gのハ ミル トン道 で あ る。
よ って問題
HP(3)が問題
SC(3)に多項式 時 間 で変 換 され る こ とが
示 され た。
4.むす び
本稿 で は、計算 機 ネ ッ トワー クの再編 成 に関す る問題 を、 グ ラフGが与 え らえた ときGにスパ ンニ ングキ ャタ ピラが存在す るか ど うかを判定 す る問題 と して定式化 した。 そ して この問題 がNP完全 で あ る ことを示 した。 さらに、
この問題 の入力 の グラフにつ いて次数 を3以下 に制 限 した場 合 につ いて も、
NP完全 で あ る こ とを示 した。次数 が2以下 の連結 グラフは、道 で あ るか サ イ クル で あ るか の いず れいか で あ るか ら、 スパ ンニ ングキ ャタ ピラが存在 す る こと はあ き らか であ る。従 って本稿 で示 した結 果 は、多項式 時間で解 け る 場 合 とNP完全 とな る場 合 の境界 を明確 に した ことにな る。
SC問題 の他 の部分 問題 と して、幹 の長 さをで き るだ け短 くす る問題 も考 え られ る。 この問題 は、端局 が どの主局 に もで きるだ け速 くア クセ スで きる よ うにす る とい う課題 に対応 す る もので あ る。 この 問題 について も,NP完
全 で あ る こ とが 示 されてい るが(3)、 長 さに関 して多項 式 時 間で解 け る場 合 とNP完全 とな る場合 の境界 につ いて は未解決 であ る。
文 献
1) Fo Harary,"Graph Theory",Addisan― Wesley
2)M.R.Garey,Do S.Johnson,"Computers and lnstractitability",V.H.Free man and CompaRy,1879
