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…

PKIが本格化しそうな気がする

Legal Tech / Fin Techがすこしづつ現実的になりつつある今日この頃。ちょっと気持ち悪いけど、契約書をポストすると承認者に通知が飛んで、承認者が承認すると契約書に署名がされるとかいう未来が見える気がする。開発者的にはそれはGitHubのPRとマージ作業…