補グラフでの最小頂点被覆ってなんだろう?って考えてて、最大クリークの頂点以外の頂点集合って意味しかないのかな

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…

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

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

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

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

最初は彩色数kのグラフは2部グラフマッチングか最大流にできるとおもっていたのですが、制限付きナップサック問題かなにかに帰着できそうな気がしています。 たしかに組み合わせ問題なのでナップサック問題になってもおかしくなさそうです。 現在、v,e,kのみ…

完全グラフばかり考えていたのですが、マイナーを考えないと本質にたどりつけなさそうなので考えています。Kn を彩色数を変えずにKmだけ分離していく(強連結を置換していく)には、完全2部グラフが必要になる。(片方はmだけど、もう片方が、m+1かn-1か、それ…

変更しました。 四色定理から求められる平面グラフの性質 交差のない平面グラフにおいて、任意の1面に対し、その面を構成する閉路の頂点を3彩色し、 且つ、グラフ全体を4彩色する塗り方がある 交差のない平面グラフGにより構成される面Fの内、任意の面fを構…

いろいろ考えて、NP完全、NP困難とされているk-彩色、彩色数がO(|V| |E|)でできそうな気がしてきた。 無理、無理。

01223という数字が頭に浮かびあがってきて、ABC予想にたどり着いた。c 回=開->閉、回=開->閉だ。 001223*2だった。*2がなんなのかだけど、きっと彩色数みたいな層だ。

N2層からN3層にあがるとき、3角錐がある。ここに選択があってN2,N3で十字から正八面体をつくるのと、N1,N3層で正六面体で中心にN2層がある状態がつくれる。 正八面体が虚数空間で-1を無限,1を無限で-1は2で割る方向、1は2,3と増えていく方向があり、-1/2と無…

回、開、閉だな。これはどの層にも出現することができる。 回はループで0に相当する、開は+、閉は-。開 + 閉 回の操作を行うと関数Pにより規定される写像に反映される。 この3基底で彩色数を操作していたのがこれまでのポストだ。もうすこし足りなかった。点…

タイトルを変えました。変えましたが、まとまっていないです。Hadwiger予想の証明を近いうちに書きたいと思います。 たぶん正多面体上のグラフマイナーで砂時計みたいに半分でわって頂点でくっつけたものなんで？ 層を移動する推進力を得るため。ポエムみた…

なんでこんなことをおもいついたのかわからないけど、吐き出してみる彩色数を基にした層Nnがあるとする。 点を作る -> N1層に点を作成する(K1)。 辺を作る -> N1層の2点を接続し、N2層に点(K2)を作成し、N1層の点は消す 面を作る -> N2層の3点がK3を構成した…

平面に落ちないからってことなんだけど一旦マイナーとか平面はおいておくとして 彩色数で分割した多層ネットワークを考える1層にはK1、2層にはK2、3層にはK3を頂点として配置することとする。1層目に辺ができると2層目に頂点を作って接続する(上層にジャンプ…