辺容量付き電力需給ネットワーク *

辺容量付き電力需給ネットワーク _*

丸田 真平

^†a)

西関 隆夫

^†b)

Parametric Power Supply Networks with Edge-Capacities

^∗

Shimpei MARUTA

^†a)

and Takao NISHIZEKI

^†b)

あらまし 辺容量付き電力需給ネットワークはグラフGで表現できる．Gの各点は供給点あるいは需要点で あり，供給量あるいは需要量が割当てられており，各辺には辺容量が割当てられている．パラメトリックネット ワークでは，供給量，需要量及び辺容量は変数λの関数である．各需要点は，丁度一つの供給点からグラフG の辺を通してその需要量だけの“電力”を受け取りたい．一方，各供給点は，幾つかの需要点へGの辺を通して

“電力”を送ることができるが，送る電力の合計はその供給量以下である．無論各辺を流れる電力フローはその辺 の容量以下でなければならない．このようなことが可能かどうか調べたい．また不可能ならば，全ての需要量を 一様にr(0≤r <1)倍に減少させて，そのようなことを可能にしたい．このようなrの最大値r^∗を求めたい．

本論文では，木であるグラフGに対してこれらの問題を解くアルゴリズムを与える．

キーワード アルゴリズム，木，最大供給率問題，パラメトリックネットワーク，分割問題

1.

^{ま え が き}

辺容量付き電力需給ネットワークはグラフ

G

で表 現できる．

G

の各点は供給点あるいは需要点であり，

供給量あるいは需要量が割当てられており，各辺には 容量が割当てられている．（

G

に供給点が複数ありえる ことが，通常のネットワークフロー問題と大きく異な る．）供給点

v

の供給量を

s

_vと表し，需要点

v

の需要 量を

d

_vと表し，辺

e

の容量を

c

_eと表す．定常ネット ワークでは，供給量，需要量及び辺容量が全て非負の 整定数である．一方，パラメトリックネットワークで は，供給量，需要量及び辺容量は，時刻，気温，原油 価格などを変数

λ

とする関数である

[1]

〜

[6]

．このと き供給点

v

の供給量を

s

_v

(λ)

と表し，需要点

v

の需要 量を

d

_v

(λ)

と表し，辺

e

の容量を

c

_e

(λ)

と表す．グラ フ

G

が木である定常ネットワーク及びパラメトリック ネットワークを，それぞれ定常木ネットワーク及び パラメトリック木ネットワークと呼ぶ．図

1

の定常木 ネットワークにおいて，供給点は正方形で，需要点は

†関西学院大学理工学部情報科学科，三田市

Kwansei Gakuin University, 2–1 Gakuen, Sanda-shi, 669–

1337 Japan

a) E-mail: [email protected] b) E-mail: [email protected]

*本論文は学生論文特集秀逸論文である．

円で描かれており，供給量や需要量はその内側に書か れており，辺は直線分で描かれており，辺にその容量 が付けられている．図

2(a)

はパラメトリック木ネット ワークを表しており，その

λ

とともに変動する需要量

d

_v3

(λ), d

_v4

(λ)

及び辺

e = (v

3

, v

5

)

の容量

c

_e

(λ)

は図

2(b)

に描かれている．

各需要点

v

は，丁度

d

_vだけの

“

電力

”

を一つの供給 点からグラフ

G

の辺を通して受け取りたい．一方，各 供給点

v

は

G

の辺を通して幾つかの需要点へ

“

電力

”

を送ることができるが，送る電力の合計はその供給量

s

_v以下でなければならない．このとき，グラフ

G

か ら何本か辺を除去して

G

を幾つかの連結成分に分割し て，各成分には供給点が丁度一つ含まれ，その供給点 からその成分内の各需要点へその需要量だけの電力フ ローを流し，しかも各辺を流れるフローはその容量以 下であるようにしたい．（除去された辺にはフローは流 れない．）このような分割はグラフ

G

の許容分割と呼 ばれている

[4], [7]

．定常ネットワークの分割問題は与 えられたグラフ

G

に許容分割があるかどうかを問う．

パラメトリックネットワークの分割問題では，許容分 割をもつ変数値

λ

の全てを見つけたい．もし定常ネッ トワーク

G

に許容分割がないならば，

0 ≤ r < 1

なる 実数

r

を用い，全ての需要量

d

_vを一様に

r

倍に減少 させて，新しい需要量を

d

_v

= r · d

_vとしたときに，

G

図1 (a)許容分割のない辺容量付き木ネットワークT，

(b)最大供給率r^∗ = 3/7に対する新しいネット ワークとその許容分割

Fig. 1 (a) Steady tree network T with no feasible partition, and (b) new network constructed from T for the maximum supply rate r^∗ = 3/7.

に許容分割があるようにしたい．このような

r

の最大 値

r

^∗を見つけたい．この

r

^∗を最大供給率と呼び，

r

^∗ を計算する問題を最大供給率問題と呼ぶ

[4]

．

図

1(a)

の木

T

には許容分割がなく，

T

の最大供給率

r

^∗は

3/7

である．

T

の各需要量を新たに

d

_v

= (3/7) · d

_v にした新しい木を図

1(b)

に示す．新しい木の許容分割 は図

1(b)

で点線で表されている．各辺に付けられた 括弧の中の数字は，その辺を流れるフローの値である．

分割問題は定常直並列ネットワークに対してすら

NP

完全であるので

[8]

，最大供給率問題は

NP

困難で ある．したがって，どちらの問題も，定常直並列ネット ワークに対してすら多項式時間では解くことができそ うもない．定常木ネットワークに限定すれば，分割問 題は線形時間で解くことができる

[8], [9]

．一方，辺容 量がないならば，定常木ネットワークの最大供給率問 題が多項式時間で解け，パラメトリック木ネットワー クの分割問題が擬多項式時間で解けることが知られて いる

[4]

．しかし，辺容量がある場合のアルゴリズムは 知られていなかった．

本文では，まず文献

[4]

のアルゴリズムを拡張して，

辺容量があっても定常木ネットワーク

T

の最大供給率 問題が多項式時間で解けることを示す．

T

の点数を

n

とし，

T

の対数サイズ（すなわち

T

の供給量や需要量 である整数を二進数表現したときのビット数の総和）

を

L

とすると，そのアルゴリズムの計算時間は

O(nL)

である．次に，辺容量付きパラメトリック木ネットワー クに対する分割問題を解くアルゴリズムを与える．供 給量，需要量及び辺容量が整数係数をもつ区分的線形 関数であるとき，そのアルゴリズムの計算時間は擬多 項式である．より正確にいうと，全ての需要量，供給 量及び辺容量の整数係数の絶対値の合計を

W

とする と，そのアルゴリズムの計算時間は

O(nW

²

)

である．

2.

定常木ネットワークの最大供給率問題 この節では，辺容量付き定常木ネットワークの最大 供給率問題が多項式時間で解けることを示す．

T = (V, E)

を辺容量付き定常木ネットワークとする．

V

は木

T

の点集合であり，

E

は

T

の辺集合である．

全ての供給点からなる集合を

V

sとし，全ての需要点か らなる集合を

V

dとする．無論，

V = V

s

∪ V

dであり，

V

s

∩ V

d

= ∅

である．

n = |V |

，

n

s

= |V

s

|

とする．定 常木ネットワーク

T

の許容分割

π = (V

1

, V

2

, · · · , V

_ns

)

とは，集合

V

の

n

s個の部分集合

V

1

, V

2

, · · · , V

_nsへ の分割であり，

1 ≤ i ≤ n

sなる各

i

について次の

(a)

及び

(b)

を満足するものである．

(a) V

_i は

T

の連結部分グラフ，すなわち部分木

T

_i を 誘 導 し ，

V

_i は 丁 度 一 つ の 供 給 点

u

を 含 み ，

v∈Vi/{u}

d

_v

≤ s

_uである．

(b)

部分木

T

_iの各辺

e = (v, w)

を流れるフローの値

ψ

_eは

e

の容量

c

_e以下である．すなわち

ψ

_e

≤ c

_e である．なお，

ψ

_e

=

x∈Des(w)

d

_xである．ただ し，部分木

T

_iを供給点

u

を根とする根付き木と みなしたときに辺

e

の端点

v

が端点

w

の親である とき，点

w

及び

w

の全ての子孫からなる集合を

Des( w )

とする．

分割問題は，与えられた木

T

の許容分割を見つけ る問題である．辺容量付き定常木ネットワークに対す る分割問題を

O(n)

時間で解くアルゴリズムは既に知 られている

[9]

．そのアルゴリズムを

Partition

^と呼

ぶ．

Partition

を繰り返し用いて，最大供給率問題を

解く．

木

T

の最大供給率問題は，全ての需要点

v

の需要 量

d

_vを新しい需要量

d

_v

= r · d

_vに置き換えたとき，

T

に許容分割があるような

r

の最大値

r

^∗を求める問

題である．

r

^∗は

T

の最大供給率と呼ばれる．

r

^∗は

1

よりも大きいかもしれない．

明らかに次の補題が成り立つ．

補題

1. r

は非負実数とし，木

T

の全ての需要量

d

_vを

d

_v

= r · d

_vに置き換えたとき，

T

に許容分割が存在す るとする．このとき

0 ≤ r

≤ r

なる任意の実数

r

に 対して，全ての需要量

d

_vを

d

_v

= r

· d

_vに置き換えた とき，

T

に許容分割が存在する．

したがって，アルゴリズム

Partition

^{を用い，二分} 探索で

r

^∗が計算できる．しかし，全ての非負実数集 合上の二分探索で，最大供給率

r

^∗を計算しようとす ると，

r

^∗は正確に求まらないか，あるいは多項式時間 で計算が終了しない．提案手法のアイディアは，

r

^∗が 有理数であることに注意することである．

補題

2. T = (V, E)

は定常木ネットワークであると

し，

S =

v∈Vs

s

_v，

D =

v∈Vd

d

_v，

C =

e∈E

c

_e とすると，

T

の最大供給率

r

^∗は

r

^∗

∈ { C · S/z | z

は整数であり，

C · D · S ≥ z ≥ 0 }

である．

証明

r

^∗ は

T

の 最 大 供 給 率 で あ る と す る ．こ の と き点集合

V

は部分集合

V

1

, V

2

, · · · , V

_ns に分割でき，

1 ≤ i ≤ n

_s なる各

i

について

V

_iは木

T

の部分木

T

_i を 誘 導 し ，

V

_i に は 丁 度 一 つ の 供 給 点

u

が あ り，

v∈V_i/{u}

r

^∗

· d

_v

≤ s

_uであり，部分木

T

_iの各辺

e

に対して

ψ

_e

≤ c

_e である．

r

^∗は最大供給率なので，

1 ≤ i ≤ n

sなるある

i

について次の条件

(i)

あるいは

(ii)

が成立する．

(i)

不等式

v∈V_i/{u}

r

^∗

· d

_v

≤ s

_uが等号で成立する．

すなわち

v∈V_i/{u}

r

^∗

· d

_v

= s

_uである．

(ii) T

_iのある辺

e

= (v, w)

について，不等式

ψ

_e

≤ c

_e が等号で成立する．すなわち

ψ

_e

= c

_eである．こ こで

ψ

_e

=

x∈Des(w)

r

^∗

· d

_xである．

なぜならば，どの

i

についても条件

(i)

も

(ii)

も成立 しないとすると，

r

^∗は最大供給率ではないことになっ てしまうからである．

z

^∗を

z

^∗

= C · S/r

^∗とおく．条件

(i)

が成立する とき

z

^∗

=

e∈E

c

_e

·

⎛

⎝

v∈Vi/{u}

d

_v

⎞

⎠ ·

^v∈Vs

s

_v

s

_u

であり，

z

^∗は整数であり，

0 ≤ z

^∗

≤ C · D · S

である．

条件

(ii)

が成立するとき

z

^∗

=

^e∈E

c

_e

c

_e

·

⎛

⎝

x∈Des(w)

d

_x

⎞

⎠ ·

v∈Vs

s

_v

であり，

z

^∗は整数であり，

0 ≤ z

^∗

≤ C · D · S

である．

このように，どちらの場合にも，

0 ≤ z ≤ C · D · S

な るある整数

z

に対し，

r

^∗

= C · S/z

である．

2

有理数の集合

{C · S/z | C · D · S ≥ z ≥ 0}

の要素 数は

C · D · S + 1

である．（辺容量がない場合の集合 の要素数は

D · S + 1

であった

[4]

．）辺容量付きの定 常木ネットワーク

T = (V, E)

の最大供給率

r

^∗は，こ の有限集合上の二分探索と線形時間判定アルゴリズム

Partition

を用いて，

O(n log

₂

(C · D · S))

時間で計 算することができる．辺容量付き定常木ネットワーク

T

の対数サイズ

L

は，

L =

e∈E

log

₂

(c

_e

+ 2) +

v∈Vd

log

₂

(d

_v

+ 2)

+

v∈Vs

log

2

(s

_v

+ 2)

であるので，明らかに，

log

₂

(C · D · S) ≤ L

であり，

次の定理を得る．

定理

1 T

は辺容量付きの定常木ネットワークとし，

n

を

T

の点数とし，

L

を

T

の対数サイズとすると，

T

に対する最大供給率問題は

O(nL)

時間で解くことが できる．

3.

パラメトリック木ネットワークの分割 問題

この節では，辺容量付きのパラメトリック木ネット ワーク

T

に対する分割問題を解くアルゴリズムを与 える．

3. 1

定 義

一般性を失わずに，与えられた木

T

は任意に選んだ 点

v

rootを根とする根付き木であるとしてよい．更に，

T

の各点

v

の供給量

s

_v

(λ)

，需要量

d

_v

(λ)

及び各辺

e

の容量

c

_e

(λ)

は，非負実数の変数

λ( ≥ 0)

の関数であ るとする．また，

T

には供給点が

n

s個あるとする．

根付き木ネットワーク

T = (V, E)

の変数値

λ

に対 する許容分割

π

_λ

= (V

1

, V

2

, · · · , V

_ns

)

は，

V

の

n

s個 の部分集合

V

1

, V

2

, · · · , V

_nsへの分割であり，次の条件

(a)

−

(c)

を満足するものである．

(a) T

の根

v

rootは

V

1に含まれる．すなわち

v

root

∈ V

1

である．

(b) 1 ≤ i ≤ n

sなる各添字

i

について，

V

_iは丁度一つ の供給点

u

を含み，

V

_iは

T

の部分木

T

_iを誘導し，

v∈V_i/{u}

d

_v

(λ) ≤ s

_u

(λ)

である．

(c)

各部分木

T

_iの各辺

e

を流れるフローの値

ψ

_e

(λ)

は

ψ

_e

(λ) ≤ c

_e

(λ)

である．

パラメトリック木ネットワーク

T

の分割問題とは，

T

が許容分割をもつ変数値

λ

の全てを見つける問題で ある．そのような変数値

λ

の集合は幾つかの実数区間 からなるので，実際にはそのような全ての区間からな る集合を見つける．

図

2(a)

のパラメトリック木ネットワーク

T

では，

v

5

= v

rootであり，

s

_v1

(λ) = 8, s

_v2

(λ) = 7, d

_v5

(λ) = 2

であり，辺

(v

1

, v

3

)

，

(v

2

, v

4

)

，

(v

4

, v

5

)

の容量は定数 であり，それぞれ

11

，

7

，

10

である．変動する需要 量

d

_v3

(λ)

，

d

_v4

(λ)

及び辺

e = (v

3

, v

5

)

の容量

c

_e

(λ)

は 図

2(b)

に描かれている．図

2(a)

で点線で示した分割

π

_λ

= ( { v

1

, v

3

} , { v

2

, v

4

, v

5

} )

は，

0 ≤ λ ≤ 5

なる

λ

に 対する

T

の許容分割である．

T

に対する分割問題の解 は

[0,7]

と

[10,∞)

の二つの区間からなる集合である．

値

λ

に 対 す る

T

の 許 容 分 割 を

π

_λ

= (V

1

, V

2

, · · · , V

_ns

)

とする．

1 ≤ i ≤ n

_s なる各

i

に ついて

V

_iには丁度一つの供給点が含まれている．

u

を

V

1に含まれる供給点としたとき，許容分割

π

_λの余裕

surp(π

_λ

)

を

surp(π

_λ

) = s

_u

(λ) −

v∈V1/{u}

d

v

(λ)

と定義する．パラメトリック木

T

の余裕

f

_T

(λ)

を

f

_T

(λ) = max

π_λ

surp(π

_λ

)

と定義する．ただし，値

λ

に対する

T

の全ての許容 分割

π

_λにわたって

surp(π

_λ

)

の最大値をとるものと する．値

λ

に対して

T

が許容分割をもたないならば，

f

_T

(λ) = −∞

とする．直感的には，辺容量条件を満足

させながら

T

の全ての需要点に電力を供給したとき，

根

v

root

∈ V

1から

T

の外へ出力できる電力量の最大 値が，

T

の余裕

f

_T

(λ)

である．（図

2(a)

の

T

に対する

f

_T

(λ)

を図

2(c)

に示す．）

f

_T

(λ) ≥ 0

なる

λ

の区間全 てからなる集合が分割問題の解である．

根付き木

T

に基づく動的計画法を用いて

T

の許容 分割を見つける．より詳しくは，許容分割とその拡張 である

“

根許容分割

”

を小さい部分木から大きい部分

図2 (a)v5を根とする辺容量付きパラメトリック木ネッ トワークT，(b)変動する需要量d_v3(λ)，d_v4(λ) 及び辺容量c_e(λ)，(c)Tの余裕f_T(λ)，(d)T の 不足g_T(λ)

Fig. 2 (a) Parametric tree networkT rooted atv5, (b) variable demandsd_v3(λ),d_v4(λ) and ca- pacityc_e(λ), (c) surplusf_T(λ), and (d) deficit g_T(λ) ofT.

図3 木T にダミーの供給点と辺を付加して得られる木 Tdum

Fig. 3 Tree Tdum obtained from T by adding a dummy supply vertex and a dummy edge.

木へと繰り返し求めていく．

図

3

のように，木

T

の根

v

rootの新しい子として ダミーの供給点

u

dumを付け加え，その供給量を

∞

とし，

u

dumと

v

rootをダミーの辺で結び，その辺の 容量を

∞

とする．こうして得られた木を

T

dumとす る．

T

dumには供給点が

n

s

+ 1

個ある．

T

dumの許容 分割

π

_λ

= (V

1

, V

2

, · · · , V

_ns+1

)

で，

v

root

, u

dum

∈ V

1

なる

π

_λを，

T

の根許容分割と呼ぶ．したがって，

T

に根許容分割があるならば，

v

rootは需要点である．ま た，

v

rootが供給点ならば，

T

は根許容分割をもたな い．（図

2(a)

の木

T

に対して，

π

_λ

= ({v

root

, u

dum

}

，

{ v

1

, v

3

}

^，

{ v

2

, v

4

} )

は

0 ≤ λ ≤ 7

なる

λ

に対する根許 容分割である．）

根 許 容 分 割

π

_λ

= (V

1

, V

2

, · · · , V

_ns+1

)

の 不 足

def(π

_λ

)

を

def(π

_λ

) =

v∈V1/{u_dum}

d

_v

(λ)

と定義する．パラメトリック木

T

の不足

g

_T

(λ)

を

g

_T

(λ) = min

πλ

def(π

_λ

)

と定義する．ただし，値

λ

に対する

T

の全ての根許容 分割

π

_λにわたって

def(π

_λ

)

の最小値をとるものとす る．値

λ

に対して

T

が根許容分割をもたないならば，

g

_T

(λ) = + ∞

とする．このようにして，

v

rootが供給 点であるとき，任意の値

λ

に対して

T

は根許容分割 をもたないので，

g

_T

(λ) = + ∞

^{である．直感的には，}

v

rootを含む幾つかの需要点が木

T

の外から電力を供

図4 根付き部分木 Fig. 4 Rooted subtrees.

給されるときに

v

rootを通して

T

に入力されなければ ならない電力量の最小値が，

T

の不足

g

_T

(λ)

である．

（図

2(a)

の

T

に対する不足

g

_T

(λ)

を図

2(d)

に示す．）

T

の根付き部分木

T

に対しても余裕

f

_T

(λ)

と不足

g

_T

(λ)

を同様に定義する．

T

の点

v

を根とする

T

の最大部分木を

T

_vと表す．

点

v

の子を

v

1

, v

2

, · · · , v

_lとし，

1 ≤ i ≤ l

なる各

i

に 対し，

v

と

v

_iを結ぶ辺を

e

_iとし，

v

_iを根とする

T

の 最大部分木を

T

_vi とする．点

v

と，辺

e

1

, e

2

, · · · , e

_i と，部分木

T

_v1

, T

_v2

, · · · , T

_viからなる

T

_vの部分木を

T

_vⁱと書く．図

4

で

T

_vと

T

_vⁱは点線で囲まれている．

明らかに

T

_v

= T

_v^lである．点

v

だけからなる部分木 を特に

T

_v⁰と書く．

3. 2

アルゴリズム

以下の

(i)

−

(iii)

で示すように，本文のアルゴリズ ムは動的計画法を用いて，

T

の各点

v

に対し，葉から 根に向かって，

T

_vの余裕

f

_Tv

(λ)

と不足

g

_Tv

(λ)

を計 算する．

T = T

_vrootの余裕

f

_T

(λ)

から，

f

_T

(λ) ≥ 0

で あるような非負実数

λ

の区間全てを容易に見つけるこ とができる．パラメトリック木ネットワークの分割問 題の解として，これら全ての区間からなる集合を出力 する．例えば図

2(a)

のパラメトリック木

T

に対して は，集合

{ [0,7],[10, ∞ ) }

^{を出力する．}

(i)

まず次のように，

T

の各点

v

に対して

T

_v⁰の余裕 と不足を計算する．

T

_v⁰は点

v

だけからなる．

v

が供給 点ならば，全ての

λ

に対して

f

_T0

v

(λ) = s

_v

(λ)

であり，

g

_T0

v

(λ) = + ∞

^である．

v

が需要点ならば，全ての

λ

に対して

f

_Tv0

(λ) = −∞

であり，

g

_Tv0

(λ) = d

_v

(λ)

で ある．

T

の全ての葉

v

に対して

T

_v

= T

_v⁰なので，こ のようにして葉

v

に対する

f

_Tvと

g

_Tv は計算できる．

(ii)

^次に

T

の各内点

v

に対して，部分木

T

_vⁱ

(1 ≤

i ≤ l)

の余裕と不足を，

T

_vⁱの部分木

T

_vⁱ⁻¹と

T

_viの余 裕と不足から計算する．ここで

l

は点

v

の子の個数で あり，

T

_v

= T

_v^lである．図

5

のように，

T

_vⁱ⁻¹の根

v

図5 T_vⁱの許容分割π_λ． Fig. 5 Feasible partitionsπ_λofT_vⁱ.

と

T

_vi の根

v

_iを辺

e = (v, v

_i

)

で結んで

T

_vⁱから得ら れる．

(ii-1)

まず，

T

_vⁱの余裕

f

_Ti

v の計算法を説明する．

n

_i を

T

_vⁱの供給点の個数とする．

f

_Tvi

(λ) = −∞

^とする．

すなわち値

λ

に対して

T

_vⁱは許容分割をもつとする．

f

_Ti

v

(λ) = surp(π

_λ

)

であるような

T

_vⁱの許容分割を

π

_λ

= (V

1

, V

2

, · · · , V

_ni

)

とする．このとき図

5

のよう に，

V

1は

T

_vⁱの根

v

を含んでいる．同図で

π

_λは点線 で示され，供給点は正方形で表されている．次の三つ の場合がある．

場合

(a)

：

v

_i

∈ / V

1であるとき．

この場合

f

_Tvi

(λ) ≥ 0

であり，

T

_vⁱの許容分割

π

_λは

T

_vⁱ⁻¹と

T

_viの許容分割を誘導する．すなわち

T

_vⁱの点 集合の分割

π

_λを，

T

_vⁱ⁻¹の点集合及び

T

_vi の点集合 へそれぞれ（数学的意味で）

“

制約

”

したものは，

T

_vⁱ⁻¹ と

T

_viの許容分割である．（図

5(a)

を参照．）この場合 に対して

f

_Ti−1

v と

f

_Tvi から次の関数

f

_T^a_i

vを計算する．

f

_T^ai v

(λ) =

⎧ ⎨

⎩ f

_Ti−1

v

(λ) (f

_Tvi

(λ) ≥ 0

のとき

)

−∞ (

それ以外のとき

)

辺

e = (v, v

_i

)

にはフローが流れていなく，

ψ

_e

(λ) = 0

である．

場合

(b)

^：

v

_i

∈ V

1であり，

V

1の供給点

u

が

T

_vⁱ⁻¹に 入っているとき．

こ の と き ，

f

_Ti−1

v

(λ) ≥ g

_Tvi

(λ)

か つ

ψ

_e

(λ) =

g

_Tvi

(λ) ≤ c

_e

(λ)

であり，

v

_iは需要点である．

π

_λは

T

_vⁱ⁻¹の許容分割と

T

_vi の根許容分割を誘導する．（図

5(b)

で辺

e = (v, v

_i

)

に付けられた矢印は

e

を流れる フローの向きを表している．）この場合に対して次の関 数

f

_T^b_i

vを計算する．

f

_T^bi v

(λ) =

⎧ ⎪

⎪ ⎪

⎪ ⎪

⎪ ⎨

⎪ ⎪

⎪ ⎪

⎪ ⎪

⎩ f

_Ti−1

v

(λ) − g

_Tvi

(λ)

(f

_Tvi−1

(λ) ≥ g

_Tvi

(λ)

かつ

g

_Tvi

(λ) ≤ c

_e

(λ)

のとき

)

−∞ (

それ以外のとき

)

場合

(c)

^：

v

_i

∈ V

1であり，

V

1の供給点

u

が

T

_viに 入っているとき．

こ の と き ，

g

_Ti−1

v

(λ) ≤ f

_Tvi

(λ)

か つ

ψ

_e

(λ) = g

_Ti−1

v

(λ) ≤ c

_e

(λ)

であり，

v

は需要点である．

π

_λは

T

_vⁱ⁻¹の根許容分割と

T

_vi の許容分割を誘導する．（図

5(c)

を参照．）この場合に対して次の関数

f

_T^c_i

v を計算

する．

f

_T^ci v

(λ) =

⎧ ⎪

⎪ ⎪

⎪ ⎪

⎪ ⎨

⎪ ⎪

⎪ ⎪

⎪ ⎪

⎩

− g

_Ti−1

v

(λ) + f

_Tvi

(λ) (g

_Ti−1

v

(λ) ≤ f

_Tvi

(λ)

かつ

g

_Ti−1

v

(λ) ≤ c

_e

(λ)

のとき

)

−∞ (

それ以外のとき

)

上の三つの関数

f

_T^a_i

v

(λ), f

_T^b_i

v

(λ), f

_T^c_i

v

(λ)

から，

f

_Ti v

(λ)

は次のように計算できる．

f

_Tvi

(λ) = max { f

_T^ai v

(λ), f

_T^bi

v

(λ), f

_T^ci v

(λ) } . (ii-2)

次 に

T

_vⁱ の 不 足

g

_Ti

v の 計 算 法 を 説 明 す る ．

g

_Ti

v

(λ) = +∞

とする．すなわち値

λ

に対して

T

_vⁱ は根許容分割をもつとする．

T

_vⁱにある供給点の個数を

n

_iとする．

T

_vⁱにダミーの供給点

u

dumを付け加えると，

供給点の総数は

n

_i

+ 1

になる．

g

_Ti

v

(λ) = def(π

_λ

)

であ るような

T

_vⁱの根許容分割を

π

_λ

= (V

1

, V

2

, · · · , V

_ni+1

)

とする．このとき図

6

のように

V

1は

u

dumと

T

_vⁱの根

v

を含む．次の二つの場合がある．

場合

(a)

^：

v

_i

∈ / V

1であるとき．

この場合，

v

は需要点であり，

f

_Tvi

(λ) ≥ 0

でなけ ればならず，

π

_λは

T

_vⁱ⁻¹の根許容分割と，

T

_viの許容 分割を誘導する．（図

6(a)

参照．）この場合に対して次 の関数

g

^a_Ti

v を計算する．

g

_T^avi

(λ) =

⎧ ⎨

⎩ g

_Ti−1

v

(λ) (f

_Tvi

(λ) ≥ 0

のとき

)

+ ∞ (

それ以外のとき

)

図6 T_vⁱの根許容分割π_λ Fig. 6 Root-feasible partitionsπ_λofT_vⁱ.

辺

e = (v, v

_i

)

にフローは流れていない．

場合

(b)

^：

v

_i

∈ V

1であるとき．

この場合，

v

及び

v

_iは需要点であり，

g

_Tvi

(λ) = + ∞

でなければならず，

ψ

_e

(λ) = g

_Tvi

(λ) ≤ c

_e

(λ)

であり，

π

_λは

T

_vⁱ⁻¹及び

T

_viの根許容分割を誘導する．（図

6(b)

参照．）この場合に対して次の関数

g

_T^bi

v を計算する．

g

_T^bi v

(λ) =

⎧ ⎪

⎪ ⎪

⎨

⎪ ⎪

⎪ ⎩ g

_Ti−1

v

(λ) + g

_Tvi

(λ)

(g

_Tvi

(λ) ≤ c

_e

(λ)

のとき

) +∞ (

それ以外のとき

)

上の二つの関数

g

_T^ai

v

, g

^b_Ti

v から

g

_Ti

v は次のように計 算できる．

g

_Tvi

(λ) = min{g

^a_Tvi

(λ), g

^b_Tvi

(λ)}.

(iii) T

に含まれる

n − 1

本の辺

e = (v, v

_i

)

の各々 に対して

(ii)

の計算を繰り返して

f

_T

(λ)

と

g

_T

(λ)

を 計算する．

3. 3

計 算 時 間

この節では全ての供給量，需要量及び辺容量が非負 実数変数

λ

の区分的線形関数であるとして，アルゴリ ズムの計算時間を解析する．

区分的線形関数

f

の折れ点とは，

f

を表す折れ線の 傾きが変わる

λ

の値と定義する．関数

f

の折れ点の 個数を

p(f )

と表す．便宜上

λ = 0

は

f

の折れ点であ るとする．（例えば図

2

の

c

_e

(λ)

と

f

_T

(λ)

については，

p(c

_e

(λ)) = 3

であり，

p(f

_T

(λ)) = 5

である．）このと きパラメトリック木ネットワーク

T = (V, E)

のサイ ズ

N

は

N =

v∈Vs

p(s

_v

(λ)) +

v∈Vd

p(d

_v

(λ)) +

e∈E

p(c

_e

(λ))

である．

P

を次式で定義する．

P = max{max

T

p(f

_T

(λ)), max

T

p(g

_T

(λ))}.

ただし，

T

の全ての根付き部分木

T

に渡り最大値をと るものとする．

f

_T

(λ)

と

g

_T

(λ)

が区分的線形関数で あることに注意しよう．

T

の余裕

f

_T

(λ)

と不足

g

_T

(λ)

を解として出力する必要があるならば，そのサイズは

P

であることが多いので，そのときは

P

が出力サイ ズである．

点

v

だけからなる木

T

_v⁰の余裕

f

_T0

v

(λ)

と不足

g

_T0 v

(λ)

は

3.2

の

(i)

のようにして求まる．明らかに

T

の全て の点

v ∈ V

に対する

f

_T0

v

(λ)

と

g

_T0

v

(λ)

は

O(N )

時間 で求まる．

木

T

_vⁱの余裕

f

_Tvi と不足

g

_Tvi は，

3.2

^の

(ii)

のよう にして木

T

_vⁱ⁻¹と

T

_vi の余裕と不足及び辺

e = (v, v

_i

)

の容量

c

_e

(λ)

から

O(p(c

_e

(λ)) + P )

時間で計算できる．

T

には

n −1

本の辺があるので，

(ii)

の計算は

n −1

回 実行される．また

e∈E

p(c

_e

(λ)) ≤ N

である．した がって木

T

の余裕

f

_T

(λ)

と不足

g

_T

(λ)

は

O(N + nP )

時間で計算できる．

f

_T

(λ) ≥ 0

なる

λ

の区間全ては，

f

_T

(λ)

から

O(P )

時間で求まる．このように分割問題 は

O(N + nP )

時間で解くことができる．

P

は

N

よりも大きいかもしれない．（例えば，図

2

に お い て

f

_T

(λ)

の 折 れ 点

λ = 2.5, λ = 5

及 び

λ = 7

は，どの供給量，需要量，辺容量の折れ点 でもない．）しかし，

P

は

N

の多項式以下であること が多い．特に，

T = (V, E)

が定常ネットワークなら ば，

N = | V | + | E | = 2n − 1, P = 1

であり，本文の アルゴリズムの計算時間は

O(n)

である．もし全ての 供給量，需要量，辺容量が階段関数ならば

P ≤ N

で あり，計算時間は

O(nN )

である．

3. 4 P

の 上 界

供給量，需要量及び辺容量の折れ点は重複している かもしれない．重複を除いた折れ点の総数を

B

とし，

これらの折れ点を

p

1

, p

2

, · · · , p

_Bとする．無論

B ≤ N

である．（例えば，図

2(a)

の

T

に対して

B = 5

であ り，図

2(b)

において折れ点は黒点で描かれている．）

0 = p

1

< p

2

< · · · < p

_Bとし，

p

_B+1

= ∞

^であると する．次の

(a)

−

(c)

を仮定する．

(a) v

が供給点であり，

p

_i

< λ < p

_i+1

, 1 ≤ i ≤ B

な らば，ある整数

a

_vi

, b

_viに対して

s

_v

(λ) = a

_vi

λ + b

_vi

である．

(b) v

が需要点であり，

p

_i

< λ < p

_i+1

, 1 ≤ i ≤ B

な