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:plain

f: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:plain

f: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.6181ⁿ) なので， chordal graphではminimal separatorの数がすごく少なくなるのが知られています．一般のグラフでのMinimal separatorの数の上限についてはここを参照してください．

2017-11-03

Chordal Graph

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

Twitter ID: kazu0x17

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

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

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

Minimal vertex separators
Perfect elimination ordering (PEO)
Maximum cardinality search (MCS)
Lexicographical breadth first search (Lex BFS)
Potential maximal clique
Simplicial vertex
Clique tree
Tree width
Cops and Robber game

2016-12-03

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

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

2016-12-03

ビームスタックサーチ

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

chokudaiサーチのメモ

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

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

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

2016-11-28

Code Festival 2016に参加しました

今年もCode Festivalを開催していただけて（しかも，本戦まで行けて）本当に楽しかったです．問題セットも良問ぞろいでした．下の方に今回解いた問題セットがあるのですが，どのコンテストでも1問以上はこの問題考えた人頭いいなと思う問題があってすごかったです．結果は220人中98位だったのでかなりいい感じかと思います．しかも，今回はいつも負けている人に初めて勝つことができたのがいい記念になりました．（しかもきちんとパーカーもゲットした）．実は問題文を読んですらいない問題や，制約見てできそうだけどよくわからんといって投げた問題が結構あるので，後で解いて自分なりの解説をしてみたいです．問題セットはこんな感じでした．

本戦セット 10問
エキシビションセット 2問
朝トーナメント 1 2 3 各2問
リレー 11問

今年は壇上で表彰されたいなぁとかひそかにに思ってたので，一番可能性たかそうなcsenryuにbrute force attackしてみたけど，DEGwerさんに大賞を取られてしまったのはちょっと悲しい．

2016-11-13

初めての機械学習

なんやかんやあって初めて機械学習のアルゴリズムを実装しました．機械学習アルゴリズムの実装といっても大したことなくて，PRLMという教科書の最初にある多項式フィッティングというものを実装してみました．点が$N$点与えられるので誤差関数$E(\vec{w})$を最小化する$M$次多項式求めるというアルゴリズムです（入力は$N$個の点$x$と，整数$M$，出力はベクトル$\vec{w}$）．誤差関数$E(w)$は次の二乗誤差の関数を使いました．

$E(\vec{w}) = \Sigma_{n = 1}^{N} (y(x_n, w) - t_n)^{2}$

解説は次のページがわかりやすかったです．（僕が読んだ教科書と同じ教科書を読んで解説記事を書いていてくれたので，）

点(2 4), (9 1) ,(3 8), (-1 3) (4 -2) (-3 2) (-9 4)で， $M = 7$の場合 f:id:chocobaby-aporo:20161113012123j:plain $M = 5$の場合 $M = 3$の場合

$M = 5$がなんか一番いい感じですね．

2016-11-12

ビームサーチ

研究室の後輩がマラソンに出るというので一緒に参加してみようかと思いました．ただ，まだ運営がvisualizerを用意してくれないので，とりあえず練習のため，ビームサーチを実装してみました．ビームサーチは名前は聞いたことがあるけどよくわからないアルゴリズムという印象でした．

ググると色々情報が出てくるのでとりあえずこの辺りのサイトを参考にしました．

要は幅優先探索をするんだけど，ただやると計算が終わらないから，それぞれの探索木の深さで評価値がTOP $k$のノードだけ探索を続けようという結構簡単なアルゴリズムでした．練習用にAOJの0-1ナップサック問題をビームサーチで解いてみました．コードはこんな感じです．

数十秒の計算時間がかかるくらいにビーム幅を設定すると最適値*0.9くらいの答えを出してくれるのでそんなに悪くない印象を受けました．ただ，この問題は評価関数簡単だからいいけどもっと複雑な問題は色々厳しそう．

あとはビームサーチをランクアップさせた探索アルゴリズムとしてchokudaiサーチ(正式名称 beam stack search)というのがあるのでそれも勉強しておこう．．．

アルゴリズムは実装してみると色々発見があって面白いです．

kazu0x17’s diary

Chordal Graph: Minimal vertex separators