Length of edge 10
10 10 10 10 10 10
10
10 10
v u
Distance of u and v = 60
10
e’
u’
Facility F’
u’’ q e’’
Facility F’’
T’ T’’ T’’’ T’’’’
v’ v’’
図 5.3: 木Tの設備F0，F00と隣接する長さの部分辺e0，e00
性質 13 木構造ネットワークをT，設備をF，Fに隣接する部分辺をe=(u;v)とする．た だし，F \e=vである．また，T0 \e =vなる最大の部分木をT0，T00\e=uなる最大の 部分木をT00とする（図5.2）．このとき，設備 Fに部分辺eを追加することによる距離和
の削減量D D(e) は，次式で表される．
D D(e)=D(F)0D(F [e)=l (e)w T
00
:
(5:4)
性質 14 木構造ネットワークをT，部分辺をejとする．設備Fがejに含まれるならば，ej の端点を含みejに含まれる設備で，Fより距離和の大きくないものがある．
証明 性質13による．
また，距離和の削減量は性質15，16を満たす．
性質 15 木構造ネットワークをT，ある点q，長さ（> 0）の部分辺をe0，e0上の点をv， パスP(q;v)上の長さの部分辺をe00とする．部分辺e0，e00上の最もqに近い点をそれぞれ
u
0，u00とする．そして，e0\F0 =u0，e00\F00 =u00なる設備をF0，F00とする．また，部分 辺e0，e00の最もqより遠い点をそれぞれv0，v00とする．更に，T0 \e0 =v0なる最大の部分 木をT0，T00\e0 =u0なる最大の部分木をT00，T000\e00 =v00なる最大の部分木をT000とする
（図5.3）．このとき，設備F0，F00に対する部分辺e0，e00の距離和削減量DD(e0)，D D(e00) は，次式を満たす．
D D(e 0
)=DD(e 00
) (w
T 00
\T 000
=0)
D D(e 0
)<DD(e 00
) (otherwise)．
(5:5)
e’
u’
Facility F
u’’ q e’’
T’ T’’ T’’’ T’’’’
v’ v’’
図 5.4: 木Tの設備Fと隣接する長さの部分辺e0，e00（重心q 2V(T000)）
証明 wT00\T000 = 0ならばwT0 = wT000なので，性質13よりDD(e0) =DD(e00)．さもな くばwT0 <wT000なので，DD(e0)<DD(e00)．
性質 16 木構造ネットワークをT，Tの重心q，設備F，Fに隣接する長さの部分辺をe0 =
(u 0
;v 0
)，e00=(u00;v00)とする．ただし，e0\F =u0，e00\F00 =u00である．また，部分辺e0，
e
00の最もFより遠い点をそれぞれv0，v00と表す．更に，T0\e0 =v0なる最大の部分木をT0，
T 00
\e 0
=u
0なる最大の部分木をT00，T000\e00 =u00なる最大の部分木をT000，T0000\e00 =v00 なる最大の部分木をT0000とする（図5.4）．このとき，設備Fに対する部分辺e0，e00の距離 和削減量D D(e0)，DD(e00)は，次式を満たす．
DD(e 0
)=D D(e 00
) (w
T 0000
=w T
=2かつwT00\T000 =0)
DD(e 0
)<D D(e 00
) (otherwise)．
(5:6)
証明 wT0000 =wT=2かつwT00\T000 =0ならばwT0 =wT000なので，性質13よりDD(e0)=
DD(e 00
)．さもなくばwT0 <wT000なので，DD(e0)<D D(e00)． 一方，全対距離和は次の性質17，18を満たす．
性質 17 木構造ネットワークをT，設備をF，Fに隣接する部分辺をe=(u;v)とする．た だし，F \e=vとする．また，T0 \e =vなる最大の部分木をT0，T00\e=uなる最大の 部分木をT00とする（図5.2）．このとき，設備 Fに部分辺eを追加することによる全対距 離和の削減量DP(e)は，次式で表される．
DP(e)=P(F)0P(F [e)=l (e)w T
0
w T
00
:
(5:7)
証明 辺 e の長さ l(e) = 0の場合は，F [e = Fであることから全対距離和の削減量
DP(e) = 0 である．辺 e の長さが 0 以外の場合は，Tの頂点集合 Vは，V(T0)，V(T00) に分割できる．設備 Fに辺 e を追加したとき，二点 vi，vjの距離は，vi;vj 2 V(T0) と
v
i
;v
j
2V(T 00
)の場合は変化せず，vi 2V(T0)，vj 2V(T00)の場合はl (e)wiwj減少する．し たがって，全対距離和はl (e)wT0wT00減少する．
性質 18 木構造ネットワークをT，部分辺をejとする．同じサイズの設備F0とF00がとも にejに含まれるならば，F0とF00 の全対距離和は等しい．
証明 性質17による．
また，全対距離和の削減量は性質19，20を満たす．
性質 19 木構造ネットワークをT，Tの重心をqとする．また，性質15と同様にe0，e00，F0，
F
00，T0，T00，T000，T0000を表す（図5.3）．このとき，設備F0，F00に対する部分辺e0，e00の 全対距離和削減量DP(e0)，DP(e00)は，次式を満たす．
D P(e 0
)=DP(e 00
) (w
T 00
\T 000
=0)
D P(e 0
)<DP(e 00
) (otherwise)．
(5:8)
証明 wT0;wT000 wT=2，wT00 = wT 0wT0，wT0000 = wT 0wT000である．したがって，
w T
00
\T 000
=0ならばwT0 =wT000なので，性質17よりDP(e0)=DP(e00)．さもなくばwT0 <
w T
000なので，DP(e0)<DP(e00)．
性質 20 性質16と同様にT，q，e0，e00，F，T0，T00，T000，T0000を表す（図5.4）．このとき，
設備Fに対する部分辺e0，e00の全対距離和削減量DP(e0)，DP(e00)は，次式を満たす．
D P(e 0
)=DP(e 00
) (w
T 00
\T 000
=0)
D P(e 0
)<DP(e 00
) (otherwise)．
(5:9)
証明 wT0;wT000 wT=2，wT00 =wT 0wT0，wT0000 =wT 0wT000である．したがって，性 質19と同様に，wT00\T000 =0ならばD P(e0)=DP(e00)，さもなくばDP(e0)<DP(e00)．
よって，距離和と全対距離和は次の性質21を満たす．
性質 21 木構造ネットワークをT，Tの重心qを含む設備をF，Fに隣接する長さの部分辺を
e
0，e00とする．このとき，Fに対する部分辺e0，e00の距離和と全対距離和の関係は，DD(e0)<
DD(e 00
)ならばDP(e0)<D P(e00)であり，逆も成り立つ．また，DD(e0)=DD (e00)ならば
DP(e 0
)=D P(e 00
)であり，逆も成り立つ．
e’
u’
Facility F
q u’’
e’’
T’ T’’ T’’’ T’’’’
v’ v’’
Weighted centroid
図 5.5: 木Tの設備Fと隣接する長さの部分辺e0，e00（重心q 2V(T00\T0000)） 証明 長さ > 0とする．部分辺e0，e00上の最も Fに近い点をそれぞれu0，u00，最も遠 い点をそれぞれv0，v00とする．また，T0\e0 =v0なる最大の部分木をT0，T00\e0 =u0なる 最大の部分木をT00，T000\e00 =u00なる最大の部分木をT000，T0000\e00 =v00なる最大の部分 木をT0000とする．重心qがT0000にも含まれる場合は，性質16，20より，DD(e0)< DD (e00) かつDP(e0) <DP(e00)である（図5.4）．重心qがT0にも含まれる場合も同様．一方，重 心qがT00\T000のみ含まれる場合を以下に示す（図5.5）．DD(e0) < DD(e00)ならば，性 質13よりwT0 <wT0000．また，wT0000 wT=2．したがって，性質17よりDP(e0)<D P(e00) である．同様に，DD (e0)=D D(e00)ならばD P(e0)=DP(e00)，DD(e0)>DD (e00)ならば
DP(e 0
)>D P(e 00
)である．
5.2.3
全対距離和を指標とした最適設備問題
全対距離和を指標とした最適設備における性質について議論する．
5.2.3.1 最適な連続木形状設備
距離和最小の連続木形状設備は，距離和最小の連続木形状設備を求めることにより得ら れることを示す．
距離和最小の連続木形状設備は性質22を満たす．
性質 22 木構造ネットワークをT，Tの重心をq，距離和最小の連続木形状設備をFとす る．すると，Fはqを含むか，さもなくばqの隣接頂点vjとqの間の辺ejに含まれる．ただ し，後者の場合，vjも重心である．
e’
Facility F
e’’ q
T’ T’’
v’ v’’
Weighted centroid u’’
u’
図 5.6: 木Tの重心qを含まない設備Fと長さの部分辺e0，e00
証明 Fはqを含まないとする．長さ（>0）の部分辺をe0 =(u0;v0)，e00 =(u00;v00)とす る．ただし， 最もqに近いFの端点をu00として F \e00 = u00，e00 P(u00;q)，またu00以 外のFの端点をv0として v0 e0，e0 Fとする．また，T0 \e0 = v0なる最大の部分木を
T
0，T0000\e00 = v00 なる最大の部分木を T00とする（図 5.6）．すると，F=e0が頂点を含む か，F=e0が頂点を含まずwT00 >wT=2 の場合，性質16よりD(F [e00=e0) <D(F)なので，
Fは距離和最小でない．F=e0が頂点を含まない場合，設備F，部分辺e0，e00は，一つの辺
e
j
=(v
j
;v
k
)2Eに含まれる．そして，wT0 =wT00 =wT=2なので，頂点vj，vkはともに重 心となり，そのうちの一つはqである．したがって，Fはqを含むか，さもなくばqの隣接 頂点vjとqの間の辺ejに含まれる．
同様に，全対距離和最小の連続木形状設備は性質23を満たす．
性質 23 木構造ネットワークをT，Tの重心をq，全対距離和最小の連続木形状設備をFと する．すると，Fはqを含むか，さもなくばqの隣接頂点viとqの間の辺eiに含まれる．た だし，viは，qを含まないTの重み最大の部分木に含まれる頂点である．
証明 Fはqを含まないとする．そして，性質22と同様にe0，e00，T0，T00を表す（図5.6）．
すると，F=e0が頂点を含まない場合，性質20よりP(F[e00=e0)=P(F)である．よって，F と全対距離和の等しい設備F0で，F0=e0が頂点を含むものがある．一方，F=e0が頂点を含む 場合，性質20よりP(F [e00=e0)<P(F)なので，Fは全対距離和最小でない．したがって，
Fはqを含むか，さもなくばqの隣接頂点vjとqの間の辺ejに含まれる．さて，以下ではqを 含まずqの隣接頂点vjを含むTの最大の部分木をTj，Tjの重みをwTjと表す．Fがqの隣接 頂点viとqの間の辺eiに含まれるとすると，性質18より，同じ全対距離和でqを含む設備F0
Facility F’’
v’ q v’’
Weighted centroid Facility F’
Partial tree F
e’ e’’’ e’’’’ e’’
図 5.7: 木Tの重心qを含む，最適な連続木形状設備F0と距離和最小の連続木形状設備F00 がある．もし，wTk >wTiなる子頂点vkがあるならば，qを含むek上の長さの部分辺をe00，
F
0のq以外の端点を含むF0上の長さの部分辺をe0とすると，P(F[e00=e0)<P(F)なので，
Fは全対距離和最小でない．したがって，qのすべての隣接頂点vjに対してwTi wTj． よって，距離和最小の連続木形状設備と最適な連続木形状設備は，次の性質24，25，26 を満たす．
性質 24 距離和最小の連続木形状設備は，最適な連続木形状設備である．
証明 木Tのサイズは設備サイズ上限lより大きいとする．このとき，最適な連続木形状 設備も距離和最小の連続木形状設備もサイズはlとなる．距離和最小の連続木形状設備をF とする．FがTの重心qを含む場合，性質21よりFは最適な連続木形状設備である．Fがq を含まない場合，性質22よりFはTの2つの重心間の辺 ejに含まれる．よって，性質14 よりTの重心を含み辺 ejに含まれる距離和最小の設備F0がある．性質21より，F0は最適 な連続木形状設備である．したがって，性質18よりFは最適な連続木形状設備である．
性質 25 2つ以上の頂点を含む設備に対し，最適な連続木形状設備と距離和最小の連続木 形状設備は等しい．
証明 木Tのサイズは設備サイズ上限lより大きいとする．このとき，最適な連続木形状 設備も距離和最小の連続木形状設備もサイズはlとなる．Tの重心をq，最適な連続木形状 設備をF0，距離和最小の連続木形状設備をF00とする．ここで，性質22，23より，F0とF00 はqを含む．すると，F0と F00の積F =F0 \F00はqを含む部分木である．Fのサイズl0は
設備F0とF00のサイズlより小さいとする．長さ（>0）の部分辺e0は，e0 F0でe0 \F00 が空か点である部分辺で，その一つの端点v0はF0の端点とする．同じく長さの部分辺e00 は，e00 F00で e00\F0が空か点である部分辺で，その一つの端点 v00は F00の端点とする．
パスP(q;v0)上の長さの部分辺e000は，e000 F0でe000\F00が点となる部分辺とする．パス
P(q;v 00
)上の長さの部分辺e0000は，e0000F00でe0000\F0が点となる部分辺とする（図5.7）．
すると，性質13より，DD (e000) DD (e00)．性質17，21より，DD(e0000) DD(e0)．性質
15より，DD(e0) DD(e000)，D D(e00) D D(e0000)．したがって，DD(e000) =DD(e00)とな る．よって，部分木F000 =F00[e000=e00は距離和最小の連続木形状設備であり，積F0\F000 のサイズはl0+となる．以上により，最適な連続木形状設備F0に対し，積Fのサイズがl となる距離和最小の連続木形状設備が存在する．すなわち，F0は距離和最小の連続木形状 設備である．逆は，性質24による．
性質 26 木構造ネットワークTの各辺の長さが1の場合，最適な離散木形状設備と距離和 最小の離散木形状設備は等しい．
証明 離散木形状設備は2つ以上の頂点を含む．よって，性質25の証明において，=1 とすればよい．
距離和最小の連続木形状設備や，木構造ネットワークTの各辺の長さが1の場合の距離 和最小の離散木形状設備の算出はO(n)時間で算出できるので[40]，この場合の最適な木形
状設備はO (n)時間で求まる．
5.2.3.2 最適な離散木形状設備
図5.8に，頂点数n=6の木Tに対するサイズ3の離散木形状設備を示す．図のF0はサ イズl =3の距離和最小の木形状離散設備，F00は最適な離散木形状設備であり，D(F0)=
14< 15=D (F 00
)，P(F0)= 64>63= P(F00)である．したがって，最適な離散木形状設 備と距離和最小の離散木形状設備が一致しないことが分る．
5.2.3.3 最適な連続パス形状設備
先ず，最適な連続パス形状設備が距離和最小の離散パス形状設備と異なることを示す．図
5.9のF0はサイズl =20の最適な連続パス形状設備，F00は距離和最小の連続パス形状設備 であり，D(F0)=23>22=D(F00)，P(F0)=129 <134 =P(F00)である．
また，次の性質27が示される．