なんかいろいろやってこんな形に落ち着いた。 簡単にいうとまず適当にソートして、有向グラフに変換して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層目に頂点を作って接続する(上層にジャンプ…

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

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

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

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

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

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

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

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