2017-03-10

Brooksの定理++

無向グラフGの頂点を適当に順序付けして、辺の両端 $i, j$ が $i \lt j$ なら、 $i \leftarrow j$ へ方向付けした有向グラフをHとする。
Hの最大出次数 $\Delta_+(H) = k$ のとき、Gはk+1彩色可能で、これはBrooksの定理を含んで、より上限を押さえるとおもってるんだけど、~~既知なのかがわからん~~。

これは既知だった。これはk-degenerate graph(縮退)というらしい。
Degeneracy (graph theory) - Wikipedia

証明自体はたぶん正しいとおもう。

n頂点からなる単純な無向グラフを $G$ とし、 $G$ に頂点 $v$ を一つ追加したグラフを $G'$ とする。
$G$ の彩色数 $\chi(G) = k$ の時、 $\chi(G')$ は、 $v$ の次数 $d(v)$ により次のいずれかとなる。

$\chi(G')=\begin{cases} k+1 & ( d(v) = n ) \\ k+1 \text{ or } k & ( d(v) \ge k )\\ k & ( d(v) \lt k ) \end{cases}$

証明については下記リンク先を参照*1
kousuke.hatenablog.com

これは結局、グラフに1点追加したとき、彩色数は2つも3つも上がらないし、接続する次数が彩色数未満なら確実に上がらないし、全点に接続すれば1上がるし、その間はよくわからんということに他ならない。ただ、グラフGをある空間から別の空間に頂点を一つずつ移動していくようなオペレーションを考えれば、移動先の彩色数と移動する頂点の辺の片側(移動先側)だけ見ていればよい、そうすればおよそ上限がわかってくるよということになる。

単純な無向グラフGの頂点集合Vを順序付ける写像fを用意する。
$f: \{ \> i \in \mathbb{N}_0 \> | \> i \lt |V| \> \} \rightarrow V$

$f(i)=v$ である頂点を $v_i$ と書くことにする。

無向グラフGから有向グラフHへの変換を $h: G \rightarrow H$ とする。

$h: \{ \> \{u,v\} \in E \> \} \rightarrow \{ \> (v_{src}, v_{dst}) \in V \times V \> | \> src \gt dst \>\}$

hはfにより辺の向き(i > jならi -> jの方向)が一意に決まることを示している(つもり)。
$V_n = \{ v_0, v_1, \dots, v_{n-1}\}$ とし $V$ から $V_n$ を除く差集合 $V \setminus V_n$ を ${V_n}^c$ と書く。

$G,\> H$ の $V_n$ による誘導部分グラフ $G[V_n] ,\> H[V_n]$ を $G_n ,\> H_n$ 、また $G ,\> H$ から $G_n, H_n$ を除く部分グラフ $G \setminus G_n, H \setminus H_n$ を ${G_n}^c,\> {H_n}^c$ と書く。

頂点vでの次数、出次数をそれぞれ $d(v),d_+(v)$ 、最大次数、最大出自数については $\Delta(G),\Delta_+(H)$ と書く。 ${G_n}^c,\> {H_n}^c$ に対しては、 $\Delta({G_n}^c)=\max \{ \> d(v), v \in {V_n}^c \> \}$ , $\Delta_+({H_n}^c)=\max \{ \> d_+(v), v \in {V_n}^c \> \}$ である。

最初の式を書きなおすと以下のようになる。 $\chi(G_n)=k$ とする。

$\chi(G_{n+1}) - \chi(G_n) = \begin{cases} 1 & (d_+(v_n) = n)\\ 1 \text{ or } 0 & (d_+(v_n) \ge k)\\ 0 & (d_+(v_n) \lt k) \end{cases}$

後続の頂点の出次数がすべて彩色数未満であれば、彩色数はもう上がらないことがわかる。よって次式が成り立つ。

$\chi(G_n) > \Delta_+({H_n}^c) \Rightarrow \chi(G_n) = \chi(G)$

n = 0のとき、 ${H_n}^c = H$ なので、 $G$ は $\Delta_+(H)+1$ で彩色可能なことがわかる。

さて $\chi_{n}$ を $\chi_{n} \ge \chi(G_n)$ を満たす数列とすれば、ステップ関数 $u(x)$ を使用して、もうすこし精度よく上限を求めることができる。

$\begin{cases} \chi_{n+1} - \chi_{n} = u(d_+(v_n) - \chi_{n}) \\ \chi_0 = 0 \\ \end{cases}$

$u(x)=\begin{cases} 1 & (x \ge 0) \\ 0 & (x \lt 0) \end{cases}$

計算量はHに対して $O(|V|)$ ででき、上限は最悪でも $\Delta_+(H)+1$ で抑えることができる。

いままでの内容を例としてまとめるとこんな感じになる。(n=4の時の図)
f:id:tinsep19:20170320145321p:plain

$n$	0	1	2	3	4	5	6	7	8
$\chi(G_n)$	0	1	2	3	4	4	4	4	4
$d_+(v_n)$	0	1	2	3	2	2	2	3	-
$\Delta_+({H_n}^c)$	3	3	3	3	3	3	3	3	-
$d(v_n)$	3	4	3	7	4	3	3	3	-
$\Delta({G_n}^c)$	7	7	7	7	4	3	3	3	-
$\chi_n$	0	1	2	3	4	4	4	4	4

まずブルックスの定理での彩色数の上限が $\chi(G) \le 8(= \Delta(G)+1)$ なのに対して、 $\chi(G) \le 4(= \Delta_+(H)+1)$ で抑えられていることがわかる。

次にn=4のとき、既に彩色数は4となっていて、後続の出次数はすべて4未満になっている。また実際に彩色数も上がっていないことがわかる。

結局、次数が高い頂点があっても、それが1つしかなければ、ほとんど彩色数には寄与しない。
例えば、頂点を次数降順でソートすると $d(v_n) = \Delta({G_n}^c) \ge \Delta_+({H_n}^c)$ となるが一番次数の大きい頂点は $v_0$ でその出次数は $d_+(v_0) = 0$ となり、彩色数を0から1にするだけになる。むしろ重要なのは次数降順の場合、 $\chi(G_n) \gt d(v_n)$ となるような部分グラフ $G_n$ で全体の彩色数を求められるということだとおもう。

頂点の順序を変えると出次数も変わってしまうので出次数を抑えるような順序を探すのは難しいかもしれないが、次数であれば簡単になる。ちなみに次数降順とした際に、n=0を考えるとBrooksの定理と一致することもわかる。

現在、厳密に彩色数を求める計算量は $O(2^nn)$ らしいけど、頂点半分で求まるなら実際の時間はかなり減る。彩色数の下限にあたりをつけて少しずつ増やしていくのがよさそうな戦略に思える。

そこで重要になるのが、ヒューリスティックな方法で、今回の例では $\chi_n$ が彩色数と一致している。順序によっては4以上となることもあるのだけれど、上限はかなり抑えられている。

貪欲彩色のWelsh-Powellのアルゴリズムに比べると実際に彩色するかしないかの違いがある。ただ単に彩色数を近似したいときは今回紹介したほうが便利で、実際に彩色した結果がほしいのであればWelsh-Powellの方が便利。

$\chi_n > d(v_n)$ となった時点で、いったん厳密な彩色数を求めて $\chi_n$ を更新して、もう一度 $\chi_n > d(v_n)$ となった時点でもう一度というような方法で時間的には短縮できるんじゃないかとおもっている。

その他

例えば、ソーシャルグラフのような次数がパレートの法則に従うようなグラフだと、ロングテール部分の次数は小さそうなので、そうするとヘッドの部分を調べるなかで結構テールの頂点を削れるとおもう。逆に次数があまり分散してなくて、大きなクリークがないのが一番大変ということになりそう。

シャープレイ値がやはり気になっていて、彩色数は劣加法性があるので符号を反転して、優加法性をもたせてシャープレイ値やその固有ベクトルに何かつながらないかなとおもっている。
位置エネルギーがスケールが大きくなったときに無限遠を0にして、符号がマイナスになったような感じで物理学的なロマンにときめいている。

追記

Welsh-Powellの貪欲彩色だと実際に彩色していくけど、彩色せずに進めるとステップ関数使ったやつみたいになりそう。ちなみに手元でいろいろためしたところ、次数降順が安定して彩色数が小さく出る。予想してたけど1000頂点10彩色可能なものが次数降順だと13ででていたけど、適当にシャッフルしたやつだと23くらいがよくでる。

また上記の近似解kを使ってgales-sharpleyの変形で外部性のある安定結婚問題として解くとk以下の彩色が求められる。
計算量は $O(k^2(|V| + |E|))$ だとおもうけどこれは少し怪しい( $k^2$ で収束するかが微妙)。

外部性があってもDA方式(受入保留方式/gales-sharpleyのアルゴリズム)で安定マッチング(ペア安定マッチング)はあることがわかっているけど、グループ安定性を満たさない、耐戦略性を満たさないというのが下記論文に書いてある。

~~外部性のある一対多マッチングの安定性~~

*1:いろんな文書の中で見かけるんだけど、ちゃんと定式化?されてるのをみたことがない気がする

2017-02-21

winptyってすごいんだな

SourceTree付属のgit-bashが便利で使ってるんだけど、rubyのirbとかつかうと何か変になってるなぁって思ってたんだけど、winpty ruby -S irbで起動すればよいことに気が付いた。pryとかもこれでよくなるのかな。

2017-01-17

Facebookは恐ろしいよね。

jp.techcrunch.com

昔からプラットフォームとしてのFacebookが好きで、特に自分の予想として次のThe Next Webはコミットメントをあつかう、その信用情報などの担保としてのSNSというのに興味があって、過去にこんな記事を書いていたのだけれど、同じようなことが書いてある記事があって割と嬉しい。

そして法整備や認識が熟成されていくのは結構時間が掛かるんだなと実感している。当時、技術で足りない部分もあったとはおもうけどそれは過去記事をかいた時点でも乗り越えられたとおもうんだよね。

そしてやはりFacebookは一歩一歩進んでいて凄いなぁという感じである。

kousuke.hatenablog.com
kousuke.hatenablog.com

2017-01-13

最大クリーク問題　試行

いままでと全然変えてみてある辺(i,j)を含む、順序上 j以下の頂点で構築できる最大クリークとか考えてみた。
サイズcのクリークがある時、全点から接続している点はc+1のクリークって考えると凄くコンパクト。

でも2^cとか含むだろうけどね。

n,m = gets.split.map(&:to_i)
G = {}
U = {}
V = n.times.to_a
E = m.times.map do
    gets.split.map(&:to_i).sort
end
E.sort!

V.each do |v| 
   G[v] = []
   U[v] = [] 
end
E.each do |from, to| 
    G[from] << to
    G[to] << from
    U[to] << from
end

MEMO = {}

def dfs(clique, c)
    clique.sort!
    s,t = clique.first, clique.last
    status = clique.join(' ')
    return MEMO[status] if MEMO[status]
    
    nclique = clique.inject(U[t]){|n, v| n & G[v] }.sort
    nc = nclique.empty? ? c : nclique.map {|nv| dfs(clique + [nv], c+1) }.max
    p clique: clique, c: nc
    MEMO[status] = nc
end

E.each do |e|
    puts "#{e} #{dfs(e, 2)}"
end

なんとなくこのコードが引っかかる。

再帰呼び出しc回でサイズcの極大クリークが見つかる、サイズcのクリークは2^c - 1個のクリークがあるけど、なんとなくうまく枝刈りするとサイズがcの極大クリーク(他のクリークに含まれないの意味)をc^2のオーダーで抜けれそうな気がするんだよね。

例えばこんな感じのコードかなぁ。

n,m = gets.split.map(&:to_i)
VISITED = {}

G = {}
V = n.times.to_a
E = m.times.map { gets.split.map(&:to_i).sort }

V.each {|v| G[v] = [] }
E.each do |from, to|
    G[from] << to
    G[to] << from
end

def dfs(clique, max)
    clique.sort!
    status = clique.join(' ')
    
    return max if VISITED[status]
    
    VISITED[status] = true
    
    if clique.size > max
        max = clique.size
        # p clique: clique, max: max
    end
    
    head, *body = clique
    nclique = body.inject(G[head]){|n, v| n & G[v] }
    if clique.size + nclique.size > max
        max = nclique.inject(max) {|m, u| dfs(clique + [u], m) } 
    end
    
    max
end

if n == 0
    puts 0
elsif m == 0
    puts 1
else
    puts E.inject(0){|max, e| dfs(e, max) }
end

下記入力に対して

こういう動き

{:clique=>[0, 1], :max=>2}
{:clique=>[0, 1, 2], :max=>3}
{:clique=>[0, 1, 2, 3], :max=>4}
{:clique=>[0, 1, 3], :max=>4}
{:clique=>[0, 2], :max=>4}
{:clique=>[0, 3], :max=>4}
{:clique=>[1, 2], :max=>4}
{:clique=>[1, 3], :max=>4}
{:clique=>[2, 3], :max=>4}
{:clique=>[0, 4], :max=>4}
{:clique=>[0, 5], :max=>4}
{:clique=>[0, 6], :max=>4}
{:clique=>[0, 7], :max=>4}
{:clique=>[4, 7], :max=>4}
{:clique=>[4, 5], :max=>4}
{:clique=>[5, 6], :max=>4}
{:clique=>[6, 7], :max=>4}

サイズcのクリークの全点から接続している点は必ずサイズc+1のクリークで、これまでに見つかった最大クリークのサイズをmaxとすると、サイズc+1のクリークがmax - c個より多く存在しないとmax + 1のサイズのクリークはないので枝刈ってみた。

Submission #1100279 - AtCoder Beginner Contest 002 | AtCoderの結果

これcarraghanのアルゴリズムっぽい。。。
https://www.jstage.jst.go.jp/article/ciqs/2006/0/2006_0_JP04/_pdf

2017-01-10

あけましておめでとうございます。

本年もよろしくお願いします。

昨年は最大クリーク問題で頭イタイ人に思われたりして、一時期、心を病んだ状態でしたが、すごく楽しかったなぁとおもっています。
ことしも全然やるつもりで、まさにブログ名どおりの高温処理済みになったなぁとおもっています。

2016-12-09

続: 最大クリーク問題

なんかいろいろやってこんな形に落ち着いた。

簡単にいうとまず適当にソートして、有向グラフに変換してDPする。
dp[j][c]はj以下の頂点を使用したjを含むサイズcのクリークの文字列表現の配列。
後続の頂点iからはこのクリークの頂点にすべて辺があれば、サイズc+1のクリークなのでdp[i][c+1]に追加する。
このクリークの頂点にすべて辺があればの部分は、rubyなので配列を&した、他の言語だとbitsetみたいなライブラリで行うほうがよいと思う。

belongs_max_cliqueは前回のソースを引き継いでいるので現在は適当ではないかもしれないけど、ある頂点vに隣接する誘導グラフから、最大クリークサイズをだす場合はbelongs_max_clique(G[v]) + 1とすればよいようになっている。

#!/usr/bin/env ruby

V, m = gets.split.map(&:to_i) # read Graph Infomation
G = {} 

# Initialize Graph
V.times {|v| G[v] = []}
m.times do 
  from, to = gets.split.map(&:to_i).sort
  G[from] << to
  G[to] << from
end


def belongs_max_clique(node = V.times.to_a, limit =  V)
  subgraph = {}
  node.sort!
  node.each_index{|i| subgraph[i] = [] }
  node.each_with_index do |u, i|
    i.times do |j|
      w = node[j]
      subgraph[i] << j if G[u].include?(w)
    end
  end
  
  dp = Array.new(node.size + 1){ Array.new(limit + 1){ [] } }
  node.each_index{|i| dp[i][1] << i.to_s }
  max_clique_size = (1 ... limit).find do |c|
    found_clique = false
    node.each_index do |i|
      subgraph[i].each do |j|
        dp[j][c].each do |clq|
          clique = clq.split.map(&:to_i)
          shared = clique & subgraph[i]
          if shared == clique
            clique << i
            dp[i][c + 1] << clique.join(' ')
            dp[node.size][c + 1] << clique.join(' ')
            found_clique = true
          end
        end
      end
    end
    !found_clique
  end
  max_clique_size || limit
end

puts belongs_max_clique

前回指摘をもらったグラフだとDPした結果は以下のようになる

[[], ["0"], [], [], [], [], [], [], []], 
[[], ["1"], ["0 1"], [], [], [], [], [], []], 
[[], ["2"], ["0 2", "1 2"], ["0 1 2"], [], [], [], [], []], 
[[], ["3"], ["0 3", "1 3", "2 3"], ["0 1 3", "0 2 3", "1 2 3"], ["0 1 2 3"], [], [], [], []], 
[[], ["4"], ["0 4"], [], [], [], [], [], []], 
[[], ["5"], ["0 5", "4 5"], ["0 4 5"], [], [], [], [], []], 
[[], ["6"], ["0 6", "5 6"], ["0 5 6"], [], [], [], [], []], 
[[], ["7"], ["0 7", "4 7", "6 7"], ["0 4 7", "0 6 7"], [], [], [], [], []],

入力はこんな感じ

dp[node.size][c]は別になくてもよいけど、サイズcのクリーク( c >= 2)の全列挙用につくっている。

こんな感じになる。

[],
["0 1", "0 2", "1 2", "0 3", "1 3", "2 3", "0 4", "0 5", "4 5", "0 6", "5 6", "0 7", "4 7", "6 7"],
["0 1 2", "0 1 3", "0 2 3", "1 2 3", "0 4 5", "0 5 6", "0 4 7", "0 6 7"], 
["0 1 2 3"]

追記: コメントに計算量のことを書いて質問をいただきました。現在のコードがc^2 * v * eかと言われれば、ご指摘の通りたぶん違うんじゃないかとおもってきました。ただ自分的にはc^2 * v * eにまでおそらく落とせると思っているのでそこまで計算量を落としたアルゴリズムを作りたいと思っています。

メモ: cのループをnodeのループの中に入れて、サイズcのクリークの全列挙をやめると計算量は落ちるな。でもやはりサイズcのクリーク数に依存しそうだから、サイズcのクリークの個数に対して、cかc^2になりそうかな。計算量は落ち着かないけど、これならできそう。

2016-11-30

最大クリーク問題

まだうまく証明できていないかもしれないけど、~~これで解けてると思う~~解けていないです。

別の実装を考えたのでコードを消しました。

kousuke.hatenablog.com

belongs_max_cliqueではある頂点を含む極大クリークのサイズを返していて、それを全点に対して行いその最大のものを出力している。

belongs_max_cliqueは任意の1頂点(v)とそれに隣接する頂点集合をUとすると、誘導部分グラフG[U]に対し、その次数をまず計算する。 Uの次数の少ないものから、順に切断していくと最終的に他の全ての点と同じ次数になるので、その時残っているグラフがvを含む最大クリークとなる。クリークのサイズは次数 + 1すればよい。

(証明)

最大クリークはそのグラフの頂点のどれかを含んでいる(自明)
ある頂点を選んでその頂点を含む極大クリークがわかれば、それを全点でおこなうことで最大クリークがわかる。(問題ないとおもう)
G[U]はvとvに隣接する頂点集合からなる誘導部分グラフであるので、vを含むクリークはすべて含まれる。(多分、自明)
G[U]はvとvに隣接する頂点集合からなる誘導部分グラフであるので、vの次数は必ず他の頂点の次数以上である。(Uの頂点数がnならG[U]の頂点の次数はn-1より大きくなることはなく、vの次数はn-1)
G[U]が完全グラフ(Kn)のとき、その全ての頂点の次数はn-1となり、頂点数はnとなり、停止条件となる。(n-正則グラフの場合があり、判定できてない)
G[U]からvの次数未満の最小の次数をもつ頂点を1点切断した頂点集合をU'とするとG[U']も必ずvを含む極大クリークが含まれる。(問題あり)
U'をUとして5に戻っても矛盾はない。(問題ないとおもう)

以上より、このアルゴリズムは停止条件をもち、有限時間内に停止する。またその時、このグラフに含まれる極大クリークのうち、最大のサイズを示す。

計算量はちょっと自信がないけど、頂点数をv , 次数の平均をdとすると O(v * d^2) じゃないかとおもう。次数の平均はE / VなのでO(E^2 / V)かな。

以下、コーナーケースとして指摘されそうな例

G[U]が2つの完全グラフ(Kn,Km)を含み、その節点がvのとき、vは次数n+m - 2をもち、vを除くKn,Kmに含まれる点はそれぞれn-1,m-1の次数をもつ。
- n < mのとき、Knの点から順に切断され、最終的にKmだけ残りすべての頂点がm-1の次数をもつ。
- n = mのときはvをのぞく全ての点がn-1の次数を持ち、そのうち1点を切断することで、n < mと同じ状況になる。
G[U]が2つの完全グラフ(Kn,Km)を含み、vを除くKn,Km上の点を結ぶ接続がある場合も、上記のケースでの切断する順序に変化があるだけで、同様に最大クリークを返す。
G[U]が2つの完全グラフ(Kn,Km)を含み、vを除くKn,Km上の点にすべて接続がある場合、それは完全グラフKn+m-1であり、同様に最大クリークを返す。

TODO: 課題

全ての次数が同じだけど、片側に完全Kn,もう片側にn-1正則グラフがある場合

@tinsep19 最小の頂点が複数ある時ってどれを選びますか（図で真ん中をvとして選んだ場合） pic.twitter.com/Lh7lLTTMwG
— (nは自然数) (@n_vip) December 1, 2016

@n_vip 興味持っていただき。ありがとうございます。このケースだと現在の実装だと右側を消すとは限らないですね。
vを含む極大クリークが返されるとしている部分が間違っていますね。修正してまた挑戦したいとおもいます。
— TANIGUCHI Kousuke (@tinsep19) December 1, 2016

この状況を把握するのはおそらく無理、右側と左側にリンクがある場合もあるので、フローとかで優先順位を確定できない限り難しい。もしかすると現在の実装でも、それなりに正しいものを出すかもしれないけど、コーナーケースのデータは否定できない。

- 案1. V.each前にsortするかbelongs_max_clique内のsortでabsを使用しているが、これを変えて、全体の順序のなかで順序付けして、整合性が取れるようにする。もしくは現在の状況で整合性がとれていることを示す必要がある。

- 案2. 完全グラフかどうかはキーの数 = 次数 + 1かどうかで判定できるので、そうでない場合はスキップする。この場合も全体のなかで整合性が取れている必要がある。もしくは優先順位を変えて再度実施する。

とりあえず完全グラフかどうか頂点数と次数で判定して、正則グラフの場合は-1を返すようにしてみた。ただ全体の整合性がとれるのかというと違う。もちろん右側と左側の別の頂点でbelong_max_cliqueは呼ばれるけど、全ての頂点がn-正則グラフと隣接しているというような状況はある。