2016-10-18

Hadwiger予想

~~kousuke.hatenablog.com~~

~~Hadwiger予想近づいた気がしてきた。~~

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

平面グラフの彩色においては任意の面が3彩色可能なときとしたけど、平面じゃなければ、接続可能な点は頂点数分あるから、そうなりそう。
彩色数nのグラフGnに対し、頂点を1つ追加してGn+1にするには、Knグラフマイナーのn色にn本辺を引くのが、手順になるよな。
追記:
グラフを特徴づけるHadwiger予想と今回の面の彩色数の関係が理解できてきた気がした。

K3のグラフマイナーが面に相当し、これを頂点として4彩色のグラフを構成しているのが平面グラフだ。たぶん。
グラフ全体に処理を施していくことで面がつくれる。

縮退数kのグラフが $K_{k+1}$ のマイナーを持ってないかなー

2016-10-17

彩色問題

四色定理のことをたまに考えるんだけど、平面グラフにおいて、任意の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彩色のグラフの列挙とか、判定式もできそう。。

2016-08-09

バナーグラビング / 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属性を変更する。

2016-07-12

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

www3.nhk.or.jp

Googleにではなくて、報道側に訴訟起こせばよいんじゃないかな?とおもう。

HTTP的には404だって普通のHTMLコンテンツは返せるんだから、記事の本文はそのままで404 Not Foundとか410 Gone出せば、それを受けてGoogleは削除するし。

容疑者の段階で記事になって、無罪になったら報道しないとかあったら、どうなのっておもうし、裁判とかで量刑確定した記事を作ったら、服役が終わったことをつたえる記事も作った方がよいし、その記事は元記事からリンクしてあげたほうがよい。(面倒だとはおもうけどね)

「忘れられる権利」ではなく、報道側に経緯を追いかける責任はあってもよいとおもうので、追いかけない姿勢の形として、一定期間後に404/410のステータスコードを出すとかいうのは報道側に求めてもよいんじゃないかな?とおもう。

2016-06-07

ninjaframeworkとgradle

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

github.com

grettyはすこし触っていたのでちょうどよかった。
ちなみにgrettyはTomcat/Jettyがつかえて、複数のwarプロジェクトを起動できるので使い勝手がよいとおもいます。

2016-03-07

gov-APIとかの広がり

thebridge.jp

SmartHRが電子政府の外部連携APIを利用したオンライン申請機能を出すらしい。

以前、PKIが本格化しそうな気がすると書いたが、イメージとしては上記のようなものが近い。
APIを使用するのに電子証明書などを使うことで実在性や本人性を担保するというもの。
実際には社労士の電子証明書でやってる気もするが、まあ仕業というのはそういうものな気がする。

kousuke.hatenablog.com

今の理解には誤解とかが多分に含まれていそうなので、調べていきたい。

2016-02-29

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

Gradleの実行自体に-Dをあたえてみたのだけれど、JUnitに反映されていなかったので、調査。

結論: マニュアルみれば載ってるから。

test {
  systemProperty 'some.prop', 'value'
}