前、こういうのを考えて、最大クリーク数もなんとなく半分になりそうって書いたんだけど、 kousuke.hatenablog.comそれって式にするとこういうことになるのかな? fはの辺を頂点にして、がの時に辺とするような変換。 完全グラフについては証明できそうだけど…

news.yahoo.co.jpでこの記事に対して、下記のようなブクマコメントをしたのだけれど、1つではあるけれど、スターがついてしまったのでメモ代わりに書いておこうとおもう。保育士は「誰でもできる仕事」か(駒崎弘樹) - 個人 - Yahoo!ニュースホリエモンは保育…

興味はもつのだけれども、投票したい政党とかがないなぁ。 二大政党制とか目指すのやめたほうがいいんじゃないの?とおもってきた。 STOP安倍政権のスローガンとかみていると、そもそも単独政党による過半数とかできるルールが悪いんじゃないかとおもってきた…

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

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

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

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

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

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

多分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頂点のグラフがある。 このときからへひとつづつ辺を消していく順序集合のうち、を含む順序の集合を定めることができる。このときのどの順序を通ってもの補グラ…

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

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

すこしコードを変更している。興味ある人は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から最大次数で…

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

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

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

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

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

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