修士論文審査 論文要約

強連結有向グラフ上の整合円順列
松田 拓朗
指導教員: 岩田 覚 助教授

2006 年 2 月 8 日

1 要旨

length(a) :=length([u, v]) とする．
円順列から n 通りの線形順序を得ることができる．線形

強連結有向グラフの頂点はグラフの安定数以下の閉路で順序は前向き枝(vi vj , i < j) と後ろ向き枝(vj vi , i < j) を覆うことが出来るという Gallai (1964) の予想が，Bessy–持つ．ある円順列と有向グラフが与えられたとき，G の閉Thomassé (2004) によって肯定的に解決された．彼らは，

路 C のその円順列に対し，整合円順列という概念を提案し，円順列が整合的であるとP

きに成り立つ最大最小定理の系として Gallai の予想を証ind(C) :=明した．Sebő(2004) は整合円順列を求める多項式時間アa∈A(C) length(a)nルゴリズムを与えるとともに，整合円順列が与えられたグを回転数と呼ぶ．回転数は明らかに整数であり，G 上で閉ラフから最小費用流問題を解くことによって Gallai の予路をたどったときに円順列を何周するかに対応している．

想を満たす安定集合と閉路被覆が得られることを示した．

さらに，閉路の回転数は円順列から得られる線形順序の後本研究では，Knuth (1974) による強連結グラフの分解ろ向き枝の数と一致する．

を用いて得られる結果から整合円順列を求める効率的なア強連結有向グラフ G = (V, A) の頂点集合 V 上に線形順ルゴリズムが導かれることを示した．また，強連結グラフ

序が与えられたとき，全ての枝が後ろ向き枝をちょうど一の耳分解を用いて整合円順列を求めるより高速なアルゴリつ含む閉路にも含まれるとき，この線形順序が G に対しズムを提案した．

整合的であるという．円順列が G に対し整合的であると

2 Gallai の予想
Bessy–Thomassé は，整合円順列という概念を導入し，全ての有向グラフに整合円順列が存在することを示した．
さらに，整合円順列が与えられた強連結グラフにおける最大最小定理を示し，そこから Gallai[2] の予想が正しいことを証明した．
定理 1（Bessy–Thomassé[1]，Gallai[2] の予想）
強連結グラフの頂点は α 個以下の閉路で覆うことができる．

は，円順列から得られる線形順序が G に対して整合的であることをいう．また，そのような円順列を整合円順列という．これに対し，Bessy–Thomassé[1] は次の補題が成り立つことを示した．
補題 1 全ての強連結有向グラフは整合円順列を持つ．

4 整合円順列を求めるアルゴリズム
これまでの先行研究では Sebő による O(n2 m2 ) のアルゴリズム FASO が知られていた．また，Knuth[4] の強連結グラフの分解からアルゴリズムを得ることができる．

さらにこの結果を受けて Sebő[5] は，整合円順列を求める

Knuth は全ての強連結グラフが G1 , . . . , Gk がそれぞれ強多項式時間アルゴリズムと，重みつきの場合も含む Bessy–連結グラフになるように図 1 のように分解できることを示

Thomassé の最大最小定理の最大値，最小値を達成する解した．また，Knuth は次のように枝を 2 種類に分類できを求めるアルゴリズムを提案した．

ることを示した．

3 円順列と整合性

補題 2 有限の強連結グラフ G = (V, A) が与えられて，V の線形順序 v1 , v2 , . . . , vn という関係に，v1 が vn の次に続くという関係を加えたものを V 上の円順列と呼ぶ．時計回りにこの順序で並べた状態を考える．u, v ∈ Vに対し，区間 [u, v] とは u から v へ時計回りで進んだときに通る頂点の集合（u, v も含む）を表すものする．区
間 I の長さ，length(I) を，I に含まれる頂点の数より1 少ないものと定義し，さらに，枝 a = uv の長さは，v ∈ V を任意に選んだとき，以下の 3 つの条件を満たすよ
うに G の全ての枝を 2 種類 ((f) と (b)) に分けることができる．

(i)(b) を通らない閉路はない．

(ii)

任意の a ∈ A は，(b) が 1 つだけで残りは (f) の閉路に含まれる．

(iii)

任意の v0 ∈ V \ {v} に対し，v0 から v へ (f) の枝だけのパスがある．

修士論文審査 論文要約

計算機実験において，アルゴリズム EDO は非常に高速に整合円順列を求められることが確認された．

5 最大最小定理
円順列と有向グラフ G = (V, A) が与えられたとき，

S ⊆ V が安定集合で，それらが与えられた円順列と等価なある円順列で区間になるとき，S は円安定集合と呼ばれる．Sebő[5] は，Bessy–Thomassé[1] の結果にさらに重みをつけた次の最大最小定理を示した．
定理 2 整 合 円 順 列 の 与 え ら れ た 強 連 結 有 向 グ ラ
図 1. Knuth 分解

フ G=(V, A) に お い て ，w:V (G)→Nと す る ．そ の と き ，max {w(S) : S は円安定集合 } =min {ind(C) : C は w 被覆 } が成り立つ．
(i)，(ii) を満たすように枝が分類されているときに，(iii)

この定理において任意の v ∈ V に対して w(v) = 1 の場合を満たすように (f) と (b) を順次入れ替える操作を枝操作を考えると Gallai の予想は簡単に証明できる．という．本研究では，補題 2 を満たすように枝が分類されSebő は，強連結グラフが与えられたときに定理 2 の等た状態において，(f) の枝のみに対してトポロジカルソー号を満たす解は次の 2 つのステップを行うことで求められトを行うことで整合円順列が得られることを示し，以下のることを示した．

アルゴリズム KDO を構成した．

Step 1

G に対して整合的な円順列を与える．

Step 2G の補助グラフ Ĝ を作り，最小費用流問題を

1. Knuth decomposition(G, 任意の頂点 v)．
2. (f) の枝に対し，トポロジカルソートを行う．
Knuth decomposition(G = (V, A), y ∈ V )if |A| = 0 return;w = 1 としてこのアルゴリズムを実行すると定理 1（Gallai の予想）を満たす閉路の集合と安定集合を得ることができる．Step 2 は，Goldberg–Tarjan[3] のアルゴリ
ズムを用いて O(nmlog(n2 /m)logn) で解くことができる．

else

Step 1 は，これまでの先行研究では O(n2 m2 ) であった．

Knuth 分解を行う．
成分同士を結ぶ枝のうち 1 本を (b) とし，成分同士を結ぶほかの枝を (f) とする;

for i = 1 until i = k do
Knuth decomposition(Gi , yi );G に対し，y を中心に枝操作する;
return;よって全体の計算量は O(n2 m2 ) であった．アルゴリズム

EDO を用いれば，Step 1 が O(nm) で求められるので，全体の計算量を O(nmlog(n2 /m)logn) に改善することができる．

参考文献[1] S. Bessy and S. Thomassé: Three min-max theo-

さらに本研究では O(nm) 時間で整合円順列を求めることができる耳分解を用いたアルゴリズム EDO を提案した．

1. D = (V (D), A(D)) とし，1 点 v ∈ V を選び，V (D) ={v}，A(D) = ∅ とする．

rems concerning cyclic orders of strong digraphs. Integer Programming and Combinatorial Optimization,
LNCS 3064, Springer-Verlag, 2004, pp. 132–138[2] T. Gallai: Problem 15. Theory of Graphs and its
Applications, M. Fiedler ed., Czech Acad. Sci. Prague,

2. (A \ A(D)) ∩ δ + v 6= ∅ な v ∈ V (D) を選ぶ．
そのような v がなければ 4 へ．

3. D において，v を中心に枝操作する．
while (A \ A(D)) ∩ δ + v 6= ∅解く．

doa ∈ (A \ A(D)) ∩ δ + v を選び，a を (b) とする．
∂ − a から D(V ) へのパス P をみつける．
全ての a ∈ A(P ) を (f) とする．

V (D) ← D(V )∪V (P )，A(D) ← A(D)∪A(P )∪{a} とする．
2. へ戻る．
4. (f) の枝に対しトポロジカルソートを行う

1964, p. 161.
[3] A. V. Goldberg and R. E. Tarjan:

Findingminimum-cost circulations by successive approximation. Math. Oper. Res., 15 (1990), pp. 430–466.
[4] D. E. Knuth: Wheels within wheels. J. Combin.
Theory, Ser. B, 16 (1974), pp. 42–46.
[5] A. Sebő: Minmax relations for cyclically ordered digraphs. Cahiers du Laboratoire Leibniz., Septembre
2004.