数理解析研究所講究録
第 833 巻 1993 年 91-97

91
1993 年冬の $LA$ シンポジウム

グラフ節点のある種の線形配列問題について
山本和英 (YAMAMOTO Kazuhide)*yamamoto@toki.tutkie.tut.ac.jp

増山繁 (MASUYAMA Shigeru)*

masuyama@tutkie.tut.ac.jp

内藤昭三 (NAITO Shozo)**

naitoOatom.ntt.jp* 豊橋技術科学大学知識情報工学系$**NTT$ 基礎研究所

1線形配列問題
本稿では無向グラフの節点の線形配列問題を取り扱う。線形配列問題とは以下のような問題である。
無向グラフ $G=(V, E)$、$V$: 節点の集合、$E$

枝の集合として、 $k<|V|$および $K$ を自然数とする。 節点間のうち $kf$ 所を選んだ時、 そこを横切る枝数が $K$ 以下となる 1 対 1 写像 $f$ : $Varrow\{1,2, \ldots, |V|\}$ が存在するか ?

$\blacksquare$

ただし、 ここで節点間を横切る枝の数え方には、 2 通りの定義が考えられる。 すなわち、(a) 隣合った 2 節点

$i,$$i+1$ 間を結ぶ枝のみ考える場合(b) 隣合った 2 節点

$i,$$i+1$ 間を横切る (端点が $i,$ $i+1$る場合とは限らない) すべての枝を考え921993 年冬の $LA$ シンポジウムである。 しかし、 (b) の間接の枝も考慮した線形配列問題は、 以下に示す Optimal Lin-ear Arrangement 問題と同値の問題であり、 $NP$ 完全である。
Optimal Linear Arrangement[l]INSTANCE: Graph $G=(V, E)$ , positive integer $K$ .
QUESTION: Is there a one-to-one function : $Varrow\{1,2, \ldots, |V|\}$such that $\sum u,v\in E|f(u)-f(v)|\leq K$ ?
$f$

なぜならば、 Optimal Linear Arrangement 問題は、 「グラフの節点を x 軸上、1, 2, ..., $|V|$ に一列に並べた時、 その配置での枝の距離の総和の最小となる配置を求めよ」 という問題である (決定問題としては、 その配置での枝の距離の総和が $K$ 以下となる配置が存在するかどうか決定せよ、 となる)。 ところが、 ある配置で長さが となる枝は、 その配置で隣接する節点を回横切るので、 この二つの問題は同値である。
そこで、 以下では隣合った 2 節点を結ぶ枝のみ考慮する場合 (a) の検討を行なう。 また、 枝の重みはすべて一定と仮定する。
$d$

$d$

2

節点順序固定の場合
この問題は、 節点の順序を固定すると、 節点問を横切る枝の数え方の定義法とは無関

係に、 次のように容易に解くことができる。
$|V|-1$ 個ある 2 節点問を、 横切る辺数の少ない順にソートする。 そして、 少ない方から $k-1$ 個選ぶことで解ける。 これは、 $n=|V|$ とすると $O(n\log n)$ 時間でできる。

なお、 $k=1$、つまり段落数 2 に対応する場合には、 横切る枝のところだけ求めれば良いから、 $|V|-1$ 回の比較で解ける。

3

節点順序自由の場合一般性を失うことなく、 以降の議論はすべて $k=|V|-1$ として進める。

3.1

木の場合

[補題 1] 無向グラフが木である場合、 隣接枝のみを考慮した線形配列問題の最小コスト
は、 木の直径が 1 または 2 の場合は(証明) 直径が$1$、その他の場合には$0$である。の場合の最小コストが直径が 1 の場合の最小コストが 1 であることは明らかである。 直径が 2(star) の場合は、 中心を列の端点に置いた場合に最小コストが 1 となる。
$0$$0$、直径が 3 の場合は、 直径を構成する節点を端点から順に $a,$とすると、$a,$ $d,$の順に配列すれば (図 2) 隣接枝を持たず、 そのコストは である。 直径が 3 の木は、 こ$b,$ $c,$ $d$$0$$c,$$b$

931993 年冬の $LA$ シンポジウムの 4 節点に または からの枝を加えたものなので、側に配列すれば、 最小コストは である。
$b$からの枝は$b$$c$$c$

側に、$c$からの枝は$0$$b$V
図 1: 直径 3 の木a$c$$d$$b$$v$

図 2: 図 1 の線形配列

直径が 4 以上の場合は、 木の直径の大きさに関する帰納法によって証明を行なう。 直径が $p(p\geq 3)$ のときの最小コストをと仮定する。直径を構成する端点 (前述の例では$b,c)$ から枝を付け加える時、 最低でも $p+2$ 通りの場合が考えられる ( $p=3$ の時は 5 通通りのいずれかに枝を付加すれば、 コスり) が、 このうち、 その端点の両側を除いたトは になる。
以上により、 直径 $p\geq 3$ のときのを最小コストは である。
$0$

$p$

$0$

$0$

3.2

$\blacksquare$

閉路、 二部グラフ、 完全グラフの場合無向グラフが閉路である時には、 グラフの節点を図することによって、 最小コストにすることができる。

[定理 1] 無向グラフがつまり節点数の時に形配列問題の最小コストは、$C_{k^{\text{、}}}$$C_{3}$$2$

、

$k$

$3$、

あるいは、 図 4 のように配列の閉路である時、 隣接枝のみを考慮した線$C_{4}$の時に$1$、$C_{5}$以上の時$0$になる。

$\blacksquare$

94
1993 年冬の $LA$ シンポジウム

a

図 3:

a$d$

$b$

$c$

$C_{4}$の線形配列$b$$e$$c$

図 4:$C_{5}$$d$の線形配列

無向グラフが二部グラフである時には、 グラフの節点を図 5 のように配置することによって、 以下の定理を示すことができる。

[定理 2] 無向グラフが二部グラフである時、 隣接枝のみを考慮した線形配列問題の最小コストは$0$または 1 になる。

$\blacksquare$

ここで、 二部グラフが完全二部グラフ $K_{m,n}$ であるときに最小コストが 1 になり、 その他の二部グラフでは最小コストはala2

am$0$になる。

blb2bn

図 5: 二部グラフの線形配列

無向グラフが完全グラフである場合には、 すべての節点間に枝が結ばれているという完全グラフの性質を考慮すれば、 容易に次の定理を示すことができる。

95
1993 年冬の[定理 3] 無向グラフが$K_{n^{\text{、}}}$$LA$

シンポジウム

つまり節点数 $n$ の完全グラフの場合、 隣接枝のみを考慮した線形配列問題の最小コストは $n-1$ になる。

a$b$$\blacksquare$

$d$

$c$

$f$

$e$

図 6: 完全グラフの線形配列

3.3

平面グラフの場合
ここでは、 平面グラフに対する、 隣接枝のみを考慮した線形配列問題を考える。 以下の議論で個の節点が独立」 とはことを意味する。
$\text{「_{}p}$$\text{「_{}p}$個の節点はどの 2 節点問とも枝が結ばれていない」[定理 4] 無向グラフが平面グラフである時、 隣接枝のみを考慮した線形配列問題の最小コストは 3 以下になる。

$\blacksquare$(証明) 平面グラフ $G=(V, E)$ $V$ : 節点の集合、 $E$ . 枝の集合に対し、 補グラフを考える。すると線形配列問題は、 蔭の節点を一列に並べた時、 隣合う節点が結ばれていない場所の数の最小はいくつか」 となる。平面グラフ $K_{4}=W_{3}$ では、 そのコストは 3 であることから、 コスト 3 の場合が存在することがわかる。
ここでは $G$ の節点数に関する帰納法を用いる。 $G$ の任意の節点及び \iota こ隣接するすべての枝を取り除いて得られたグラフを $G-\{v\}$ とすると、 節点数 $n\leq 4$ のとき、$G-\{v\}$ の最小コストが 3 であると仮定する。 するとグラフ $G-\{v\}$ は図 7 に示すように、 $a’-b$ $b’-c$ $c’-d$ の 3 ケ所に枝のない部分 (以下すきまと呼ぶ) が存在する (なととまたはととお、が一致している場合、 つまり単一節点の場合であっても以下の議論と同様である)。
平面グラフの仮定から、 節点 と、 節点の 5 節点は独立な節点とはならず、の 4 節点間 (例えば節点このうちどこかに枝が 1 本以上存在する。 このうち、 $a,$$a-b$ 間) に枝が存在すると、 図 8 に示すように線形配列を移動することによって、 すきまを減らすことができ、 最小コストが 3 であるという仮定に反する。
このことから、 節点 は、 節点のいずれかと枝が 1 本以上結ばれている。例
えば節点 と節点 間に枝が結ばれているとすると、 節点 を節点 の隣に配置した線形配列にすることによって、 すきまの増加を抑えることができる。

$\overline{G}$、

$v$、

$a$、

$a’$

$b’$$b$、、$c’$

$c$

$d’$

$d$、$a,$ $b,$ $c,$$v$$d$$b,$ $c,$ $d$

$v$

$v$

$a$$a,$ $b,$ $c,$

$d$

$v$

$a$

$v$

96
1993 年冬の $LA$ シンポジウム

図 7: 平面グラフの線形配列

a$a’$

$b$

$b’$

$c$

$c’$

$d$$d’$

図 8: 移動した線形配列
よって、 最小コストが 3 であれば、 グラフ $G-\{v\}$ に節点増加にはならない。 なお、 最小コストが 3 未満であれば節点が 3 以下になるのは明らかである。

$v$を追加してもコストのを追加しても最小コスト$v$

ここでは、 与えられたグラフが二重連結グラフとして以上の証明を行なった。 グラフが葉を含む場合、 及びグラフがブリッジを含む場合には、 これまでの議論を利用して容易にコスト 3 以下であることを示せる。
$\blacksquare$3.4

一般のグラフの場合

既知の $NP$ 完全問題として、 Hamiltonian path 問題 [1] をとる。 Hamiltonian
path の問題例であるグラフ $G$ に対し、 その補グラフ ー G を考える。

[補題 2] 無向グラフ $G$ がハミルトン経路を持つことと、 無向グラフてのコストが$0$$\overline{G}$の線形配列としであることは、 同値である。

(証明) 無向グラフ $G$ がハミルトン経路を持てば、 節点をハミルトン経路に沿って一列ににコストの隣接する節点間には枝がないようにできる。 一方、並べることによってはハミルとすると、 $G$ での線形配列があれば、 その節点列を$\overline{G}$$\overline{G}$$0$$v_{1},v_{2},\ldots,v_{n}$$v_{1},v_{2},\ldots,v_{n}$トン経路になる。

$\blacksquare$

補題 2 より、 次の定理を容易に示すことができる。

[定理 5] 一般の無向グラフに対する線形配列問題は $NP$ 完全である。

$\blacksquare$

97
1993 年冬の $LA$ シンポジウム

枝に重みのある場合 (今後の課題)

4

本稿では枝の重みをすべて 1 と考えて議論を進めてきたっ 枝に重みがあった場合、 以下のことは、 本稿の議論から容易に示すことができる。
$\bullet$

木の場合には、 直径が 1 または 2 の時には最小重みの枝のコスト、 その他の時には$0$$\bullet$。

閉路の場合、$C_{4}$$\bullet$$C_{3}$の時には (すべての枝の重みの合計一最大重みの枝のコスト)、の時には最小重みの枝のコスト、二部グラフの場合、 完全二部グラフの時には$C_{5}$

以上の時には$K_{??\iota,n}$$0_{0}$の時には最小重みの枝のコスト、 その他$0_{0}$

また、 完全グラフの場合、 線形配列問題は Traveling Salesman 問題 [1] となり、$NP$ 完全となる。

今後は、 平面グラフで枝に重みがある場合の検討をしていきたい。

参考文献[1] Garey, M. R. and Johnson, D. S.: Computers and Intractability: A Guide to theTheory of NP-Completeness, W. H. Freeman and Co. (1979).