K4の対辺を繋ぐグラフにしてみる

の各辺を頂点にして、その完全マッチングの対に辺を引くという変換をおもいついて、やってみたら面白かった。 → 1頂点 → 3頂点、辺無し → 6頂点、3本の辺 → petersenグラフ → 正則グラフ → 正則グラフ Rの右肩が次数、右膝が頂点数。たぶんあってるとおもう…

計画性

自分はすごく計画性がないなとおもっているんだけど、最近すこしづつ計画性がついてきたとおもっていて、それでも人から期待される程度の1割以下だとおもっているので、自分の成長を自分でほめて、且つ、人には申し訳ない感じなので、大変こころがつらい。

ヒューリスティックな彩色

k-degenerationグラフの順序で彩色してやれば、最大出次数+1以下で彩色できるのだけど、1点を除いて、最小最大出次数が2以上減る場合は彩色数が減るなと思った。あと平面グラフで彩色数がk(≧4)のときに、頂点を追加して、色がkの頂点とその隣接点全部に接続…

最大出次数を最小にする順序/Rubyのpriority queue

kousuke.hatenablog.com以前、この記事で最大出次数を最小にする順序は難しいかもと書いたけどできるらしい。Degeneracy (graph theory) - Wikipediaアルゴリズムも載っていたのだけれど、優先度を変更できる優先度付キューをつかうと簡単にできそうだった。…

最大クリーク問題(改)

最大クリーク問題をいま全面的に書き直していて、すごくおもしろいアルゴリズムになった。補グラフを彩色して、各色の頂点数を数えて最大のものが最大クリークの下限になる。この下限を使用して元グラフで頂点、辺を落としていく。補グラフをk彩色できたら、…

P≠NP予想が嫌い

P≠NP予想 - Wikipedia 多くの研究者が長年にわたって多項式時間オーダーのアルゴリズムの開発に取り組んでいるにもかかわらず、そのような効率的なアルゴリズムは見つかっていない。このことがP≠NP予想の根拠の一つとなっている。 別にP=NPでもP≠NPでもどっ…

続(4) - 最大クリーク問題

多分4じゃないかと思う。ナンバリングは適当 グラフが非連結でk個のグラフに分割できるとして、n(頂点数),m(辺数),w(補グラフの辺数)と分割後の各n,m,wをとすると下記が成り立つ 補グラフが非連結も同様 すげぇコンパクトになるんですけどって感じだ。これが…

巡回セールスマン問題

最大クリーク問題は改善があって、これでいいってところまで来たので一旦終わり。 巡回セールスマン問題でなんとなくアイデアが湧いて、葉指定 + k-best最小全域木問題に帰着できないかな?とおもっている。 ハミルトン閉路から一本辺取り除いたら道だけど、…

最大クリーク問題の現在

Dinkelbach algorithmは強多項式/超一次収束らしいけど、探索部分にワーストケースでがはいってるし、指数の底もまだ1にできていないのでまだ多項式時間じゃない。大まかには頂点問題を、辺の問題に変換して、貪欲法。アウトラインは全部このスライドにあっ…

最大クリーク問題で面白いなとおもったこと

いろいろ考えてるけど、最大クリーク問題は主に3つの関数からなる。 ある無向グラフGについてを最大クリークサイズを返す関数とする。f(w) : 補グラフが非連結で、頂点がn個に分けられているとする、そのとき元の誘導部分グラフをとすると g(m) : グラフが非…

補グラフでの最小頂点被覆ってなんだろう?

補グラフでの最小頂点被覆ってなんだろう?って考えてて、どの頂点を追加しても、それが極大クリークになる頂点集合かなとおもった話。ちがうかもしれない。

最大クリークの途中で補グラフが出てくる話

kousuke.hatenablog.com 前回、ワーストケースでになると書いた。FPTでの幅はほぼ極大グラフの数でよいとおもっているけど、それをなぜ補グラフでやろうとしているか? 簡単に言うと補グラフに辺があれば、極大集合が2つ以上あるから。最大クリーク判定の式を…

最大クリークの計算量とか(続き)

kousuke.hatenablog.com 大事なことに気が付いたので、前回の修正。単純な無向グラフに対し、をサイズkのクリークが含まれるかどうかを判定する関数とする。グラフGに自身を除く全頂点に接続する頂点がある場合、それらは必ず最大クリークに含まれる。そのよ…

グラフと補グラフの関係

kousuke.hatenablog.comn頂点の完全グラフを、独立グラフ(頂点のみで辺がないグラフ)をとする。n頂点のグラフがある。 このときからへひとつづつ辺を消していく順序集合のうち、を含む順序の集合を定めることができる。このときのどの順序を通ってもの補グラ…

P=NPだと夢がある。

kousuke.hatenablog.com 頂点に関しては極大グラフが1つになるまでは(底を小さくするという意味ではもう少し改善はあるのだろうけど)、たぶん最速だとおもう。あとは補グラフの辺数wをなるべく少なく消しながら、進めばよい。 これは一緒に補グラフの最大独…

最大クリークの計算量とか

修正しました。 kousuke.hatenablog.com (以下、古い内容)をサイズkのクリークが含まれるかどうかを判定する関数とする。(0: 含まない or 1 : 含む)最大サイズkのクリークを含む、単純な無向グラフがあるとする。頂点vに隣接している頂点の集合をとし、に対…

続々々 最大クリーク問題(2)

すこしコードを変更している。興味ある人はpaiza.ioで動かしてみてほしい。 https://paiza.io/projects/14TYw6RR2KIPBLRjSNCPrgV=1000、E=9988、20彩色可能、最大次数 69、次数の分布具合は下記のグラフを参考。 最大クリークは8。列挙しているわけではない…

続々々 最大クリーク問題

基本的には前書いた内容。 kousuke.hatenablog.com1000頂点20彩色可能なグラフ(|V|=1000,|E|=9988)から最大8クリーク探すのにpaiza.ioで1.85秒たぶん正しいとはおもうんだけど。 動作 0. 頂点数、辺数を確認して、0,1,2は確定させる。あとは3から最大次数で…

UnionFind木(簡易版/ruby)

すこし忘れていたのでメモ rootで親をつなぎかえるのが肝。 class UnionFind < Array def initialize(n) super(n){|i| i} end def root(i) self[i] == i ? i : self[i] = root(self[i]) end def unite(i,j) self[root(i)] = root(j) end def same?(i,j) root…

ハドワイガー予想って

lealgorithm.blogspot.jp をマイナーとして含まないグラフは t-彩色可能 なのでしょうか? もしかして対偶とって、t彩色可能でなければ、少なくとものマイナーを含むにすればよい?だとするとそれに含まれる臨界グラフの頂点は全て次数t以上で、頂点数はt+1以…

最大クリークの。。。

最大クリーク数をcとすると、の確率で最大クリークと一致する順序が得られるのか。。。同じサイズの極大クリークあればもっと良い確率になるけど。。とりあえず下記でできる気がしてきた。1. サイズcのクリークは次数c-1以上の頂点がc個必要(条件A)なので、…

縮約していいのかな?

kousuke.hatenablog.com上記ポストの中で下記のような式がわかったわけだけど、この左辺のの部分を縮約してよいのだろうか?という疑問がいま頭をよぎっている。 基本的にはなら影響しないので、が接続する頂点の内、最大の頂点が彩色数を上げた頂点の場合、…

Brooksの定理++

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

winptyってすごいんだな

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

Facebookは恐ろしいよね。

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

最大クリーク問題 試行

いままでと全然変えてみてある辺(i,j)を含む、順序上 j以下の頂点で構築できる最大クリークとか考えてみた。 サイズcのクリークがある時、全点から接続している点はc+1のクリークって考えると凄くコンパクト。でも2^cとか含むだろうけどね。 n,m = gets.spli…

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

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

続: 最大クリーク問題

なんかいろいろやってこんな形に落ち着いた。 簡単にいうとまず適当にソートして、有向グラフに変換してDPする。 dp[j][c]はj以下の頂点を使用したjを含むサイズcのクリークの文字列表現の配列。 後続の頂点iからはこのクリークの頂点にすべて辺があれば、サ…

最大クリーク問題

まだうまく証明できていないかもしれないけど、これで解けてると思う解けていないです。別の実装を考えたのでコードを消しました。kousuke.hatenablog.com belongs_max_cliqueではある頂点を含む極大クリークのサイズを返していて、それを全点に対して行いそ…

グラフ理論について、今のところわかったこと

任意のグラフをGとし、その彩色数をとあらわす。 1点uを加えG'とするとき、その接続数がk未満の場合には必ずが成立する。証明 であるGからk未満の点を選択するとき、uはかならずk色の中から彩色の色を選択できる。 よって上記が成りたつ。 (証明終わり)任意…