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

最初は彩色数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とマージ作業…

誰得?だけどTomcatとかでつかうkeystoreのテスト書いてみた。

JKSのファイルが正しくできているかどうかを確かめたくて作ってみた。JRuby + RSpecで実行する。JRubyあんまりつかったことなくて、to_javaとか、 to_inputstreamで引っかかった。証明書のインポートがちゃんとできてるか、キーチェインがちゃんと解決できる…

POH6 霧島ミッション

paiza.jp動的計画法で解いてるのが多いけど、Union-Find木でといた。 今回のPOHは回文よりも、こっちのがコードゴルフ的にも解法のアプローチ的にもいろいろありそうで好き。 class UnionFind < Hash def initialize super do |hash,key| hash[key] = key en…

Google Appsで対象の会議室の予定をメールで送るサンプル

依頼があって作ってみた。要件が違ったので、これはつかわないので貼り付け。 Google Spreadsheetに会議室ID一覧を記入して、対象の会議室の予定をメールで送るサンプル Spreadsheetをつくって、A列に会議室IDをざっと貼り付ける。 ツールからスクリプトエデ…

「週刊現代」 編集長戦記 よんだ

「週刊現代」編集長戦記 (イースト新書046)作者: 元木昌彦出版社/メーカー: イースト・プレス発売日: 2015/02/08メディア: 新書この商品を含むブログを見る週刊現代、フライデーの編集長 元木昌彦さんの著書。雑誌の方向性の掲示、それを実現するため/乗り越…

ツイッター創業物語 読んだ

ツイッター創業物語 金と権力、友情、そして裏切り作者: ニック・ビルトン,伏見威蕃出版社/メーカー: 日本経済新聞出版社発売日: 2014/04/24メディア: ?行本-平装この商品を含むブログ (17件) を見るLong Tail World: 忘れ去られたツイッター共同創業者:Twi…

BackLogのファイルにmavenリポジトリを作成する

いまさらながらに社内用にmavenリポジトリをつくろうかとおもい、gradleなんかを調査。プロジェクトの作成 mkdir YOUR_LIB cd YOUR_LIB gradle init --type java-librarymavenリポジトリを構築するための設定。リポジトリはBackLogのファイルがWebDAVを提供…

定額制音楽サービスについて

AppleがApple Musicを出したり、LINE musicがはじまったり、定額制音楽サービスがまた盛り上がりを見せている。 個人的にはあまり日常的に音楽を聴かないので、どうなろうがあまり興味がないが、 facebookのOpenGraph Musicが更新されて、もりあがるんじゃな…

CORSについて

Office 365 API : CORS の使用 - 松崎 剛 Blog - Site Home - MSDN Blogsをよんでいました。 JavaScript を使って Access Token を取得し、この Access Token を使って下記の通り Office 365 API を呼び出します この部分をよんだときに、これまでCORSはサー…