計画性
自分はすごく計画性がないなとおもっているんだけど、最近すこしづつ計画性がついてきたとおもっていて、それでも人から期待される程度の1割以下だとおもっているので、自分の成長を自分でほめて、且つ、人には申し訳ない感じなので、大変こころがつらい。
ヒューリスティックな彩色
k-degenerationグラフの順序で彩色してやれば、最大出次数+1以下で彩色できるのだけど、1点を除いて、最小最大出次数が2以上減る場合は彩色数が減るなと思った。
あと平面グラフで彩色数がk(≧4)のときに、頂点を追加して、色がkの頂点とその隣接点全部に接続したグラフを作って、それを彩色してやるとkになって間違っていることがわかるとかないかなとかおもった。
最大出次数を最小にする順序/Rubyのpriority queue
以前、この記事で最大出次数を最小にする順序は難しいかもと書いたけどできるらしい。
Degeneracy (graph theory) - Wikipedia
アルゴリズムも載っていたのだけれど、優先度を変更できる優先度付キューをつかうと簡単にできそうだった。
Rubyの優先度付キューを探してみると標準では優先度付キューはないようだ。lazy priority quueuというgemがあって、この中でベンチマークがある。
優先度変更がなくてよいならPriorityQueueCxx、 変更有りならsupertinou/PriorityQueue、どちらもC++ extensionなので、Pure Rubyならlazy_priority_queueがよいよとのこと。
サンプルやコードを見ていると、なるほど優先度を高くする方向(min heapでは、値としては下がる方向)はサポートできるみたいな感じっぽい。
ヒープのデータ構造に違いがあり、lazy_priority_queueは2項ヒープとのこと、フィボナッチヒープと比べると、フィボナッチヒープの方が平均的には早いけど、ワースト時間で遅いものがあるみたいな感じっぽい。さきのC++拡張の2つともフィボナッチヒープ。
多分2007年度の卒業論文(学部生)じゃないかと思うんだけど、グラフの彩色アルゴリズムの内容も基本的にはk-degenerationグラフの順序を求めているのと一緒だった。強いてあげるならば、なるべく次数降順に並ぶように順序を決めていた。
自分としてはここに安定結婚問題をもってきたいとおもっていて、適当につくったのが、結構いい値がでてて、精度保障できないかなとか思ってるけど、全然証明とかできない。
貪欲法と違うのは基本的に1色で塗れるだけ塗るというのをやってる。安定結婚問題に合わせて色を男性、頂点を女性とすると、貪欲法だと女性優先で、下記のコードだと男性優先なんじゃないかとおもっているが実際には貪欲法と変わらない。なんというか、うまいこと頂点毎の順序や色ごとの順序つくれないかなとおもっている。なんで安定結婚問題でやりたいかといえば、マッチングの質に関しての研究が進んでいるからというのが理由。意外と順序決めるのが早かったりしないかなとおもっている。
#!/usr/bin/env ruby require 'lazy_priority_queue' require 'optparse' def degeneracy_order(graph, vset) q = MinPriorityQueue.new k = 0 order = [] used = {} d = {} vset.each do |v| dv = graph[v].size d[v] = dv q.push v, dv end until q.empty? v = q.dequeue used[v] = true k = d[v] if d[v] > k order << v graph[v].each do |u| d[u] -= 1 unless used[u] q.change_priority u, d[u] end end end order.reverse end def build_graph(vset, eset) graph = {} vset.each do |v| graph[v] = [] end eset.each do |u,v| graph[v] << u graph[u] << v end graph end def gs_coloring(graph, vset_order) match = {} c = -1 until vset_order.empty? c += 1 vset_order.reject! do |v| if graph[v].none?{|u| match[u] == c } match[v] = c end match[v] end end [c + 1, match] end opt_result = false opt = OptionParser.new opt.on('-r','print result.'){ opt_result = true } opt.parse!(ARGV) n,m = gets.split.map(&:to_i) V = n.times.to_a E = m.times.map{ gets.split.map(&:to_i) } G = build_graph(V,E) vset_order = degeneracy_order(G, V) number, result = gs_coloring(G, vset_order) puts number puts V.map {|v| "#{v} #{result[v]}" } if opt_result
最大クリーク問題(改)
最大クリーク問題をいま全面的に書き直していて、すごくおもしろいアルゴリズムになった。
補グラフを彩色して、各色の頂点数を数えて最大のものが最大クリークの下限になる。この下限を使用して元グラフで頂点、辺を落としていく。
補グラフをk彩色できたら、かけてで色クラスを2つ選んで最大マッチングで最小頂点被覆を求めて、最大独立集合を求めて少しずつ大きくしていく。
もしk=2になったら確定する。
k≧3から落ちなければ、微妙。ただ、ある程度の大きさまで来たら、補グラフの連結性を判定して細切れの補グラフ連結成分の元グラフのクリークサイズで足し合わせることができるので、そこがカーネルになるなら、それはそれであり。
補グラフを彩色するのは最適彩色じゃなくてよいので、Welsh-Powellの貪欲彩色とか、外部性のある安定結婚問題とかで解ける。
むしろ最適だとn/kに近くなっちゃうので、頂点数最大になるような方法の方がよい。まあ、その方法はNP完全なんだけどね。
続(4) - 最大クリーク問題
多分4じゃないかと思う。ナンバリングは適当
グラフが非連結でk個のグラフに分割できるとして、n(頂点数),m(辺数),w(補グラフの辺数)と分割後の各n,m,wをとすると下記が成り立つ
補グラフが非連結も同様
すげぇコンパクトになるんですけどって感じだ。
これが何につながるかというと最大クリーク問題なわけで、例えば頂点数100で、補グラフがのような非連結のグラフのとき、元のグラフではサイズ50のクリークが個あるわけだけど、補グラフで考えると一気に頂点2 * 連結成分50の問題になる。
とはいえ、きっとよく知られた内容だとおもうんだけど、自分的にはこれは結構すごいなと感動した。