オープンハウス 2010年6月3日

平面ネットワークの利用
データの高速更新（カーナビなど）
河原林 健一
国立情報学研究所

k_keniti@nii.ac.jp
http://www.nii.ac.jp/~k_keniti

Introduction

マイナー操作平面判定

私の研究

日常生活には，平面構造のネットワークが多い．
例えば，１．鉄道網
２．道路網 etc….
これらの「平面構造」という特徴を利用することで，ネットワークの理論的な解析が可能→ VLSI等のネットワーク構築→ 迅速なカーナビゲーションシステムの情報アップデート etc…

ネットワークの解析のためには「平面グラフ」の研究が必要不可欠！

Introduction

マイナー操作平面判定

私の研究

例えば，迅速なカーナビゲーションシステムの情報アップデート
は「動的計画法」を平面ネットワークに応用する動的計画法とは？

ネットワークの解析のためには「平面グラフ」の研究が必要不可欠！

Introduction

マイナー操作平面判定

私の研究

動的計画法とは，「近所」同士の情報を組み合わせて，ボトムアップで解を求める方法．
・ この方法は一般には時間がかかりすぎる．
・ しかし「平面ネットワーク（地図）」では，近所同士の情報の組み合わせが「最適解」を与えるため，ボトムアップで，解決可能．
・ 近所同士のみならず，「遠方」の情報を考慮し，組み合わせる必要があると，時間がかかりすぎる．

ネットワークの解析のためには「平面グラフ」の研究が必要不可欠！

Introduction

マイナー操作

マイナー操作

１．辺を取り除く．
２．頂点を取り除く．
３．辺を縮約する．

平面判定

私の研究

Introduction

マイナー操作平面判定

私の研究

では，コンピューターはどのように地図（平面ネットワーク）を認識するか？
注意：コンピューターは０と1のみしか認識できない！
まずは，地域同士が，隣接していれば１，していなければ０を入力
０，１のデータから平面ネットワーク（地図）を描く．

ネットワークの解析のためには「平面グラフ」の研究が必要不可欠！

Introduction

マイナー操作平面判定

私の研究

では，コンピューターはどのように地図（平面ネットワーク）を認識するか？
０，１のデータから平面ネットワーク（地図）を描く．
疑問 １． コンピューターも同じ地図を描けるか？
また多くの人が，０，１のデータをもらった場合，「同じ」地図を描けるか？

ネットワークの解析のためには「平面グラフ」の研究が必要不可欠！

Introduction

マイナー操作平面判定

私の研究

では，コンピューターはどのように地図（平面ネットワーク）を認識するか？
→ 隣接していれば１，していなければ０を入力
定理 （Whitney，１９３５) 平面地図は一意に描ける！
つまり，あなたの地図の描き方と，私の地図の描き方は，どのような地図の描き方をしようと同じ！

ネットワークの解析のためには「平面グラフ」の研究が必要不可欠！

Introduction

マイナー操作

平面判定

私の研究

定理 （Whitney，１９３５) 平面地図は一意に描ける！
つまり，あなたの地図の描き方と，私の地図の描き方は，どのような地図の描き方をしようと同じ！(本当？？)
つまり，
１．東京とは神奈川県,千葉県,埼玉県と隣接している．
２．千葉県は埼玉県と茨城県に隣接している．
３．栃木県は群馬県に隣接している.などの情報から関東地方の地図を描く．
(隣接していれば入力は１，していなければ０）．
あなたの地図は,私の地図とほぼ同じ！
これはあたりまえ？？？

Introduction

マイナー操作

マイナー操作

１．辺を取り除く．
２．頂点を取り除く．
３．辺を縮約する．

平面判定

私の研究

Introduction

マイナー操作

平面判定

私の研究

定理 （Whitney，１９３５) 平面地図は一意に描ける！
つまり，あなたの地図の描き方と，私の地図の描き方は，どのような地図の描き方をしようと同じ！
では次の地図はどう？
１．カリフォルニア州はオレゴン州とニューメキシコ州に隣接
２．モンタナ州はノースダコダ州，ワイオミング州などと隣接.
３．テネシー州は,アラバマ州，ジョージア州などと隣接．
４．イリノイ州は,ミシガン州,オハイオ州と隣接．
等の情報からアメリカ州地図を描く．
(隣接していれば入力は１，していなければ０）．
あなたの地図は,私の地図とほぼ同じ！
これは難しい？？

Introduction

マイナー操作平面判定

私の研究

０，１でもらったデータから平面ネットワーク（地図）を描
く．
疑問 ２． コンピューターへの入力は間違っていないか（入力ミス）？
つまり，平面的に（地図として）描けるかどうかをどうやって見極める？
この疑問にこたえるためには「平面グラフ」の研究が必要不可欠！

ネットワークの解析のためには「平面グラフ」の研究が必要不可欠！

Introduction

マイナー操作

平面判定

私の研究

平面グラフとは，「辺をそれぞれ交差しないように平面上に描くことができるグラフ」を指す

平面グラフの一例

Introduction

マイナー操作平面判定

私の研究

では，コンピューターはどのように地図（平面ネットワーク）を認識するか？
→ 隣接していれば１，していなければ０を入力
この０，１のデータから地図を描く．
定理 （Whitney，１９３５) 平面地図は一意に描ける！
つまり，あなたの地図の描き方と，私の地図の描き方は，どのような地図の描き方をしようと同じ！
定理 （Whitney，１９３５) (3連結)平面グラフは,一意に平面に描ける！

Introduction

マイナー操作平面判定

私の研究

ネットワークを理論的に解析するためには，実際のネットワークが平面（またそれに近い構造の）グラフかどうかを判定する必要がある！！

問題： 与えられたネットワークが「平面グラフ」
かどうかを，どのように判定するか？
問題： 与えられたネットワークが「平面グラフ」ならどのように「よい」平面グラフを得るか？
→この問題の解答を得るためには「マイナー操作」を理解する必要がある．

Introductionマイナー操作

平面判定

私の研究

マイナー操作とは？？？
どんな平面グラフでも，次の３つの操作を加えた後も平面グラフの性質は変わらない
１．辺を取り除く．
２．頂点を取り除く．
３．辺を縮約する．

この３つの操作をグラフ理論の分野では「マイナー操作」という

Introductionマイナー操作

マイナー操作

１．辺を取り除く．
２．頂点を取り除く．
３．辺を縮約する．

平面判定

私の研究

Introductionマイナー操作

平面判定

マイナー操作１．頂点を取り除く．
２．辺を取り除く．

３．辺を縮約する．

私の研究Introductionマイナー操作

平面判定

私の研究

この３つの操作（１．頂点を取り除く ２．辺を取り除く ３．辺を縮約する）をしても平面グラフがその性質を保存することを「マイナー操作に関して閉じている」と呼ぶ
重要：「全ての平面グラフはマイナー操作に関して閉じている」が，「マイナー操作に関して閉じているグラフが全て平面グラフ」ではない！

Introduction大きいグラフ平面グラフ
非平面グラフマイナー操作

平面判定

マイナー操作１．頂点を取り除く．
２．辺を取り除く．
３．辺を縮約する．

私の研究

小さいグラフ平面グラフ
非平面グラフとは限らない．

与えられたグラフが平面グラフかどうかを判定する
ためには，「非平面グラフ」から，「平面グラフ」になる「最小」のグラフは何かを調べる必要がある．

Introduction

マイナー操作平面判定

私の研究

非平面から，平面になる「最小」のグラフは何か？
クラトスキーの定理 その１非平面の「最小」なグラフは，K3,3とK5である．
与えられたグラフが平面グラフである必要十分条件は，「どのようなマイナー操作をしても，K3,3とK5にならない」ということである

Introduction

マイナー操作K3,3とK5グラフの例

左: K5グラフ

右: K3,3グラフ

平面判定

私の研究Introductionマイナー操作

平面判定

私の研究

クラトスキーの定理 その２平面グラフに対しては，「禁止」すべき「最小グラフ」は，K3,3とK5のみである．
平面グラフかどうかを判断するための指標になる．平面グラフかどうかの判定に利用されている．

Introductionマイナー操作

平面判定

私の研究

実用の場面では，平面グラフの判定を可能な限り迅速に行う必要がある！！

平面グラフの判定の計算量(Hopcroft, Tarjan)
平面グラフは，線形時間で判定できる（ここでいう『線形時間』とは，入力の頂点数に関して線形関数のステップ（O(n)）という意味である）．

この判定アルゴリズムを導き出すために，クラトスキーの定理が利用されている．

Introductionマイナー操作

平面判定

私の研究

私の研究の一例
実際のネットワーク網は，「完全な平面」とは限らない．(例えば，交通網における立体交差や鉄道網での地下トンネル等）→ 与えられたグラフが，ｋ交差グラフであるかの判定を線形時間で行うことは可能か？
→ 与えられたグラフが，ｋ‐平面グラフであるかの判定を線形時間で行うことは可能か？
…等を明らかにする必要がある

Introductionマイナー操作

平面判定

私の研究

最近の研究で，以下の性質のグラフを線形時間で判定することが可能であることを明らかにした（STOC’07,STOC’08,FOCS’08,STOC’０９,FOCS’09等）．
１．ｋ平面グラフ．
２．ｋ交差グラフ．
３．曲面上に埋め込めるグラフ（例えばドーナツ状のトーラス）．

Introductionマイナー操作

３．曲面上に埋め込めるグラフ（ドーナツ状のトーラス）

平面判定

私の研究

Introductionマイナー操作

平面判定

私の研究

私の研究の一例
実際のネットワーク網は，「完全な平面」とは限らない．(例えば，交通網における立体交差や鉄道網での地下トンネル等）→ ｋ交差グラフでのデータ更新の高速化→ ｋ平面グラフでのデータ更新の高速化…等の開発（STOC‘07,STOC’08,FOCS‘08,STOC’09,FOCS’09など）

Introductionマイナー操作

平面判定私の研究実用の場面では，平面グラフを可能な限り迅速に得る必要がある！！

平面グラフの判定の計算量(Hopcroft, Tarjan)
平面グラフを，線形時間で得ることできる（ここでいう『線形時間』とは，入力の頂点数に関して線形関数のステップという意味である）．

このアルゴリズムは，マイナーの「逆操作」を利用し，高速で平面ネットワークを得ることができる