【グラフ理論とネットワーク理論】線形構成法

線形構成法 Linear Design Method

直径最小化問題 Minimizing Diameter Problem

(n, d) グラフとは、接点数n, 各接点は出枝、入枝をそれぞれd本ずつもっているグラフのこと。このグラフの事をd正則有向グフラと呼ぶ。 また、経路の長さは、経路中の枝の数で決まる。そして、距離δ(i, j)はiからjへの最短経路の長さと定義する。

グラフの直径とは、グラフ内における２接点間距離の最大値。

(n, d)グラフの直径最小化問題を解きたい。

直径１以下の(5, 2)グラフは存在しない。

→ このグラフが(5, 2)グラフ最小化問題の解の１つ。

(n, d)グラフの直径の下界値

1 + d + d² + d³ + … + d^k = (d^{k+ 1} - 1)/(d - 1)

距離がｋ以下の接点数を最大化。

直径の下界値をｍとすると

(d^m - 1) / (d - 1) >= n

↓

m >= 「log_d {n(d - 1) + 1}」 - 1 => l(n, d)

「x」= Smallest integer >= x

「log_d n」 - 1 <= l(n, d) <= 「log_d n」 (3.1)

線形構成法 Linear Design Method

定義 枝(i, j)とした時に、jは次式で計算される。

j ≡ (a*i + b) * d + α (mod n) , α = 0, 1, 2, 3, ,,,d - 1 (3.2)

a, b:　整数

定理１
式(3.2)が(n, d)グラフを構成するのは、a*dとnの最大公約数がｄの約数のときである。

例

n = 6, d = 2, a = b = 1 => (n, d)グラフを構成できる

i = 0の時
j = (1 * 0 + 1) * 2 + 0 ≡ 2 (mod 6)
= (1 * 0 + 1) * 2 + 1 ≡ 3 (mod 6)
i = 1の時, j = 4, 5
i = 2の時, j = 0, 1
i = 3の時, j = 2, 3
i = 4の時, j = 4, 5
i = 5の時, j = 0, 1

これらのiとjは、iからjに枝が伸びている事を表す。

有向線形構成法 Effective Linear Design Method

定義

1 = ± 1 の場合の線形構成法

定理２
有向線形構成された(n, d)グラフの直径は、「log_d n」を超えない。

定理２と式(3.1)より有向形成された(n, d)グラフの直径は最適解と等しいか１大きい。