基本的には前書いた内容。 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の定理を含んで、より上限を押さえるとおもってるんだけど、既知なのかがわからん。これは既知だった。…