Document

演習問題
各問題の帰着（演習１）
下記のように帰着可能であることを示せ．
また，それぞれの帰着は平面性を保つか？

無向点素パス問題
有向点素パス問題
無向辺素パス問題
有向辺素パス問題
演習２

平面性判定のアルゴリズムを用いて，
平面グラフで s1, s2, t1, t2 が
この順番に同じ面上
をみたすかどうかを判定できることを示せ．
演習３

サイクルの木幅が 2 であることを示せ．
演習４
Demand graph
枝集合 s1t1, s2t2, …, siti をもつグラフを H とする．
定理 (Okamura-Seymour, 1981)
グラフが平面的，ターミナルが1つの面の周上，
オイラー条件 (G+H の次数がすべて偶数) を満たすとき，
辺素パスが存在
カット条件が成立
任意のカットに対して，
G の枝数 ≧ H の枝数

「オイラー条件」を除くと，この関係が成り立たなくなることを示せ．

「1つの面の周上」という条件を除くと，成り立たなくなることを示せ．
演習５
obstacle
各 i に対して， si と ti が共通の面の周上のとき，
Shortest non-crossing walks が多項式時間で
解けることを示せ．
（計算時間はとりあえず気にしない）
演習６

頂点数 n のサイクルが与えられたときに，
互いに交わらない弦の引き方が 2O(n) 通り
であることを示せ．
主張１
X(σ, Ω) は非空で even な部分列を持たない
証明
σ
even な部分列を持つと，walks を繋ぎ直して
より短い ST-walks が得られるので矛盾．
1 1 3 1 8 3 5 3
2 2 4 2 7 4 6 4
σ
1 1 3 1 8 3 5 3
2 2 4 2 7 4 6 4
同じ色を繋ぎかえる
1 → 4
5 → 8
9 → 12
演習７
この繋ぎかえで，クロスが
生じないことを示せ
主張２
長さ 2k 以上の X(σ, Ω) は，非空で even な部分列を持つ
演習８
主張２を証明せよ
σ : ある2点間の最短パス
Ω = {ω1, … , ωk}：最適な ST-walks
X(σ, Ω) : σ が交差する walk を順に並べた index 列
X(σ, Ω) の部分列が even
どの index も偶数回現れる

Download Report