n 次元超立方体グラフcnのn 個の独立全域木の構成

Memoirs of the Osaka Institute

of Technology, Series·A

Vol.48,No.1(2003) pp.9~29

n次元超立方体グラフらのn個の独立全域木の構成

川 口 喜三男

情報科学部 情報システム科

〈2003年5

月

26

日受理〉

A construction of

n

independent spanning trees in a hypercube graph

C

_n

by

Kimio KAWAGUCHI

Department of Information Syste

皿

s, Faculty of Information Science and Technology

(Manuscript received May 26, 2003)

Abstract

In this paper it is shown that there exist n independent spanning rooted trees

尽…，r:•

in a n -dimensional hypercube graph C

n ,

and the maximum height of the

trees is given by the following expression :

1

芭

_Hei

ght(い

=

{::�

(n =1)

(2s n

s;

4)

(n�S)

- 9

1. 序論

グラフG=(V,E)の定点rEVを根とするn個の全域木刀，・・・，乃は，任意の点VEVに対 してVからrに至る刀，…，乃上の道Pi[v,r],・・・,P,,[v,r]が互いに内点独立であるとき独立で あるというグラフGがn個の独立な全域木刀，…，冗を持つならば，Gから高々n-I個の (VuE)-{r}の要素を取除いたグラフの任意の点Vからrへは少なくとも1本の道P;[v,r] が残存するので，Gを放送中心を持つ通信網のグラフモデルであると解釈するとき，Gは故 障耐性の高い，換言すれば信頼性の高い通信網を構成するということができる．亦，rを根と して構成された各全域木刀の高さHeight(T;(r))が小であるほど通信に要する時間は短い．

従来，Altaiand M.Rodeh [l]は，2連結グラフに於ける2個の独立全域木を見出す線形 時間アルゴリズムを与え，J.Cherian and S.N.Maheshwari [2]は，3連結グラフに於ける 3個の独立全域木をO(IV IIEI)時間で見出す方法を示した.A Zehavi and A Itai [3]は， 3· 連結グラフGに於いて任意の点rを根とする3個の独立な全域木が存在すること を示し，更に任意のK連結グラフは任意の点rを根とするK個の独立全域木を持つことを予 した五十嵐善英，等[4]は，任意のグラフGx,Gyがそれぞれnx,n 個の独立な全域木を持_y つならば，積グラフGx_xGYのn_x+ny個の独立全域木が構成できることを示した． 文献[4] に於ける一_{般的構成法を例えばn次元超立方体グラフenというように具体的グ} ラフに適用するとき，個々のグラフの特殊な性質を慮外に置き，一般論のみに立脚して独立 全域木の高さの最大を評価するfょらば，最悪ケー_{スを想定せざるを得なくなり，その結果文} 献[4]ではCnIこ対しては独立全域木の構成順序を C. =(···((C1 xCJxC1)x- ..)xC1 に基づいて行うとき，MaxHeight(T;) = 2n -1と評価し，又 c,, =(…_{(((C1 xC1)x(C1 xC1))x((C1 xC1)x(C} 1 xC1)))x(C1 xC1)…) に基づいて行うとき，MaxHeight(7;) =「3n/27と評価している． 上記の如く構成された独立全域木の評価基準をMaxHeight(T;)の最小化に置くならば， この基準に沿って構成法を定めるべきである．本稿はこの観点に立ってc,. の独立全域木を 構成し，

1

(n==l)

塗

_{�Height(T,)= { n + I (2 s; n 5 4)} n+2 (n�5) という結果を得しかもc,, =(…((C1 xC1)xC1)x・・・） xC1 果が得られることを示す嶋 く構成順序を用いてこの結

n次元超立方体グラフの独立全域木 3

2.

(V,E)は点の有限集合Vと

ヽ対の集合{ (x,y) I (x,y) = (y,x),x .= y;x,y EV}

oが存在するとき，Gにはル

ー_プも2 フG Eからなる特に異なる とEとの間に1

ー

Gは単純な無向グラフ である¢に って辺eEEに（恥巧）が対応するならば，e=(vp巧）又はV1V2と るという．以下本稿で扱うグラフはすべて単純な無向 VI, V2はe G=(V,E)に対して <. このと フである． フH=(V',E')が『こにE'kE すならば，HはGの部 分 フであるという． 気＝（片，Ei)とG2= CV2, 互）の直積G1x V = Vi X V2 = { (u, v) I U Ev;, VE v2}

E = { (u₁, v)(u₂, v),(u叫(u, iら)I U1U2 E E_p V E V₂, U E佐叫eEj により定義 さ れる.G1xG2をGIとG2の積グラフという． よう =(V,E)は， n フ 旦の点は2 即

({0,1},{

叫）； C,, "'Cn-l X C1

(a日叫％）で表すことができ，2点(an-!

…

a1ao), (bn-1…_{b/i,。)が隣接する，} (a,,_: 叫ao)(bn-1崎b。）が存在する

た

めの必要十分条件は，或るiがあってa』¢.b少 つa戸も(j¢i)を満たすことである．

2部グラフはG=(XvY,E) (但しXnY=<fi,X:t; ゆ，Y-:t=</J;X+Yとも く），v1v2eE ならばV1E Vi EY又はv1E Y,v2 EXであるような

フGに於いて点 vを端点とする辺がK フである． あるときVの次数はKであるといい，d(v) Kと <.Gのすべての点の次数がKであるときGはK・_{正則であるという.n次元超立方体} グラフ

e

llはn·正則である冤 無向グラフGに於ける の系 v← 1V1':f:;Vた1Vj (i':f:; j)を <, P[v0, v,,,] == P[vm, v0] = vmv正1'..V。である.mをその長さといい, Length(P[v0, v,,,]) 閏...v,,, に於いて特にV()=Vmであるとき，この道を閉路という道P[p,qJが特に部分 フH上にありこれを明示するとき，PH[p,q]と た P[ll

。,

vm] = ll

。

Vt ... Vm と き，P[v。心］はGの道であると い EE (i=l,2,· 噂貪，m) ．道には向きはな

＜．

Gの2点 u,v さ さ をu,v といい，dc(u,v)又はd(u,v) u,vを結ぶ2本の道u。(==u)u₁…_u i(=v)とv。(=u)v; ··· < l,l:::; j < m)を満 た すときこの2本の道は互いに Gの2 _{v)がui:t- vj (Is i} るという ·- 11

にu,vを結ぶn本の道の任意の2本が互いに内点独立であるとき，これらn本の道は内点独 立又は単に独立であるという． Gの任意の2点u,vに対し，Gの道P[u,v]が存在するとき，Gは連結であるといい，又独 立なn本のGの道J;[u,v],-··,P,,[u, v]が存在するとき，Gはn連結であるという． グラフTが連結であり，しかも閉路を持たないならば，Tは木であるという．木に於いては 任意の2点を結ぶ道は唯一_{存在する．特に木の1点rを指定するときrを根と呼び，Tを根付} き木という．木Tの点vと根rを結ぶ道P[v,r]の長さLength(?[v, r])の最大を木Tの高さ といいHeight(T(r))又はHeight(T)と書く．即ち Height(T) = Max Length(P[ v, r]) _veV

Gの部分グラフH= (V',E')が，特にV'=VであるときHをGの全域部分グラフという． 全 域 部 分 グ ラ フ Hが木であるときHは全域木であるという .U�VuEに対して G印〕=(W,WxW nE) (W =U nV)をUによって 誘導された部分グラフという．亦 F�VuEに対する誘導部分グラフG[VuE-F〕をG/Fと書く． 応・・'T,, はグラフG= (V,E)のrEVを根とするn個の全域木であるとする.Gの任意の 点vとrを結ぶ刀，・・・，乃の道F;[v,r], · • •, P,Jv,r]が互いに内点独立であるとき， n個の全域 木刀，···,T"は独立であるという．

3. 超立方体グラフの描画法

超立方体グラフ

g

を描くにはそれを2部グラフとして描くのが便利である．そこで先ず これに関連する若干の考察を為すことにする．次の補題はよく知られている． ［補題l] 2個以上の点をもつグラフが2部グラフであるための必要十分条件はすべての 閉路が偶数個の辺から成ることである

・

n次元超立方体グラフenがn-1次元超立方体グラフ_en-Iと1次元立方体グラフC_lの直 積として定義されることから，enの閉路はすべて偶数個の辺から成り，従って補題1により enは2部グラフである次に2部グラフとしてのenの標準的描画法を定める． 4点2正則2部グラフ 2次元立方体グラフ

G

を2部グラフとして描けば下図右のようになる． O' 1 O' l': Y

c,

ロ

゜

ー

〉

＇

゜

_:X

n次元超立方体グラフの独立全域木 5

8点3正則2部グラフ

2部グラフG(V=XuY,E)をここでは単に(X,Y)と書く.3正則2

しIXI= 4,1 YI= 4;X = {0,1,2,3} ,Y =

{0',1',2',3'})

_{の辺集合Eが，各点i'E fはX-};,} 点との間にのみ辺を有するとして定義されるとき，この8点3正則2部グラフをKjo•kh'h· と され グラフ(X,Y)(但 表ず例えば，各点i'E yから出 各点i'E y から出る辺

＼

0

2 3

j。、 て，下に示すように描くことができる． K 1230 を次の図が示すよう

vt

。

＇ .j

O' I' 2' 3': Y

鴻

X 2 一般にK. 量 “ ＊ Jo• 11·12·13· からjJ',j2•,jr, んの順に描くならば，例えばKl2_30に 対しては

0,3,2,1

の順に左から描けば，右の図のよう してXの点を描く順序を左 に描かれるこのように描き直すことにより全ての K 1230

//oh

y/[23

O' 1' 2' 3'

k祁k加]'が互いに同型であることが直観的に明らかになる． ［補題2] K 1230 3正則8点2部グラフ(X,Y) (IX 1=_{4,1 Y 1=4)はすべて3次元立方体グ} に同型である． 下左に示す3正則8点2部グラフK3210 と ラフである． K ・ 3210令

O' I' 2' 3'

鸞

フC3

．

=C3: 3次元立方体グラフC3は同一のグ O' 2

ーー

上述からC3の描画の標準としてK321。を用いる． 高次元の立方体の描画については以下のよう l) C_4の描画 る．

2個の Kmo の中 1 個を上下反転させて描けばC4が 2 部グラフとして描ける． O'

ー

＇ 2' 3'

₍₀

2

3) : y

゜

2

K

3210 3

(O'

ー

＇ 2'

3') :X

K ₃₂₁₀ 2) e_nの描画 同様に 2 個の 2 部グラフ Cn-1の中 1 個を上下反転させて下図に示すように描けばよい． C _n-1

�-

:Y e_n

4. e

_n

の点独立な全域木の帰納的定義

2次元立方体グラフ C2の点独立な全域木

i;

2

,

対が次の図のように定義できる．

:X

a`°

aN°

〗口°

c2

が

T22 C₂の任意の点 u から上図の点0へだ，月のそれぞれにより定義される道 Pi2[u,O], ぢ[u,O] を表によって示すと Pi2[u,O] Pi

[u,0]

と なる表から明らかなように c2の任意の点 u から点〇への道 Pi2[u,O], 界[u,O] は点独立 である．亦，表から明らかなように Height(刀2

)

= 3, Height(月）=3 が成り立つ． 本章では，

n

次元超立方体グラフ

c.

の点独立な全域木のh組(7;"'…_,

r;)

_{が帰納的に定義} できることを示す．唯，方法への洞察を容易ならしめるため， 帰納的定義の第 1 段としてC₃ aO aibO blaO bO laO lbO の点独立な全域木の3組(7;3,T/'乃りを構成し，これを初期値に設定する．次に定義の第1I段 に於いてCkー1の点独立な全域木の

(k-1)

組(I;k-1'…，冗勺）が定義されたと仮定してC_kの点 独立な全域木のK組（刀ピ..,½k_{) が定義できることを示す} ．その結果次の定理が得られる．

n次元超立方体グラフの独立全域木 7 ること ［定理l]n次元超立方体グラフellの点独立な全域木のn組(I;",・・・，だ）を帰納的に構成す 0を根とするとき，構成され た全域木T;"の高さに就いて ，しかも Height(�2_{) = 3 (i = 1, 2)} Height(J; 八=4 (i = 1,2,3) Height(T,") = Height(刀n-1)+ 1 Height(T,;') = Height(刀’＇ー1₎₊₂ .l

（

l,·.. ,n-1)

｝

( n 2:: 4) が成り立つ． （証明） [ I J先ず，C3の点独立な全域木の3組(T;3_{,T{,冗）を下回のように構成する．} d a b c d a b c

勾：

a b c d

冗：

゜

2 3

゜

2 3

゜

2 3 C3の各点名を上図のように定めると，C3の任意の点Uから の上の道だ[u,0] (i = 1,2,3)が点独立であることは次の表により容易に確かめられる． 吼u,0] f>i [u, 0] �[u,O]

亦表からも明らかな ように Height(刀3_{) = Height(Tj) = Height(冗）=4 である．}

[ II J任意の自然数Kに対してCk-Iの点独立な全域木の(k-1)組(I;k-1,…，冗勺）が定義され たと仮定してGの点独立な全域木のK組（冗，・・・，だ）が定義できることを示す． Ck-Iに対する（刀k_{-1, …J冒）からck1こ対する}

cr

t

_{,···,T/)を構成する方法の理解を容易} ならしめるため，具体例として 上述の（冗，勾，冗）からこに対する（刀4 ,・・・，だ）を如何に構 0への全域木か(i

=

1,2,3) aO blaO c2a0 dlaO laO 2a0 3dla0

albO bO c3b0 d3b0 lbO 2d3b0 3b0 a2c0 b3c0 cO d2c0 ld2c0 2c0 3c0 成するかを示す． ［（庁，…_{内）の構成法］} 一般にGは2部グラフであり，Ckの点集合の2部分割はV(Ck) る.X(Ck)=X,Y(Ck)= Y と略記すれば，V(C3)に対しては，前図に従って X = {0,1,2,3} Y = {a,b,c,d} とし，V(C4)に対しては (X(Ck),Y(Cん,)) と書け {O,l,2,3,0',1',2',3'} Y = {a,b,c,d,a',b',c',d'} とする．亦r;4(i = 1, …, 4)の部分グラフT,尺r;4+を誘導部分グラフ が＝四{O,l,2,3,a,b,c,d}〕炉＝戸{O',I',2',3',a',b',c',d'}) X -

15-となるように構成し更に

T/

―,

T,

4+を結合して

T/

を完成する．

2

部グラフ

G=G(X+Y,E)(

但し

X= {0,1,2,

…

},Y = {a,b,c,

…｝とする ）に対してその 反転℃

= :tG(X'+ Y', E')

を次のように定義する．

X'= Y = {a,b,c, ···}, Y'= X = {0,1,2, ···}, E'= E

グラフ

G=(X +Y,E)

の全ての点名mにダシュを付してm'と改名する操作を行ったと き，

G

d

= (x

d

+ y

d

, E

りと書いてこれを表す但し

E

勺ま点の改名に伴う自然な変更に因る． 上記の反転と改名の操作については，それよってグラフGのトポロジー_{は実質的に全く} 変らず，名目上の変更が行われるのみである． （例）

Y: a

b

Y':

O I

Y':

o' I'

G�.N

［冗の構成］ 先ず，

T

₄

4

―=

(X + Y,¢) (X = {0,1,2,3},Y = {a,b,c,d})

とする．

刀

3_{の反転とその点の改名操作により先ず}

_c

t_冗/

_{= ((X(}

1

_7;

3

_{)/ +(Y(}

_切り）

_d,E

りを求め ると次の図のようになるそこでは，

(X(

t_か）

t

_{= {a',b',c',d'},(Y(}

1_か））

_{d ={0',l',2',3'}.}

a b c d

゜

2 3 O' I' 2' 3'

゜

2 3 ⇒ 'G X'

し］

a b c d a'

b'

c'

d'

⇒ ＇b a ．．

口

d >

_＾

G t

刀

3

tTJ

ほり

d 更に

r;

4と共に辺を

2

重に使用するのを避けるため

2

0_と

_2'(

_一般に刀k十_{の構成に於いて} は

2

0

_,2

1

_{'・・・，2}

k

_-

3

_{)に対応する（元}

_3/

_{の点b',c'と点}

_l',2'

_を繋ぐ辺

_b'l',c'2'

_{を削除し，その代} りに辺

b'O',c'O'

を追加するこうして得られたグラフを

_T/

+とする（次図右半部参照）． 次に，

X(

冗―)の各点

_{I (I =0,}

・・・，

3)

と

Y(�

4

+)

の各点

I' (I= 0,

・・・，

3)

を繋ぐ辺

_{00',.. ·,33'}

及 び

Y(T/

―)の各点

a (a=a,.. ·,d)

と

X(�

4

₊₎

_の各点

_{a' (a=a, .. ·,d)}

_を繋ぐ辺

_aa',

_…,

_dd'

_を

追加する．以上の操作により得られるグラフが刀であるこれは下図のようになる．

Y(T,

り：

a b c d O' l' 2' 3'

T44:

n

次元超立方体グラフの独立全域木

，

�

4―

,

E(T

44―)

＝ゆ

庁＝（団）

d

-{b'l',c'2'} +{b'O',c'O'}

高さに就いては

Height(�

4

)= Length(33'

d

'

l

'a'O'O) = Height(J;

3

) + 2 = 6

が成り立つ．

[T

2

4,

冗の構成］ 先ず，

T

23

,冗を以ってrt-,冗

―とする． 次に対，冗から

c

t

_r;t

_{,(勺げを構成し，それぞれ}

_T

24

+'½

4

+とする

． だの構成は勾―の点

b

と

r;

4

+

の点

b'

を繋ぐ辺

bb'

を追加することにより完了する．又冗 の構成も冗―の点

c

と乃4+の点c'を繋ぐ辺cc'を追加することにより完了する． これを図示すると次のようになる． Y(T�

り：

a b c d O' l' 2' 3'

冗：

X

(T� り： 0

Y(冗）： a 2 3 a ＇ b' c' d'

が＝勾

ヰ＝（て）

d b _c d O' l' 2' 3' ．． 4 T 3 X(冗）： 0 2 3 a ＇ b' c' d'

冗＝冗

灯＝（

＄

だ）

d 亦，上図より明らかに

Height(T,

り=(Height(T,4

_{+)-1) + 2 = (Height(T,}

_りー

_{1)+2=5(i=2,3)}

が成り立つ．木刀4

_{+の根は点}

_O'

_{の隣接点となるからである．} ［かの構成］ 先ず刀4-=かとする． 炉は，X

(尽）

= {a',b',c',d'}

と

Y

可）

= {O',

l

',2',3'}

の和集合を点集合とし，辺集合を

E(尽）

= {a'O',b'l',c'2'}

とするグラフである．ここで注意するべきことは，3 個の辺の端点

O',

l

',

2

'

が

O'

及び関係式

2;

<がを満たす非負整数

i= 0,1

に対応する(20

_)'

_{と(2り＇であるこ} とである更に言えば，刀k+_{の構成に於いては}

_O'

_{以外に関係式}

₂

_{i く}

₂

k

_-

2_{を満たす非負整数}

i = 0,-··,

k

-3

に対応する(i)'(i=O,-··,k

-3)

が

E(

刀k+

)

の辺の端点となることである． 刀4は，X

(炉）

一

{b',c'}(b',c'

は上述の

(i)'(i= 0,1)

を端点とする辺のもう一方の端点） の点

a',

d

'

と

Y(か）の点

a,

dを繋ぐ辺

aa',

dd

',及び

O'

を除く

Y(

刀4

+)

の全ての点

1',2',3'

と

X(T;

4―)の対応する点

1,2,3

を繋ぐ辺

_{1 1',22', 33'}

を追加して完成する．

Y(T;4): a ．． 4

Tー

b _c d O' I' 2' 3'

x

可）： 0 2 3

a ＇

b' c' d' 冗＿＝か 炉

木の高さに就いてはHeight(T;4)= Length( 3'3dla0) = Height(T;3) + 1 = 5 が成り立つ．

［考察］上述の構成によれ ば以下が成り立つ．

(1) i )庁＝訊冗=T;, 冗＝冗

ii) E(T44―) =</J

従って ，（冗，

T/

―，芹）はc;(=CJの点独立な全域木の

3

組であり，又uが口の点であるな

らば冗に於けるuから0への道月[u,O]の内点は，E(T₄4―)=</Jであるので，すべて

c:

の点

である．故に道J;4[u, O], 月[u,O],冗[u,O],だ[u,O]は，uが

c;

の点である限り点独立である． (2) i) E(炉）= {a'O',b'l',c'2'}

ii) Tt=(団）d' 灯＝（団）d

iii) r:i4+ = (団）d - { b'l', c'2'} + { b'O', c'O'}

u E

vcc:)

から点0への各全域木T,勺こ沿う道に就いては場合を分けて考察する．

a) u = O'の場合：各全域木T,勺こ沿う道は

町O',O]= O'a'aO, P/[O',O] = O'b'bO, 肝[O',O]= O'c'cO, だ[0',0]=0'0

であるから，こ れらは点独立である．

b) u

*

_{O'の場合：（＄か）［（団）}d

,(団）dは，だ，T;,だとトポロジー_{を等しくするから，点}

独立である．かに於いて点b,cは葉であるから｝ド[v,O] ( v

*

0)が点wE{b,c} (辺bl,c2)

を含むのは，v=wのときに限られる従って道をJ;3[b,O]= blaOからbOへ, f;3[c,O] = c2a0

からcOへ変更したとしても点独立性に影響しない．（ ＄冗）dとr:i4+の相違はこの変更に照応

するから，任意の点UE V(C:)からO'へのTt =(tT;iぷ�+ = (1_y;3_t及びT44+_{のそれぞれ}

の道町[u,O'], 町[u,O']及び 凡�+[u,O']の点独立性は保障さ れる更に道月�+[u,O']の終点

O'の直前の点はb',道尺4+[u,O']の終点O'の直前の点はc'であるから，

冗の道：因[u,0]=[坪[u,0']-0']・[bO]= u· · ·b'bO

冗の道：村[u,0]=[

バ

4+[u,0']-0']・[cO]= u· · ·c'cO

冗の道：だ[u,0]=凡�+[u,O']·[O]= u· ·-0'0

の三者も点独立である点uEV(Cりに対する勾の道の

c;

_{部分は[bO], 冗の道の}

c;

部分

n次元超立方体グラフの独立全域木 11

るのは道の始点がb',c'のときだけであり，それはかに於ける道Fi3_{[ b, O], Fi}3 _{[ c, O]の}一_部 bl,c2に相当するb'l',c'2'である更に，一_{般に庁の道の}

c;

_{部分はV(C�}―_{) -{O,b,c}の点の}

みを通過する．故に，刀4は他の三者と道の内点を共有することはない．

以上により，上述で構成された4組（冗，

rt,冗，だ）は点独立であることが示された．

木の高さに就いては， Height(T;り= 4 (i = 1,2,3) に対してC4では

Height(T; り=Height(T;3_{) + 1 (i = 1, 2, 3), Height(T}

44) = Height(刀り+2 が成立するが，この関係式は実はck(k�4)に対して

Height(か）= Height(か―1) +1 (i=J, .. ·,k-1), Height(

刀）

= Height(庁―') +2 と一_{般化され，結局MaxHeight(I;}k_{) = k + 2} ISiSk を得る． [ Ckの点独立な全域木のK組（冗， ···,Tkりの構成] (Figure 1, 2 ;Table 1, 2参照） [T2k'…，尽の構成］ T2k-l'…，刀けを以ってT/―,…J言とする． 次に，T2k-l'…，冗勺から（元k-1/,…，（切勺Vをそれぞれ構成し，r/+,…J口とする． r;k _{(i = 2, …，k-l)の構成はY(T;}k―_{)のct-2 + 1)番目の点P; (前述の[T} 24'冗の構成］では P; ( (22-2 + 1) = 2 番目の点はb , (23_{-2 + 1) = 3番目の点はc)とX((T;}k_{+/)のct-2 + 1)番目} の点p; を繋ぐ辺P;P;を追加することにより完成するこの構成法では，木刀k+_{の任意の点U} から0への道は，刀K十の根を上記のp; とし，これに道p;p;Oを付加したときUから0に至る 道である．その最大の長さがかの高さとなるので次式が得られる．

Height(T;k、)=Height(T;k+)+ 2=(Height(r;k_{-t) -1) + 2 = Height(r;}k_{-l) + 1 (i = 2, …，k-l)} [ T2k'…，尽相互の独立性］ が―(i= 2, …，k-l)の任意の点xから点0への木r;k_{上の道が通過するすべての点はr;}k_­ の点であるので，これらの道が[x,O](i = 2, …, k-l)が内点を共有することがないのは帰納 法の仮定により保障される又，r;k_+と庁― が同一_{構造を持つことから'r;}k+_{の任意の点yか} ら点O'へのr;k_{上の道が通過する点はすべてr;}k+ の点であるので，だ[y,O'] (i = 2, · · ·, k- l) は同様に内点を共有することはない．但し，yから点0へ至る道はP,k_{[y,O']の終点O'の直前} の点p'(X((T;k+_/)のct-2 _{+ 1)番目の点）からY(T;}k_―)のct-2 _{+ 1)番目の点pへ行き，次い} で0に到着する従ってP,k [y,O](i = 2, ···,k-I)も内点を共有することはない． ［庁の構成］ 先ず庁―＝庁―1と定義する．今，便宜上庁―の点集合X(庁―） +Y(庁―_）を X(T;k-) = {〇_,l—’・・・，(2k-2 -1)_} Y(冗―）= { Q�,t'..'(2k-2

—叫

又，岱の点集合X(汀） +Y(万） を

X(

応）

= {o+,l十,-··,(2k-2-lt} Y(万）={0�,1>··,(2k-2-lt}

とし描画に於いては，X(冗―) uX(炉） は左からo_,・・・，(2k-Z -})_,Q十’・・・，(2k-2-ltの順

に描 き，Y(冗） uf(万）も 左から0�, ···,(2k-Z-})�,0

い

···,(2k-2-Itの順に描くものとす

る又この順序を用いて（左から）何番目 （例えば〇［はY(刀k+)の1番目 ）の点という言い方

をする．

次に刀K十内部及び冗―，刀k_{+間の辺を定義する．}

汀内部では，点i=0+,2�,2し，... ,2戸EX(汀） とY(炉）の点i'の間に辺ii'を定義する．

か，岱 間の辺は，I) j+ EX(万）ー{2�,2�,.--,2戸｝とY(T; k

-)-{(2�)', (2�)',-· ·, (2い），｝ 内の同番目の点jびの間に辺j十［を定義する.2) j: Ef(T;k+)-{O�}とX(T;k-)-{Oー｝内の

同番目の点jこの間に辺j:j_を定義する． 冗の部分木刀k―_{の高さは刀}k_{-1の高さに等しく，それ は刀}k_―の道だ― [z , O] (但し ，Kが偶数 のときz = (2k-Z -IL kが奇数のときZ = (2k_{-Z -}r)の長さであるこのzに接続される} 江の道は長さ0 であり，Kが偶数のとき点(2k-2_{-It , kが奇数のとき点(2}k_-2 -}入に外な らない従って次式が成り立つ． Height(庁） = Height(か） +I [ Tk_とTk _{:. .} k 2' ,

T

k_-1 間の独立性］ T/ (i = 2, …，k-1)の構成 ではT/十_{中の点p を発して点0に至る 道は，T/}― に於いては僅 かに点(2;―2)'E f(が―) を通過するのみであるこれに対しかでは(i-2_)'EY(T;k_{-) と刀}k_十の

点を繋ぐ辺は定義されてい ないから点(T2_{), を通過するこ とはない} 又，炉の辺(2� -2)(2�-2)'(i = 2, · ·- , k-1) は，r;k+と共有されるが ，Tt(j = 1 ,i)中の点pを 発して点0に至るそれぞれの道だ[p,O] ,だ[p,O]がこの辺を共有するこ とはないこれ はこ の辺の2個の端点と点0 との位置関係が，その間の距離d(2�-2,0) 及びd((2�2)',0)の比較： 木研に於いては d(2�-2 ,0) > d((2�-2)',0) 木亡に於いては d(2戸，0) < d((2�-2)',0) より が示す ように木刀k十と木T;k_{十に於いて相反するからである} ． なお，炉の辺〇十飢はT;k(i = 2,-· ·, k -1)により共有され ない． ［刀の構成］ 刀kー1を反転して得たけ；Kー1の点名を次のように改める．

n次元超立方体グラフの独立全域木 13

X(:i: 刀k-1) =

{〇

+'I十,···,(2k-2

—叫

Y(t圧）= { 0�, I�,·· ·,(₂k-2 -It} このように改名されたサ；k -1に更に若干の修正を加える先ず，辺(2_�)(2

り',…, (

2戸）(2_戸）＇ を削除し，新たに辺2°_{＋十'++' ,}0'io'...2戸0� を加える．こうして得られたグラフを乃k+とする． 次に刀を定義する．刀:k―の点名を次のように定義する． X(½k-) = {〇_, 1_, ・・・，(2k-2

—叫

_{Y(½k-) = { 0�, C·..'(}2-2k

—叫

刀の辺集合は空であるとする.Tk-k ,Tk人＋間の辺は，X(T: k -), Y(庁）間とX(T:k -), Y(か）間 にo_o

い

l

」い...

,(2k-l -l)_(2k -l -1): 及びo�o+,O十'...,(2k -l -lt(2k-l -I :trk-1

L

を定義する． 1 から修正を経て定義されたTK の高さは修正に拘らず変化しない勺；Kk+ ー1に於ける最 長の道の経路に修正が関係しないからである即ちTk+ん． の高さは庁―1の高さに等しい．一 方，刀k―内部で定義された辺はないので，次式が成立する． Height(

だ）

= Height(

正）

+2 ［刀とか，勾，・・・，見間の独立性］ かの点p からの道に関しては Tk十がyk-'k I の辺の付替えによる修正であり，修正された1 辺は全て点〇：に接続されてそこから直接に点0(=0ー）に至る．一方，冗，勾，・・・，尽に於しヽて はP*〇：のとき道が[p,O_],

応

_[p,0_{],・・・，尽[p,}O_{] はいずれも点〇：を通過することがない}． 他方，庁は修正前は冗―1と同構造であり，応，冗，…，応は乃(k-1)-'½(k-1―₎ ，・・・，刀�1-1)―と同 構造である更に，刀K― 内には辺は存在せず yk-_{'k 内の点qから点0(=0ー）への刀}K_{の道はqか} ら直ちに刀k+の点へ移り，やがてyk+_{K の点〇：に至り，そこから直接 0 に到着する}．他 方，Tk Tk I'2 , ・・・，尽に於いてはqから〇への道はTk+ Tk+ _{I '2 , ・・・，応の点を通過することはない．} 以上述べたことから刀とTk Tk _{I' 2'…，応は互いに独立であると結論される．}k 以上は，一定の構成原理に基ずいてk-1次元超立方体グラフCk _{-Iの点独立な全域木の組} 応，・・・，刀:�ー］りが構成されたと仮定して，K次元超立方体グラフ

G

の点独立な全域木の組 仇・・内）が同じ原理を用いて構成できることを示した．故に，一般にn次元超立方体グラ フこの点独立な全域木の組（庁，・・・，亡）は存在し，それを帰納的に構成することができる． 独立木の高さの最大に就いては定理1より次の系1が得られる

.c

_{nに対するHeight(r} (i == 1, · • •, n) は下の式により定まるが，値を下表のよ-_{つに示せば（但し，2�n�6のみ示す），系}／）

．

1の確認が容易であろう．

従って，MaxHeight('z;'') = k + 2 (但し4�n鐸） 1,;;,;,, Height(J;") CII c2 C3 C4 Cs c6 TI " 3 4 5 6 7 T;' 3 4 5 6 7

四

II 4 5 6 7 T;' 6 7 8

匹

＂ 7 8 T6 " 8 但しぶに対する独立全域木の裔さに就いては，次のような変更で改善される． a b

冗．↓

゜

↓叫↓

い

rt:

. . .

. . ..

a ＇

゜

b' C

O'

冗：／

゜

冗：

. - - -

-C ＇

゜

a ＇ 高さに就いては，Height(T;

り=

5 (1 Si S 4)が成り立つ． 同様の変更がより高次元のC,,(n�5)に対してできるかどうかは差当って不明である． 故に，次の系を得る． ［系1] 1 (n = 1)

M翌

Hight(T,")�{n + 1 (2 Sn S 4) n + 2 (n�5)

5. 放送中心(Broadcasting Centre)を有する通信網への応用

．

木Tの1点uをレベル0として，この点0に放送中心が配置されているとする．今，点0か

n次元超立方体グラフの独立全域木 15 ら通信文がレ_{ベル1の全ての点に向って送られたとする．レベル1の点はこの通信文を受信} すると，自身がTの葉でない限り同通信文を更に隣接する全てのレベル2の点に移牒する． この過程（レベルKから隣接する全てのレ_{ベルk+lへの通信文伝達）が繰返されてTの全} ての葉が通信文を受領し終えたとき通信網としての放送作業は完了する． さて，通信網Tに故障がない場合上述の放送作業により通信文がTの全ての点に伝達され ることは明らかである．しかし 1 点（中継局）でも或いは 1 辺（通信線）でも故障すれば通信 は杜絶する．このことは網のトポロジーが木構造であるとき耐故障性が薄弱であることを意 味する．そこで耐故障性を高める工夫を為すことは大いに有用であるということができる． 通信網としてn次元超立方体グラフ豆を用いるとする前章の定理1で示したように点 独立な全域木のn組（冗，・・・，亡）を構成し，定点0に放送中心を配置し全庁を用いて上述の 放送作業を行うとする今グラフenのn-1個の要素（点或いは辺即ち計算機或いは通信線 ）に物理的に故障が生じ，これらは機能を失ったと仮定する．豆の故障していない任意の点 pへ向う点 0からの刀",…, r:'の道Pi"[O,p],・・・，だ[O,p]は互い に内点独立であるか ら，n-1個の故障によって少なくとも 1 個の道だ[O,p]は故障した要素を含むことはな い.pの任意性から，n-1個の故障にも係らずenの故障していない全ての点へ通信文が伝達 されるということができる．即ち，放送を目的とする通信網として，独立なn個の全域木の組 （庁，…，T,,")が定義されたn次元超立方体グラフC "Iま耐故障性が高いということができる． 亦，通信設備に物理的故障が発生しない場合でも通信文に間歌的(intermittent)誤伝送が 生じる場合を想定するとき，受信側に於いて多数決論理に基づいて通信文を選択するならば 高い確度で正しい通信文を得ることが可能である． 以上の議論は点独立なn個の全域木の組（刀",···,T,,n_{)が定義される任意のグラフGに対} し言えることである． 更に全域木T/'の高さは通信文の放送と中継の最大回数を表すから，Max Height(I;11)が 小さいことが通信文伝達に要する時間を短縮させるために望ましい要件となる．文献 [4] の 積グラフに対する全域木構成法では，こに就いてはMax Height(I;")の下限は「3n/27であ ることが示されている．本稿ではこの値は，2:-;'.;n:-,;4に対してはn+lであり，n�5に対して はn+2である従って本稿の構成法が優れていると言える．

6. 結 論

本稿ではe_ntこ対する独立なn個の全域木の構成を，n::;3 に対しては直接に構成し，一般 のnに対してはe_n-\のn-1個の独立全域木を用いて定義するという帰納的定義によって行 った．これを文献 [4] の構成法と比較検討すると，本稿の構成法自体は文献 [4] に於ける一

般的構成法の一_{特殊例と見ることができる.e} nに対してn 個の独立全域木が存在すること の一_{般的証明を目的とするならば，文献[4]のみで充分であるといえる．しかし，可能な限り} 高さの低い全域木を実際に構成することをも目標とするとき，帰納的定義の本性から構成法 の繰返し適用によって目的の全域木を求めなければならないその際，繰返しの各段階に於 いて Ck-I に対する k-1 個の全域木のいずれを選んで Ckに対する第K番目の全域木刀の構 成に用いるべきかが問題となる文献[4]はこの面での検討を欠いている．本稿ではこの問 題に関してはCk-I に対する k-1 個の全域木の高さが同一でない点に着目しつつ繰返し構成 法を適用した結果，系1に示した結果を得ることができた． 本稿の結果を総括すると，n 次元超立方体グラフ豆は一_般にC ,,_111 と C111 (l�m<n) の直 積グラフ Cn-m xC111 であるが，特にC,, = en-I xc, としたときの構成法を扱ったのが本稿の方 法である．一般化してm:C:2の場合に有利な結果が得られるであろうヵ叱いう問題が残るが， それは否定的である従って，n次元超立方体グラフに関しては現状では本稿の構成法が単 純でもあるので最良であるといえる．

参 考 文 献

[l] A.Itai and M.Rodeh, The multi-tree approach to reliability in distributed networks, Information and Computation, Vol.79, pp.43-59, 1988.

[2] J.Cheriyan and S.N.Maheshwari, Finding nonseparating induced cycles and in­ dependent spanning trees in 3-connected graphs, J. Algorithms, Vol.9, pp.507-537, 1988.

[3] A.Zehavi and A.Itai, Three tree-paths, J. Graph Theory, Vol.13, pp.175-188, 1989.

[4]小保方幸次，飽豊，岩崎至宏，五十嵐善英，積グラフの独立な全域木について， 情報処理学会研究報告「アルゴリズム」， No.049-004, 1995.

n次元超立方体グラフの独立全域木 17 a b c d e h _{O' ]}' _{2' 3' 4' S' 6'} 5

T

ー

゜

2 4 6 7 7' h' a b c d e h _{O' I' 2' 3' 4' 5' 6' 7'} TS 2

。

2 4 6 7 _{a' b' c ，} が 5

r

a b c d e h ) W I' 2' 3' 4 5' 6' 7' TS 3

゜

2 4 6 _{e ，}

r~

g' h' a b c d e h _{O' I' 2' 3' 4' 5' 6' 7'} TS 4

゜

2 4 6 a b c d e h _{O' !' 2' 3'}

“'

_5' 6 _7' TS 5

゜

2 4 5

Length(尺[3',0]) = 7

Length(f>s[h,O]) = 7

Figure 1.

（訊だ，冗，T},冗）

for C5

が

[u,0]

瑣u,O]

瑣u,0]

改u,0]

瑣u,0]

IaO

lbO

ld2c0

If4e0

l l'a'O'O

2a0

2d3b0

2c0

2g4e0

22'a'O'O

3dla0

3b0

3c0

3h7 f4e0

33'd'l'a'O'O

aO

albO

a2c0

a4e0

aa'O'O

blaO

bO

b3c0

b5e0

bb'O'O

c2a0

c3b0

cO

c6e0

cc'O'O

dlaO

d3b0

d2c0

d7f4e0

dd'l'a'O'O

4a0

4f5b0

4g6c0

4e0

44'a'O'O

SfiaO

5b0

5h6c0

SeO

55'f'2'a'O'O

6g2a0

6h5b0

6c0

6e0

66'g'2'a'O'O

7dla0

7h5b0

7g6c0

7f4e0

77'd'l'a'O'O

e4a0

e5b0

e6c0

eO

ee'O'O

fiaO

f5b0

f7g6c0

f4e0

f f'I'a'O'O

g2a0

g7h5b0

g6c0

g4e0

gg'2'a'O'O

h3dla0

h5b0

h6c0

h7f 4e0

hh'3'd'l'a'O'O

O'a'aO

O'b'bO

O'c'cO

O'e'eO

O'O

I' laO

l'b'bO

I'd'2'c'c0

l'f'4'e'e0

l'a'O'O

2'2a0

2'd'3'b'b0

2'c'c0

2'g'4'e'e0

2'a'O'O

3'3dla0

3'b'b0

3'c'c0

3'h'7'f'4'e'eO

3'd'l'a'O'O

a'aO

a'l'b'bO

a'2'c'c0

a'4'e'e0

a'O'O

b'I'laO

b'bO

b'3'c'c0

b'S'e'eO

b'O'O

c'2'2a0

c'3'b'b0

c'cO

c'6'e'e0

c'O'O

d'dlaO

d'3'b'b0

d'2'c'c0

d'7'f'4'e'eO

d'l'a'O'O

4'4a0

4'f'S'b'b0

4'g'6'c'c0

4'e'e0

4'a'O'O

5'5/IaO

5'b'b0

5'h'6'c'c0

5'e'e0

S'f'I'a'O'O

6'6g2a0

6'h'5'b'b0

6'c'c0

6'e'e0

6'g'2'a'O'O

7'7dla0

7'h'5'b'b0

7'g'6'c'cO

7'f'4'e'e0

7'd'l'a'O'O

e'4'4a0

e'S'b'bO

e'6'c'c0

e'eO

e'O'O

『flaO

f'5'b'b0

f'7'g'6'c'c0

f'4'e'e0

f'I'a'O'O

g'g2a0

g'7'h'5'b'b0

g'6'c'c0

g'4'e'e0

g'2'a'O'O

h'h3dla0

h'S'b'bO

h'6'c'c0

h'7'f'4'e'e0

h'3'd'l'a'O'O

n次元超立方体グラフの独立全域木

₁₉

a b c d e f g h i j k I m 11 o p 0'l' 2'3' 4' 5'6'7'8' 9'10'11'12'13'14'15' 6

T

ー

r

2

0 I 2 3 4 5 6 7 8 9 IO 11 12 13 14 15 a' b'c' d'e'f'g'/,'i'j' k' {' m'n' o' p' a b c d e f g h i j k I m n o p O'I' 2'3' 4' 5'6'7'8' 9'10'I]'12'13·14'15' 0 I 2 3 4 5 6 7 8 9 10 IL 12 13 14 15 a' b'c' d'e'f'g'h'i'j' k' I' m'n' o' p' a b c d e f g h i j k I m 11 o p O'l' 2'3' 4' 5'6'7'8' 9'10'11'12'13't4'15'

だ

3 0 l 2 3 4 5 6 7 8 9 10 11 12 13 14 15 a' b'c' d'e'『g'h'i'j' k' I' m'n' o' p' a b c d e f g h i j k I m 11 o p O'l' 2'3' 4' 5'6'7'8' 9'10'11'12'13' 14'15'

だ

4 0 I 2 3 4 5 6 7 8 9 10 11 12 13 14 IS a' b'c' d'e'f' g'h';'j' k' I' m' 11' o' p'

a b c d e f g h i j k I m n o p O'1' 2'3' 4' 5'6'7'8' 9'to'I I'12'13'14'15'

6

T

₅

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 a' b'c' d'e'f'g'h'i' / k' 「 m'n' o' p' a b c d e f g I, i J k I m n o p O'I' 2'3' 4' 5'6'7'8' 9'10'11'12·13'14'15'

戸

6 0 l 2 3 4 5 6 7 8 9 10 11 12 13 14 IS a' b'c' d'e'f'g'h'i'j' k' I' m' n' o' p' Length(P,[l',OJ) = 8 ; Length(P,[h',OJ) = 8 ; Length(凡[15,0])= 8

Figure 2.

_{（冗，冗，冗，}

_T,;6

,

冗，刀）

for c6

21-J;6[u,O] 月[u,O] IaO lbO 2a0 2d3b0 3dla0 3b0 aO albO blaO bO c2a0 c3b0 dlaO d3b0 4a0 4f5b0 SflaO 5b0 6g2a0 6h5b0 7dla0 7h5b0 e4a0 e5b0 flaO f5b0 g2a0 g7h5b0 h3dla0 h5b0 8a0 8j9b0 9 jlaO 9b0 1ok2a0 IOl9b0 lldlaO IIl9bO i8a0 i9b0 jlaO j9b0 k2a0 kl 1l9b0 l 3diaO l9b0 12m4a0 l2n9b0 13/laO 13n9b0 14g2a0 14pl5n9b0 1sh3dla0 I5n9b0 m4a0 ml3n9b0 nSJiaO n9b0 o 6g2a0 ol5n9b0 p7dla0 pl5n9b0 月[u,0] ld2c0 2c0 3c0 a2c0 b3c0 cO d2c0 4g6c0 5h6c0 6c0 7g6c0 e6c0 f7g6c0 g6c0 h6c0 8k!Oc0 9/!0cO IOcO IIkIOcO ilOcO jllklOcO kIOcO lIOcO 12olOc0 - . → . -13pl4o!Oc0 14o!Oc0 15o!Oc0 ml4ol0c0 nl5ol0c0 o!OcO pl4o!Oc0 P,.6[u, O] lf4e0 2g4e0 3h7 f 4e0 a4e0 bSeO c6e0 d7 f4e0 4e0 5e0 6e0 7f4e0 eO f4e0 g4e0 h7 f 4e0 8ml2e0 9nl2e0 !Ool2e0

-llpl3m!2e0 il2e0 jl3ml2e0 kI4ml2e0 一. - ・―→ l 15p 13ml2e0 12e0 13ml2e0 14ml2e0

-

-

- . 15pl3m 12e0 ml2e0 nl2e0 Ol2e0 pl3ml2e0 Ps6[u, O] 月[u,0] lj8i0 l l'a'O'O 2k8i0 22'a'O'O 3/1 lj8i0 33'd'l'a'O'O a8i0 aa'O'O b9i0 bb'O'O clOiO cc'O'O d1 Ij8i0 dd'l'a'O'O 4m8z0 44'a'O'O 5nl 3 j8i0 55'f'l'a'O'O 6oI4k8iO 66'g'2'a'O'O 7 pl lj8i0 77'd'l'a'O'O eI2i0 ee'O'O f13}8i0 ff'l'a'O'O gI4k8iO gg'2'a'O'O h1s/1 Ij8i0 hh'3'd'l'a'O'O 8i0 88'a'O'O 9i0 99'j'l'a'O'O IOiO I OIO'k'2'a'O'O 1 lj8i0 1 11 l'd'l'a'O'O iO ii'O'O j8i0 JJ'l'a'O'O k8i0 kk'2'a'O'O II Ij8i0 ll'3'd'I'a'O'O 12i0 1-2.1.2. 'm'4'a'O'O 13j8i0

面丘

('l'a'O'O 14k8i0 面咋'2'a'O'O 15/ 1 lj8i0

后五

3'd'l'a'O'O m8i0 mm'4'a'O'O n 13 j8i0 nn'5'f'I'a'O'O ol4k8i0 oo'6'g'2'a'O'O pl Ij8i0 pp'?'d'I'a'O'O

Table 2. Tree·paths

が

[u,0] (i=l,2,---,6) for UEV(C6) (continuedtothenextpage)