$\newcommand{\set}[1]{\{#1\}}$ $\newcommand{\inset}[2]{\{#1 \mid #2\}}$ $\newcommand{\name}[1]{\emph{#1}}$ $\newcommand{\size}[2][]{\left| #2^{#1} \right|}$ $\newcommand{\sig}[1]{\mathcal{#1}}$

Chordal Graph: Maximum Cardinality Search

今回はグラフの性質のお話ではなくPEOを求めるためのアルゴリズムのお話をします. MCSとLex BFSというアルゴリズムのお話をします. chordal graphの性質についてはこの2つのアルゴリズムを説明した後にもまだまだ書きます.

今回は長くなるので,2回に分けました. PEOを求めるアルゴリズムだけ知りたい人は今回のMCSの部分だけ読むとわかると思います. ただ,Lex BFSはMCSよりも便利な印象があって,Lex BFSを使うと他の問題も解けるようです. 例としてあげられるのは1つしか知りませんが,入力グラフ$G$がCo-graph($P_4$-free graph),つまり, 誘導部分グラフとして長さ4のパスを含まないグラフかどうかの判定問題もLex BFSで解けるらしいです. 論文とかではなく,ネット上の資料ですが,こんなスライドがあって,紹介されています. 多分競プロerなら知っていると思いますが,hosさんのスライドです. こちらはブログでは紹介しなさそうな予感です.気が向いたらするかも?

今回のお話に入っていきます.前回PEOという順序があることとグラフがchordalであることが同値であることはわかりました. でもPEOを計算できないとグラフがchordalかどうかを確かめられないので悲しい気持ちになります. しかし,PEOはグラフサイズに対して線形時間で求めるMCSとLex BFSという2つのアルゴリズムがあります. 今回はそのうちの1つのMCSを紹介します.Lex BFSは次回説明するのでお楽しみに!

Maximum cardinality search

まずはアルゴリズムの動きを説明した後で,アルゴリズムの正当性を証明します. 計算時間の解析はほぼ自明なので,特にはしません. MCSは,単純にいうと貪欲に次数の大きい頂点から頂点をとっていくだけのアルゴリズムなのですが, どういったグラフの中で次数が大きいのかを考えるのがキモになります.当然ですが,入力グラフ$G$を 考えて,そこから次数の大きい順に頂点を選んで順序付してもPEOにはなりません.

そこで,入力グラフ$G = (V, E)$に対してどういったグラフを考えるかというと, 二部グラフっぽいグラフ?$H = (X, Y, E)$を考えます. ここで,$H$は,$X \cup Y = V$かつ$X \cap Y = \emptyset$を満たします.辺集合は$G$と$H$は同じです. $X$間の2頂点や$Y$間の2頂点にも辺はあるので,二部グラフではないのですが,それに近いイメージです. つまりは頂点集合を2つに分割したグラフを考えるということですね.図にするとこんな感じです.

f:id:chocobaby-aporo:20171105152859j:plain

$H$は初期状態として,$X = V$,$Y = \emptyset$を満たすとします.ここで,$\size{N(v) \cap Y}$が最大になるような 頂点$v \in X$を選択します.また,$\size{N(v) \cap Y}$の値が同じ$v$が複数ある場合はそのうちの任意の1つを選択します. そして,$v$を$X$から$Y$に移動させます.つまり$H' = (X \setminus \set{v}, Y \cup \set{v}, E)$というグラフに更新します. これを$X$が空集合になるまで繰り返します. すると,グラフがchordalであれば必ずこの頂点の追加順の逆順がPEOになります. 証明は後で行います. ここでは,順序付の逆順をMCS順序と呼ぶことにします. ただし,この順序はchordal graphでなくても定義できるので,本当にMCS順序がPEOになっているかはチェックする必要はあります. ここで保証されるのは,$G$がchordalであればMCS順序が必ずPEOになるということ保証します. アルゴリズムの動きはこんな感じですね.

f:id:chocobaby-aporo:20171105152914j:plainf:id:chocobaby-aporo:20171105152922j:plainf:id:chocobaby-aporo:20171105152924j:plainf:id:chocobaby-aporo:20171105152927j:plain

ついでに大雑把に計算時間についていうと,このアルゴリズムを線形時間で実装する方法は色々あると思うのですが, $X$中の頂点集合の次数順ソートした頂点列を持っていて,$X$から$Y$に頂点が移動するたびにそれを更新すれば $O(\Delta)$時間で1つの頂点を移動できるので,全体で$O(n + m)$時間で計算できます.($n$と$m{}$ は頂点数と辺数) ソートには$O(n \log n)$かかるんじゃね?っと思うかもしれないですが,次数はたかだか$n$しかないので, バケットソートすると線形時間でソートできます.色々自分のやりやすい実装を考えてみてください. (記事を見ている人は競プロerが多い想定なので,いい実装を思いついてくれそう)

MCSの正当性の証明

これ以降は正当性の証明です.ここでは,MCSで作る任意の順序付を$\alpha$とします. これ以降では頂点番号はの順序で番号を振り直したと考えてください. 例えば,頂点数4のグラフがあって,$\alpha = (3, 2, 4, 1)$だったら, 3を1に,2を2に,4を4に,1を4に番号をつけ直したと考えてください. グラフがchordalである場合,この順序が必ずPEOを出力することを証明します. 今回は直接これを証明する前に次の補題を証明します. ここで,$V_i$は頂点番号$i$から$n$までの頂点を含む集合とし, 頂点$v$の頂点番号を$id(v)$と表記することにします.

$\alpha$がPEOではない $\iff$ ある頂点$v_i$に対して,$v_i$から$v_j \in V_{i + 1}$までの$ V \setminus V_{i+1} $を通る長さ2以上のchordless pathが存在する.

chordless pathとはpath $P = (v_1, \dots, v_k)$の任意の頂点$v_i$が$v_{i - 1}$と$v_{i + 1}$以外の頂点と隣接しないpathです. ちょっとこの補題が何を言っているのかわかりにくいと思うので,この補題が表す状態を図にするとこんな感じです.

f:id:chocobaby-aporo:20171105153130j:plain

このグラフはchordalではないので,PEOを持ちません.なので,MCS順序も当然PEOではありません. ここで,頂点4から頂点6まで,$P = (4, 1, 2, 6)$というchordless pathがあります. このように$v_i$から$v_j \in V_{i + 1}$まで,頂点番号$i$未満の頂点だけを通ってchordless pathを作れることが$\alpha$が PEOではない必要十分条件だという補題です.

ここから証明を始めますが,いつものように,「$\alpha$がPEOではない」を条件$A$, 「ある頂点$v_i$に対して,$v_i$から$v_j \in V_{i + 1}$までの$V \setminus V_{i + 1}$を通る長さ2以上のchordless pathが存在する」を条件$B$として証明を始めていきます.

まずは$A \to B$を証明します. $\alpha$がPEOではないので,ある頂点$v_i$が存在して,$G[V_i]$中の$N[v_i]$からなる誘導部分グラフはcliqueにはなりません. したがって,$v_i$の隣接頂点に2頂点$v_j, v_k \in V_{i + 1}$が存在し, $v_j$と$v_k$は隣接していません. ここで,一般性を失わずに$id(v_j) < id(v_k)$と仮定できます. $v_j, v_k \in V_{i + 1}$より,$id(v_i) < id(v_j) < id(v_k)$が成り立つので,パス$(v_j, v_i, v_k)$は $v_j$から$v_k \in V_{j + 1}$までの,$V \setminus V_{j + 1}$を通る長さ2のchordless pathになります. よって$A \to B$が成り立ちました.

次に$B \to A$を証明します. $B$の条件を満たすchordless pathがあるので,そのパスを$P = (v_0, v_1, \dots, v_j)$とします.ここで$j \ge 2$を満たします. 今,$P$中の$v_0$と$v_j$以外の頂点で,$\alpha$で振り直した頂点番号で最小の番号を持つ頂点を$u$とします. すると,この$u$は自身よりも大きな頂点番号を持つ$P$中の頂点$x$と$y$に隣接し,$x$と$y$の間に辺はありません. なぜなら,$P$はchordless pathだからです. このとき,$G[V_{id(u) + 1}]$上で$N[u]$はcliqueになりません. したがって$\alpha$はPEOになりません.これで$B \to A$の証明完了です. これで$A \iff B$が証明できました.

ここから$G$がchordalの場合,任意のMCS順序がPEOになる証明に入ります. 興味ある人は是非読んでみてください.

chordal graph $G$の全てのMCS順序は$G$のPEOである.

MCS順序は複数あり得るのですが,ここではその全てがPEOであることを示します. 背理法を用いて証明します.なので,複数あるMCS順序の中でPEOでないMCS順序$\alpha$が存在すると仮定して, $\alpha$はMCSで出力される順序と矛盾することを示します. $\alpha$はPEOではないので,先ほどの補題からある頂点$v_0$を持ち, 長さ2以上のchordless path $P = (v_0, \dots, v_k)$を持ちます.

このような$P$は複数あることが考えられるのですが, ここでは,いくつかある$P$の中で$id(v_0)$が最大な$P$を考えます. ここで,$\alpha$がMCS順序に矛盾することを示したいので, $V \setminus V_{id(v_0) + 1}$中に 次の条件$(1)$を満たす$w$があることを示して証明します.

  • $\size{N(v_0) \cap V_{id(v_0) + 1}} < \size{N(w) \cap V_{id(v_0) + 1}} \cdots (1)$

MCSは$V \setminus V_{id(v_0) + 1}$の頂点から$V_{id(v_0) + 1}$に対する次数が大きい頂点を貪欲に取るアルゴリズムなのに, $id(v_0)$よりも小さい頂点番号を持つ$w$が$(1)$を満たすのは アルゴリズムの動作と矛盾します. そこで,今からは$P$中の$v_{k - 1}$が次の条件を満たすことを示します. そのために,以下の条件が成り立つことを示します.

  • $N(v_0) \cap V_{id(v_0) + 1} \subset N(v_{k - 1}) \cap V_{id(v_0) + 1}$ $\cdots$ (2)

この条件を満たせば明らかに$id(v_{k - 1}) < id(v_0)$はMCS順序に矛盾します. まず自明な場合を考えます.ここで,長さ1以上のchordless path $P = (v_0, \dots, v_k)$があります. $P$は長さ1以上のchordless pathの中で$id(v_0)$が最大なchordless pathです. $N(v_0) \cap V_{id(v_0) + 1} = \emptyset$の場合, $v_{k - 1}$は$v_k \in N(v_{k - 1}) \cap V_{id(v_0) + 1}$を満たすので, 明らかに$(2)$を満たします.

次に$N(v_0) \cap V_{id(v_0) + 1} \neq \emptyset$の場合を考えます. ここで,$x \in N(v_0) \cap V_{id(v_0) + 1}$とし, パス$P' = (x, v_0, \dots, v_k)$を考えます.$P$は$id(v_0)$が最大なchordless path, かつ$id(v_0) < id(x)$なので$P'$はchordを持つパスになります. $P$はchordless pathなので,$P'$の持つchordは$x$と隣接した辺になります. このときもつchordを$e = \set{x, y}$とすると, パス$P'' = (x, y = v_r, \dots, v_k)$が存在するのですが,これも$id(v_0)$の最大性より chordを持つパスになります.さらに,サイクル$C = (x, v_0, \dots, v_r = y, x)$を考えると, $G$がchordalであるという条件から$C$もchordを持ちます. このように,$x$を含むパスやサイクルはchordを持つため, どんどん短いパスやサイクルに分割ができます. この分割を繰り返すと,$P$中のすべての頂点は$x$と辺を持つことがわかります. (下の図のようになります.) つまり,$v_{k - 1}$は$x$と隣接します.したがって,$N(v_0) \cap V{id(v_0) + 1}$中の 任意の頂点は$v_{k - 1}$と隣接します.さらに, $v_0$は$P$がchordless pathであることから$v_k$と隣接せず, $v_{k - 1}$は$v_k$と隣接するので,$(2)$が証明できました. したがって,$G$がchordalの場合,$\alpha$は長さ2以上のchordless pathを持ちません. つまり,MCS順序はPEOになります. サイクルやパスで$P$が短くなっていくのは下の図のようになっています. 太線が$id(v_0)$が最大の誘導パス$P$を表し, 点線は$P$の$id(v_0)$の最大性と$G$がchordalであることから 存在することが証明できる辺です.

f:id:chocobaby-aporo:20171112092755j:plain

終わりに

これで,グラフがchordal graphかどうかを確かめる問題が線形時間で解けることがわかりました. 正当性の証明はそこそこ重い内容でしたが,とりあえず動きを知りたいという人にとっては MCSのアルゴリズム自体は簡単めかと思います.

余談ですが,今回のような「このグラフってhogehoge graphなの?」というYes/No問題のことをgraph recognitionと言います. なので,chordal graphのgraph recognitionは線形時間で解けるということですね! あとはchordal graphってhyper graphのacyclic性を表すグラフクラスだとか,そういう話を 聞くのですが,ちゃんとはわかっていないので,気になっているところです.(気が向いたら勉強してブログに書くかも?)

次回はclicque treeについてお話ししようと思いましたが,Lex BFSが今回の内容に入らなかったので,先にそちらを説明します. clique treeは今までで一番面白い内容だと思うだけに先延ばしになってしまい残念... 今回から少しずつ内容が重くなっていくと思いますが,頑張ってわかりやすく書きたいと思うので,何かわからないことがあったら是非質問してください!

Chordal Graph: Perfect elimination ordering

3回目のChordal Graph回です. 知識的にストックがあるのと,始めたばかりでやる気があるので,更新ペースがめちゃくちゃ早いです.

今回はPerfect elimination orderingについて説明します. Perfect elimination ordering (PEO) もchordal graphの重要で面白い性質の一つだと思います. chordal graphのいろんないい性質を見ていると,長さ4以上のサイクルには必ず弦があるという定義って結構狭いグラフクラスを 表しているのかなとか思いますね.

Perfect elimination ordering

Perfect elimination orderingとは頂点の順序付で,次の性質をみたす頂点の順序付のことです. どんな性質かというと,ある順序$\pi = (v_1, v_2, \dots, v_n)$の全ての$v_i$が,$G[V_i]$中でsimplicial vertexである とき,$\pi$をperfect elimination orderingと言います.ここで,$V_i$とは$\set{v_i, v_{i + 1}, \dots, v_n}$からなる頂点集合です. 図にするとこんな感じの順序付ですかね.simplicial vertexについてはこちらを見るとわかると思います.

f:id:chocobaby-aporo:20171107140822j:plain

こんな感じに順序付けると確かにどの頂点を見ても自分より頂点番号が大きい頂点からなる誘導部分グラフを考えると自分自身はsimplicial vertexになっていますね. PEOについてはこんな定理が知られています.

$G$がchordalである.$\iff$ $G$がPEOを持つ.

はい,またもや非自明感満載の定理が出てきました. とはいえ,実は前回のsimplicial vertexをうまいこと使うとこの定理も簡単に証明できます. ここでは$G$がchordalという条件を$A$,$G$がPerfect elimination orderingを持つという条件を$B$とします. それでは証明をしていきます. まずは$A \to B$から証明していきます. これは簡単で,前回にやった定理を使うと$G$はsimplicial vertexを1つは持つので,その頂点$v$を$G$から取り除きます. $G \setminus \set{v}$も同様にchordalなので,$G$がなくなるまでsimplicial vertexを選んで行けばPEOができます.

次に$B \to A$を証明します. ここで$\alpha = (u_1, \dots, u_n)$をPEOとします.ここで,$G$にサイクルがないと自明に$G$はchordalなので, $G$はサイクルを持っていると仮定し,その任意のサイクルを$C = (w_1, \dots, w_k)$とします. ここで,頂点番号を$\alpha$の順序で振り直したと考えます.$C$中の番号最小な頂点を$w_i$とすると, PEOの定義より,$w_i$の隣接頂点で,$w_i$より番号の大きな頂点たちはcliqueになっています. すると$C$は弦を持つことになります.また,その弦を含む$C$より短いサイクル$C'$を考えても 同様に頂点番号最小の頂点を持ってくると$C'$は弦を持ちます.これはサイクル長が3になるまで繰り返し 適用できるので,どんな長さ4以上のサイクルを持ってきても必ず弦を持ちます.したがって$G$は chordal graphになります.証明のイメージは下のような感じですかね?

f:id:chocobaby-aporo:20171104175426j:plain

多分次回はMaximum Cardinality Searchの話をして,次の回にClique Treeのことを書こうかと思います. Clique Treeは木幅とかとも関係がある概念だと(僕は)思っています.

雑談

  • この辺りは間違ったことを書いている可能性がありますので,変なこと書いていたらごめんなさい.

PEOの存在性もchordal graphの定義になることを紹介しました. 実はPEO繋がりでまだまだ面白い話はあってそれについて少し書いていこうと思います. この論文にも色々書いてありますが, 僕が分かる範囲で書いていこうと思います.

上記の論文中で適当に頂点の順序付をして,その順序付がPEOになるように辺をいくつか追加したグラフを$H$とすると, 元のグラフが$G$がchordalであることと$G$と$H$が一致するような順序付が存在することは 今回示した定理から同値な関係になることがわかります. しかも,PEOは実は線形時間で見つけることができるので,具体的な順序を見つけることも簡単にできます. この線形時間アルゴリズムは2つあって,一つがLexicographic breadth first search(Lex BFS)といい, もう一つが次の回で紹介するMaximum Cardinality Searchというアルゴリズムです.

ここで,この$H$が入力グラフ$G$と一致する順序を見つける問題をchordal graphでないグラフを入力とした場合を考えてみます. そうすると今回示した定理から当然そのような順序は存在しないので, ちょっと問題を変えてみて$G$に追加する辺の数が最小になるような順序付を見つける問題としてみましょう. 要は$H$の辺数から$G$の辺数を引いた値が最小になるようにしたい問題です. この問題はMinimum Fill-inと呼ばれているNP-完全問題になります. Minimum Fill-inは最適な木分解を求める問題と関連が深い問題のようです. (多分どっちかを解くアルゴリズムがあるとちょっと変更を加えるともう片方も解けるのだと思われる) すみません,どういう関連があるかは正確にわかっていない部分はあります. 一応こんな論文は出ていますね. 実際この論文では最適な木幅とMinimum Fill-inを計算するアルゴリズムを与えています. 当然多項式時間アルゴリズムではありませんが. このあたりの問題がにているなぁと感じる理由は後々書きます. もしかしたらそれまでにきちんと勉強して関連の部分を正確に書く日が来るかもしれません.

Chordal Graph: Simplicial vertex

なんか意外に反響があった(アクセスログを見ていたらみんなが見ていてくれた)のでやる気を出したのと,少し今回の内容が簡単だったのもあって が〜っと書いてしまいました.2回目のChordal Graph回です. 今回は次回にやる予定のPerfect elimination orderingのための準備として, Simplicial vertexについて説明していこうかと思います.

Simplicial vertexとは

Simplicial vertexとはすごく単純で,グラフ$G$中で$G[N[v]]$がcliqueになる頂点$v$のことです. 図に書くとこんな感じですね.($N[v]$は$v$の隣接頂点と$v$からなる集合を表します.) 下の図では頂点$v$は隣接頂点$1, 2, 3$がclicqueになっているのでsimplicial vertexになります.

f:id:chocobaby-aporo:20171104001929j:plain

さあ,これがchordal graphとどういう関係があるのかというと,次の定理が知られています.

$G$がchordal graph,かつcomplete graphではない. $\to$ $G$は少なくとも2つの隣接しないSimplicial vertexを持つ

以前紹介した定理よりは少し直感的に正しそうな定理ですね(個人的な感想). それでは証明していきます.

今回は頂点数に関する数学的帰納法で証明します. 頂点数$2$の場合はグラフは2つしかなくて,頂点$u, v$間に辺がある場合とない場合の2つのグラフしかありません. 辺があるとcomplete graph,辺がない場合は$u$と$v$がsimplicial vertexなので,この定理は成り立ちます. なので,頂点数$k$のchordal かつ completeでない全てのグラフは定理を満たすと仮定します. なので,頂点数$k + 1$の任意のchordal かつ completeでないグラフ$G$を考えます. $G$中の隣接しない2頂点$u, v$を取ってきて,その2頂点をseparateするminimal separatorを$S$とします. このとき,$G$がchordalなので,$S$はcliqueになります.(前回の記事に証明があります) さらに,$S$がseparatorなので,連結成分$A$と$B$が$G \setminus S$中に存在します. ここで,$u \in A$,$v \in B$としても一般性を失わないのでそう仮定します. したがって,$A \neq \emptyset$かつ$B \neq \emptyset$となります. $G[A \cup S]$と$G[B \cup S]$を考えると,この2つは$\size{G[A \cup S]}, \size{G[B \cup S]} < \size{G}$を満たします.

$G$の誘導部分グラフはchordalなので,$G[A \cup S]$と$G[B \cup S]$がcompleteでないならば, 帰納法の仮定より,simplicial vertexを2つずつ持つことになります. さらに,$G[A \cup S]$中のsimplicial vertexを2頂点$x, y$とすると, $x, y$は隣接しません.したがって,$x$か$y$のどちらかは$S$に含まれていません. なぜなら$S$はcliqueだからです.ここで,$S$に含まれる頂点を$x$とします. すると,$y$は$A$に含まれ,$G[A \cup S]$中の$y$の隣接関係と $G$中の$y$の隣接関係は一致します. したがって,$y$は$G$中でもsimplicial vertexになっています. また,$G[A \cup S]$と$G[B \cup S]$がcompleteだったとしても, それらのグラフは$S$に含まれないsimlicial vertexは必ず1つは持ち, その2つの頂点は元のグラフで隣接していないので,$G$は隣接していない2つのslimlicial vertexを持ちます. よって証明終了です. 証明のイメージ図はこんな感じですね.

f:id:chocobaby-aporo:20171107142405j:plain

$G$を2つに分割するんですが,そうすると$G$よりサイズの小さい2つのグラフができて,その2つのグラフはchordalだし,たとえcompleteだとしても1つは $S$に含まれないsimplicial vertexを持つので,隣接しない2つのsimplicial vertexはあるよね!という証明です. ただし,図中の$x$のように分割後の$G[A \cup S]$や$G[B \cup S]$中でsimplicialだとしても元のグラフ$G$ではsimlicialではない頂点もあります. そういう頂点を考慮しても隣接しない2つのsimplicial vertexがchordal graph$G$中には存在します.

今回の内容は少し軽めでしたが, すみません,以前の証明は間違いがありました. 現在は修正されています.(11/06)

この定理はこれからの証明にすごく便利なので, 僕としては後になればなるほどいい性質だなぁと感心しました.

Chordal Graph: Minimal vertex separators

chocobaby-aporo.hatenablog.com

Chordal Graph回の第一回目です.今回はMinimal vertex separatorsを紹介します.

Minimal vertex separators

まず,$G = (V, E)$中の頂点集合$S \subseteq V$が,vertex separator (separator)とは 次のような2頂点$u, v$が存在することを言います.

  • $u, v$は$G$中の連結成分に含まれるが,$G \setminus S$では同じ連結成分に含まれない.

この時,$S$は$u, v$をseparateすると言います. 簡単にいうと下の図のような頂点集合です.一応この例のグラフはchordalになっているはずです. f:id:chocobaby-aporo:20171103141010j:plain 特に,Minimal separatorというとSeparatorの中でもどんな頂点を除いてもseparator出なくなるようなseparatorです.

f:id:chocobaby-aporo:20171103150458j:plainf:id:chocobaby-aporo:20171103141024j:plain

ここでChordal Graphの面白い性質1つ目ですが,次のような定理が知られています.

グラフ$G$がchordalである. $\iff$ $G$中の全てのminmal separatorがcliqueである.

$G$がchordalであるという条件を$A$,$G$中の全てのminmal separatorがcliqueであるという条件を$B$とします. まず$\lnot A \to \lnot B$,つまり$B \to A$について証明します. $G$がchordalではないので誘導部分サイクル(誘導部分グラフかつサイクル,要は弦を含まないサイクル)$C = (u_1, \dots, u_k)$が存在します.$(k \ge 4)$. この$C$中の隣接しない2頂点$u, v$をseparateするMinimal separatorを$S$とすると,この$S$は$C$中の隣接しない2頂点を含むのでcliqueではありません. したがって$B \to A$が成り立ちます.

次に$A \to B$を証明します. $S$を任意のminimal separatorとして,$G \setminus S$の連結成分の集合を$\sig C$とします. ここで重要なこととして,minimal separator $S$中の任意の頂点$u$は必ず$\sig C$中のすべての連結成分と隣接しています. もし全ての隣接成分と隣接していない頂点があると,minimal性が成り立たないからです.図で見るとこんな感じの状態になっています.

f:id:chocobaby-aporo:20171103144834j:plainf:id:chocobaby-aporo:20171103144838j:plain

ここで,この性質から$S$中の任意の2頂点$u, v$は$G$中のあるサイクルに含まれることがわかります. しかも,そのサイクルの中には$S \setminus \set{u, v}$中の頂点を含まないサイクルも存在します. (要は$S$中の要素の$u$と$v$だけを含むサイクル)図中の赤線がそのサイクルを表しています. このサイクルは必ず長さが4以上なので,このサイクル中には必ず弦があります. この弦が$u, v$を結ぶ弦なら$u, v$は隣接するし,もし$u, v$を結ばないならその弦を含む$C$より短いサイクルができるため, 最終的には$u, v$を含む長さ4のサイクル$C'$ができます.ここで,$G$がchordalなので, $C'$も弦を含むのですが,$u$と$v$以外のサイクル中の頂点,つまり異なる連結成分同士の頂点を結ぶと,$S$がseparatorであることに矛盾するので, $u$と$v$を結ぶしかありません.つまり$S$中の任意の2頂点$u, v$は隣接しています.言い換えると$S$が誘導する$G $の誘導部分グラフ$G[S]$はcliqueになります.

まとめ

というわけで,Chordal Graphの面白い性質その1は

  • グラフ$G$がchordalである. $\iff$ $G$中の全てのminmal separatorがcliqueである.

という性質でした.正直Choralの定義だけみて,「それなら全てのminimal separatorはcliqueになるのか〜」と気付く人はほとんどいないと思いますが, こんな面白い性質があることが知られています. まだまだ面白い性質があるので,気合が続く限り紹介していきます.

追記

今はまだ事実だけを書いておきますが,実はMinimal separatorの数はchordal graphの頂点数よりも少なくなることが知られています. それについての論文が出ていて,これですね. chordal graph以外でもminimal separatorの数については研究されています. あまり僕が理解していないので申し訳ないですが,一般のグラフでのMinimal separatorの数は O(1.6181n) なので, chordal graphではminimal separatorの数がすごく少なくなるのが知られています. 一般のグラフでのMinimal separatorの数の上限についてはここを参照してください.

Chordal Graph

最近Chordal Graphがマイブームです. このシリーズの記事でわからないところやこれ間違っているぞっというのがあったら Twitterで教えてくれると僕が喜びます.

Chordal Graphとは

Chordal Graphとは任意の長さ4以上のサイクルに対して弦が存在するグラフです.wikiへのリンク ここで,ある辺$e$がサイクル$C = (u_1, \dots, u_k)$の弦(chord)とは,$e = \set{u_i, u_j}$かつ,$e$が$C$に含まれない辺のことです. つまり,$C$をより短いサイクルにする辺ということですね.こんな感じの例です.

f:id:chocobaby-aporo:20171104213013j:plain

これだけ聞くと,なんの感想もわかないのですが,実は色々と面白い性質があって最近勉強中です. この記事のネタ本はこれです. これから何回かに分けて自分の勉強を兼ねてこの本の内容を紹介をしていこうと思います.

とりあえず紹介しようかと思っている内容のキーワード

CodeFestival2016本戦の問題

この前Code Festival2016に行ってきました.問題はこんな感じでした.

  • A問題 Where's sunuke まあ,A問題なのでやるだけ問題です.
#include<iostream>
using namespace std;
 
int main(){
  int h, w;
  std::cin >> h >> w;
  string s;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      std::cin >> s;
      if(s == "snuke"){
        std::cout << (char)(j + 'A') << i + 1 << std::endl;
      }
    }
  }
  return 0;
}
  • B問題Exactly N points
    どうせB問題もやるだけだろうと思って適当に貪欲解を投げたらWAでびっくり.一応一瞬考えたらにぶたんでできそうだけど,B問題でにぶたんが出るわけないと思い,貪欲解を適当にいじって2回提出してもなおWA.しょうがないからにぶたん書いてACしました.(B問題でにぶたんが出るようになったんだなぁ)
#include<iostream>
using namespace std;
 
bool check(int n, int maxi){
  for (int i = maxi; i > 0; i--) {
    if(n >= i){
      n -= i;
    }
  }
  return (n == 0);
}
 
int main(){
  int n;
  std::cin >> n;
  int l = 0, r = n, mid = (r + l)/2;
  while(r - l > 1){
    if(check(n, mid)){
      r = mid;
    }else{
      l = mid;
    }
    mid = (l + r)/2;
  }
  for (int i = r; i > 0; i--) {
    if(n >= i){
      std::cout << i << std::endl;
      n -= i;
    }
  }
  return 0;
}
  • C問題Interpretation
    $M$種類の言語があり,$N$人の人がいます.それぞれの人が喋れる言語が与えられるので任意の人が喋れるかどうかを判定しろという問題です.通訳を頼んでもいいのである人AとBが共通に喋れる言語がなくても,AともBとも喋れるCさんがいればOKという問題です.
    これは$N + M$のサイズの二部グラフ作って,グラフの連結性を判定すれば良いので結構簡単.
#include<iostream>
#include<vector>
using namespace std;
 
void dfs(vector<vector<int> > &g, vector<bool> &used, int v = 0){
  used[v] = true;
  for (int i = 0; i < g[v].size(); i++) {
    if(used[g[v][i]] == true)continue;
    dfs(g, used, g[v][i]);
  }
}
 
int main(){
  int n, m, k;
  std::cin >> n >> m;
  vector<vector<int> > l(n + m);
  for (int i = 0; i < n; i++) {
    std::cin >> k;
    for (int j = 0; j < k; j++) {
      int tmp;
      std::cin >> tmp;
      l[i].emplace_back(tmp - 1 + n);
      l[tmp - 1 + n].emplace_back(i);
    }
  }
  vector<bool> used(n + m, false);
  dfs(l, used);
  bool flag = true;
  for (int i = 0; i < n; i++) {
    flag &= used[i];
  }
  std::cout << ((flag == true)?"YES":"NO") << std::endl;
  return 0;
}
  • D問題 Pair Cards
    この辺から結構難しく感じました.ある種の最大マッチング問題としても解けるけど,一般のグラフの最大マッチングは頂点数$N$に対して,$N^{2.5}$が最速だったと思うので,どう考えても無理.(しかも1,2時間で実装できるわけがない).なので,制限されたグラフクラスのマッチングなのかと思い,グラフを書いてたりしてたら,整数の和が$M$になるようなペアを作りたいので,与えられた整数を$M$でmodをとって,その値が同じなら同じ整数と考えてもいいことに気づく.なので,後は$M$でmodとった値が$i$の整数と$M- i$の整数をペアにしていけばいいことがわかる.ただし,まだ同じ整数のペアの数は考慮できていないので,この方法でペアを作って,余った整数で同じ整数があったらそのカード同士をペアにする必要がある.
#include<iostream>
#include<vector>
#include<set>
using namespace std;
 
int main(){
  int n, m, maxi = 0;
  std::cin >> n >> m;
  vector<int> x(n);
  for (int i = 0; i < n; i++) {
    std::cin >> x[i];
    maxi = max(maxi, x[i]);
  }
  vector<int> mod(m, 0);
  for (int i = 0; i < n; i++) {
    mod[x[i]%m]++;
  }
  int ans = 0, tmp;
 
  for (int i = 1; 2*i <= m; i++) {
    if(2*i == m){
      tmp = mod[m/2]/2;
      ans += tmp;
      mod[m/2] -= tmp*2;
    }else{
      tmp = min(mod[i], mod[m - i]);
      ans += tmp;
      mod[i] -= tmp;
      mod[m - i] -= tmp;
    }
  }
  tmp = mod[0]/2;
  ans += tmp;
  mod[0] -= tmp*2;
  vector<int> s(maxi, 0);
  for (int i = 0; i < n; i++) {
    s[x[i]]++;
    if(s[x[i]] >= 2 and mod[x[i]%m] >= 2){
      s[x[i]] -= 2;
      mod[x[i]%m] -= 2;
      ans++;
    }
  }
  std::cout << ans << std::endl;
  return 0;
}
  • E問題Cookies
    この問題はコンテスト中は部分点しか取れなかったです.制約を見て,dpなら部分点は取れると思い,dpの方針で考えてました.考えたいたdpは「ちょうど$k$枚のクッキーを焼くのにかかる時間は何分か?」というdpを考えました.コードはこんな感じです.
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
typedef long long int lli;
 
int main(){
  lli n, a;
  std::cin >> n >> a;
  vector<lli> cost(n + 1, 1e9);
  cost[0] = 0;
  cost[1] = 1;
  for (lli i = 2; i <= n; i++) {
    cost[i] = min(cost[i], (lli)i);
    for (lli j = 2*i; j <= n; j+=i) {
      cost[j] = min(cost[j], cost[i] + j/i + a);
    }
  }
  lli ans = n;
  for (int i = 1; i <= n; i++) {
    ans = min(ans, (lli)(ceil(n/double(i)) + cost[i] + a));
  }
  std::cout << ans << std::endl;
  return 0;
}

とりあえずこれで$O(N log N)$にはなっているとおもいます(計算量解析はあまりきちんと考えていないけど多分あっている気がする.)コンテスト中はここまでしかわかりませんでした.

コンテスト後,解説を見ながら「頭いいなぁ」と感心しながらコードを書いて次のコードでACしました.コードがpythonなのはC++でオーバーフローを機にするのが面倒だったのでpythonで書きました.

#!/usr/bin/env python
# -*- coding: utf-8 -*-
 
def pow(a, b):
    if b == 1:return a
    if b%2 == 0: return pow(a*a, int(b/2))
    return a*pow(a*a, int(b/2))
 
def binaryOne(n, multi):
    l, r = 0, n
    mid = (l + r)/2    
    while r - l > 1:
        if pow(mid, multi) >= n:
            r = mid
        else:
            l = mid
        mid = (r + l)/2
    return r;
 
 
def binaryTwo(n, maxi, multi):
    l, r = 0, multi
    mid = (l + r)/2
    while r - l > 1:
        if pow(maxi, (multi - mid))*pow(maxi - 1, mid) >= n:
            l = mid
        else:
            r = mid
        mid = (r + l)/2;
    return l
 
n, a = map(int,raw_input().split(" "))
ans = 1e18
for i in xrange(0, 40):
    maxi = binaryOne(n, i + 1);
    subt = binaryTwo(n, maxi, i + 1)
    ans = min(ans, a*i + maxi*(i + 1) - subt)
    
print ans

今年もパーカーをゲットできたので非常に良かったです.今年はパーカーラインが去年より高めで,半分くらいの人しかパーカーをもらってなかったぽいです.

ビームスタックサーチ

この前,ビームサーチを書いてみたので,今度はビームスタックサーチを書いてみました.この辺のサイトを参考に勉強しました.

このサイトに載っているchokudaiさんのスライドが(ビームサーチをわかっている人なら)結構わかりやすいと思いました.ビームスタックサーチは僕なりの理解として,ビーム幅を増やしながら何回もビームサーチを行うのだが,今までのサーチ中で探索したノードを記憶しておいて,一度探索した部分は探索しないようにしているようなビームサーチという感じです.ビームサーチで厄介(らしい)ビーム幅の設定を色々頑張らなくとも,探索時間をこちらで設定すればその時間内で,頑張れるだけ勝手にビーム幅を増やしてくれるので,楽ができるという利点があるようです.

解いた問題はナップサック問題で,計算時間を2秒で設定して計算しました.コードはこんな感じです.

確かにビームスタックサーチの方が計算時間を設定できる分使いやすそうだという印象でした.