彩色数をもとにしたグラフの性質(1)のイメージ
なんでこんなことをおもいついたのかわからないけど、吐き出してみる
彩色数を基にした層Nnがあるとする。
点を作る -> N1層に点を作成する(K1)。
辺を作る -> N1層の2点を接続し、N2層に点(K2)を作成し、N1層の点は消す
面を作る -> N2層の3点がK3を構成したら、N3に点を作成し、N2層の3点は消す。
立体を作る -> N3層の4点がK4を構成したら、N4層に点を作成し、N3層の4点を消す。
K4とK3の点連結 -> N1層の点を作ってN3層とN4層の点にリンクをつくる。K1_2でK1側をN1層に置く
K4とK3の辺連結 -> N2層の点を作ってN3層とN4層の点にリンクをつくる。K1_2でK1側をN2層に置く
こんな感じで考えると4色定理はN4上の複数の点がN4上でのリンクはなく、N3層以下で蠢く感じに思えてくる。
彩色数を性質とするとマイナーに閉じた操作もイメージしやすい。
K3,3が平面グラフの禁止マイナーな理由の想像
平面に落ちないからってことなんだけど
一旦マイナーとか平面はおいておくとして
彩色数で分割した多層ネットワークを考える
1層にはK1、2層にはK2、3層にはK3を頂点として配置することとする。
1層目に辺ができると2層目に頂点を作って接続する(上層にジャンプするイメージ)。同様に2層目が3連結になると3層目に頂点を作成し、接続するという感じで行うとき、K2_3グラフは作れるけど、K3_3グラフはねじれが起きてるんじゃないかとおもう。(イメージとしては3層から下層に向かって穴が開く、もしくはK6に突き抜けようとして5層にぶち当たるイメージ)
同じようにK3_4は作れるけどK4_4は禁止マイナーみないなものがあるかもしれない。
まあ想像で全然現実味がない。
K3_3は結局K4になるかK2_2になるしかないからだ。平面はK4マイナーなのでK4にはなれないし、K2_2になると自己ループで消えてしまう。ちなみに単独のK3を2つつなぐと一つになる。
追記:
基数層は面がせりあがって、偶数層は点がせりあがる立体のイメージ。
むしろ2部グラフはKn,mとするとmin(n,m) * 2 = sとして、P(Ks)のサブグラフに含まれるとかがありそう。
むしろ2部グラフはKn,mとするとKnとK_n+mの1点をつなぐサブグラフに含まれるとかありそう。
追記2:
K3_3は結局K4になるかK2_2になるしかないからだ。平面はK4マイナーなのでK4にはなれない。K2_2の点は自己ループで消えてしまう。
彩色数、グラフマイナーとは
イメージ的には電子部品のようなもので3次以上の完全グラフをマイナーとして持つネットワークが内部回路、内部回路も同様に入れ子にできる。その内部ネットワークを十分に機能させるために彩色数分のソケットが必要。
色を示す頂点を用意し、一つの部品のソケットには色の重複がないように割り当てるように、全てのソケットと繋ぐときの最小頂点数をみつけるのが彩色問題。
追記:
まとめるとグラフGの彩色数をP(G)とするとGを二つのグラフGa,Gbに分割したとき、P(G) = max(P(Ga), P(Gb))P(G) ≧ max(P(Ga), P(Gb))にたぶんなる(これはそんな定理もあった気がする)。
P(G) > max(P(Ga), P(Gb))の時は多分、P(G)=nとすると彩色数を決めるKnのグラフマイナーをぶった切ってる。
Ga, Gbはさらに分割可能なので、上記の式を帰納法で解いた結果はHadwiger予想とおそらく同じ。
min側の意味もGa,Gbの連結度的なものになりそう。
彩色組み合わせの数もKnから任意の辺に頂点を追加する操作を行う操作回数をoとすると彩色組み合わせはP(Kn)*(P(G)-2)^oになる筈だし、マイナーに閉じた操作での彩色組み合わせの数の変化はおそらく示せそう。
Hadwiger予想
Hadwiger予想近づいた気がしてきた。
その他のグラフの彩色数に関する未解決問題としては、Hadwiger予想(en)がある。これは、彩色数 k のグラフはマイナーとして頂点 k 個の完全グラフを含む、という予想である。
平面グラフの彩色においては任意の面が3彩色可能なときとしたけど、平面じゃなければ、接続可能な点は頂点数分あるから、そうなりそう。
彩色数nのグラフGnに対し、頂点を1つ追加してGn+1にするには、Knグラフマイナーのn色にn本辺を引くのが、手順になるよな。
追記:
グラフを特徴づけるHadwiger予想と今回の面の彩色数の関係が理解できてきた気がした。
K3のグラフマイナーが面に相当し、これを頂点として4彩色のグラフを構成しているのが平面グラフだ。たぶん。
グラフ全体に処理を施していくことで面がつくれる。
縮退数kのグラフがのマイナーを持ってないかなー
彩色問題
四色定理のことをたまに考えるんだけど、平面グラフにおいて、任意の1面に対し、その面を構成する閉路の頂点を3彩色し、且つ、グラフ全体を4彩色する塗り方があるってことに気付いた。
多分、正しい。
平面グラフGにより構成される面Fの内、任意の面fを構成する閉路をCfとする。
このCfを3彩色し、Gを4彩色する方法が必ず存在する。
Gに点uを加えて、G'を作るとき、uは必ずある面f内に配置される(グラフの外も面と考える)。
この時fを構成する閉路Cfが必ず4色必要とされる場合、uからCf上の4色の点に辺を作成したG'は必ず5色必要となり、四色定理に反する。
追記:
帰納法でもできそう。GにK4が含まれる場合には成立する。
たぶんGには、K4グラフマイナーが含まれる場合に成立する。かな? グラフマイナーよくわかってない。
そしてK4グラフマイナーを含まない場合に、CfおよびGが3彩色可能になりそう。なのかな? まだわからない。
追記2:
Gnが3彩色できる場合、3色の閉路で2色の頂点のみに接続する場合か、2色の閉路内に1頂点を加えた場合なので、3彩色のグラフの列挙とか、判定式もできそう。。
バナーグラビング / TomcatのServer infoとか
ウェブアプリならHTTPサーバーとかTomcatのようなアプリケーションサーバのバージョン情報とをHTTPヘッダーやエラーページに表示されるバージョン情報から確認して、脆弱性を利用した攻撃方法の参考にするようなことをバナー・グラビングというらしい。
エラーページの方はなぜかServerInfo.propertiesを抽出して、書き換えてもう一度jarに固めろというページがたくさん見つかる。jarに署名されてる場合にはその方法できないだろとおもうし、version.shで確認できなくなるよ。
https://github.com/apache/tomcat80/blob/trunk/bin/catalina.sh#L581
version.shはcatalina.sh versionを呼ぶんだけど、その中ではcatalina.jarだけclasspathに含めて、ServerInfo.propertiesの内容を表示しているという感じ。jarを固め直すとわからなくなる。
Apache Tomcat 8 (8.0.36) - Security Considerationsを確認するとCATALINA_BASE/lib/org/apache/catalina/util/ServerInfo.propertiesを作成して書き換えなさい。
ということなので、ServerInfo.propertiesを書き換える場合はcatalina.jarから展開して書き換える。
jar -xf catalina.jar org/apache/catalina/util/ServerInfo.properties vi org/apache/catalina/util/ServerInfo.properties
Server: ヘッダのほうはserver.xmlのConnectorのserver属性を変更する。
忘れられる権利ってなんで検索エンジンに訴訟申し入れるの?
Googleにではなくて、報道側に訴訟起こせばよいんじゃないかな?とおもう。
HTTP的には404だって普通のHTMLコンテンツは返せるんだから、記事の本文はそのままで404 Not Foundとか410 Gone出せば、それを受けてGoogleは削除するし。
容疑者の段階で記事になって、無罪になったら報道しないとかあったら、どうなのっておもうし、裁判とかで量刑確定した記事を作ったら、服役が終わったことをつたえる記事も作った方がよいし、その記事は元記事からリンクしてあげたほうがよい。(面倒だとはおもうけどね)
「忘れられる権利」ではなく、報道側に経緯を追いかける責任はあってもよいとおもうので、追いかけない姿勢の形として、一定期間後に404/410のステータスコードを出すとかいうのは報道側に求めてもよいんじゃないかな?とおもう。
