計画性

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

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

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色の中から彩色の色を選択できる。 よって上記が成りたつ。 (証明終わり)任意…

彩色数判定へのアプローチ

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

完全グラフのマイナー

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

四色定理の証明

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

彩色問題(2)

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

01223

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予想は正しい

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

彩色数をもとにしたグラフの性質(1)のイメージ

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

K3,3が平面グラフの禁止マイナーな理由の想像

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

彩色数、グラフマイナーとは

イメージ的には電子部品のようなもので3次以上の完全グラフをマイナーとして持つネットワークが内部回路、内部回路も同様に入れ子にできる。その内部ネットワークを十分に機能させるために彩色数分のソケットが必要。色を示す頂点を用意し、一つの部品のソケ…

Hadwiger予想

kousuke.hatenablog.comHadwiger予想近づいた気がしてきた。グラフ彩色 - Wikipedia その他のグラフの彩色数に関する未解決問題としては、Hadwiger予想(en)がある。これは、彩色数 k のグラフはマイナーとして頂点 k 個の完全グラフを含む、という予想である…

彩色問題

四色定理のことをたまに考えるんだけど、平面グラフにおいて、任意の1面に対し、その面を構成する閉路の頂点を3彩色し、且つ、グラフ全体を4彩色する塗り方があるってことに気付いた。多分、正しい。平面グラフGにより構成される面Fの内、任意の面fを構成す…

バナーグラビング / TomcatのServer infoとか

ウェブアプリならHTTPサーバーとかTomcatのようなアプリケーションサーバのバージョン情報とをHTTPヘッダーやエラーページに表示されるバージョン情報から確認して、脆弱性を利用した攻撃方法の参考にするようなことをバナー・グラビングというらしい。 エラ…

忘れられる権利ってなんで検索エンジンに訴訟申し入れるの?

www3.nhk.or.jpGoogleにではなくて、報道側に訴訟起こせばよいんじゃないかな?とおもう。HTTP的には404だって普通のHTMLコンテンツは返せるんだから、記事の本文はそのままで404 Not Foundとか410 Gone出せば、それを受けてGoogleは削除するし。 容疑者の段…

ninjaframeworkとgradle

ninjaframeworkに興味をもっているのだけれど、Androidの影響でgradleに大分慣れたので、mavenかとおもうと腰が引けてしまう。 ninjaframeworkのgradleプラグインとかないかなと思っていたのだけれど、grettyのoverlay機能をつかってSuperDevModeみたいなの…

gov-APIとかの広がり

thebridge.jpSmartHRが電子政府の外部連携APIを利用したオンライン申請機能を出すらしい。 以前、PKIが本格化しそうな気がすると書いたが、イメージとしては上記のようなものが近い。 APIを使用するのに電子証明書などを使うことで実在性や本人性を担保する…

gradleのテスト実行時にシステムプロパティを設定したい

Gradleの実行自体に-Dをあたえてみたのだけれど、JUnitに反映されていなかったので、調査。結論: マニュアルみれば載ってるから。 test { systemProperty 'some.prop', 'value' }

POH vol.7

ヤバい嫁ドロイドがかわいい。 水着 最初は小難しく考えてたけど、意外とすんなり解いた。でもrubyのおかげっていう点が多い気がする。 https://paiza.jp/poh/ando/share/2a940576 def answer(n) return 1 if n < 2 t = (2..n).to_a until t.size == 1 t = t…

AndroidのVolume設定

サンプルとかブログとかみているとAudioManagerから最大ボリュームと現在のボリュームを取得して、割っているのをよく見かけるが、あれは間違いではないかとおもう。MediaPlayerやSoundPoolのボリュームに1.0fを設定した場合は最大ボリュームと説明している…

gradle-jenkins-pluginというのを見つけてしまった。

github.comJenkinsのジョブ管理をどうしようとおもっていて、JenkinsのJobのDSLとかないかなとか探していたら、上記をみつけてしまった。Wikiも結構内容が充実しているのでみれば大体わかる。 Job自体はjenkins-cli使えばxml形式でエクスポートできるし、xml…