最初の式を書きなおすと以下のようになる。後続の頂点の出次数がすべて彩色数未満であれば、彩色数はもう上がらないことがわかる。よって次式が成り立つ。彩色可能なことがわかる。使用して、もうすこし精度よく上限を求めることができる。いままでの内容を例としてまとめるとこんな感じになる。抑えられていることがわかる。次にn=4のとき、既に彩色数は4となっていて、後続の出次数はすべて4未満になっている。実際に彩色数も上がっていないことがわかる。結局、次数が高い頂点があっても、それが1つしかなければ、ほとんど彩色数には寄与しない。なり、彩色数を0から1にするだけになる。全体の彩色数を求められるということだとおもう。頂点の順序を変えると出次数も変わってしまうので出次数を抑えるような順序を探すのは難しいかもしれないが、次数であれば簡単になる。ちなみに次数降順とした際に、n=0を考えるとBrooksの定理と一致することもわかる。頂点半分で求まるなら実際の時間はかなり減る。彩色数の下限にあたりをつけて少しずつ増やしていくのがよさそうな戦略に思える。彩色数と一致している。順序によっては4以上となることもあるのだけれど、上限はかなり抑えられている。貪欲彩色のWelsh-Powellのアルゴリズムに比べると実際に彩色するかしないかの違いがある。彩色数を近似したいときは今回紹介したほうが便利で、実際に彩色した結果がほしいのであればWelsh-Powellの方が便利。なった時点でもう一度というような方法で時間的には短縮できるんじゃないかとおもっている。ソーシャルグラフのような次数がパレートの法則に従うようなグラフだと、ロングテール部分の次数は小さそうなので、そうするとヘッドの部分を調べるなかで結構テールの頂点を削れるとおもう。逆に次数があまり分散してなくて、大きなクリークがないのが一番大変ということになりそう。シャープレイ値がやはり気になっていて、彩色数は劣加法性があるので符号を反転して、優加法性をもたせてシャープレイ値やその固有ベクトルに何かつながらないかなとおもっている。位置エネルギーがスケールが大きくなったときに無限遠を0にして、符号がマイナスになったような感じで物理学的なロマンにときめいている。追記Welsh-Powellの貪欲彩色だと実際に彩色していくけど、彩色せずに進めるとステップ関数使ったやつみたいになりそう。ちなみに手元でいろいろためしたところ、次数降順が安定して彩色数が小さく出る。予想してたけど1000頂点10彩色可能なものが次数降順だと13ででていたけど、適当にシャッフルしたやつだと23くらいがよくでる。上記の近似解kを使ってgales-sharpleyの変形で外部性のある安定結婚問題として解くとk以下の彩色が求められる。外部性があってもDA方式(受入保留方式/gales-sharpleyのアルゴリズム)で安定マッチング(ペア安定マッチング)はあることがわかっているけど、グループ安定性を満たさない、耐戦略性を満たさないというのが下記論文に書いてある。11:42Brooksの定理++Tweet広告を非表示にする関連記事2018-02-19最大クリーク問題つづきグラフのDegeneracyをkとすると前処理後、おおまかで最大クリー...2017-06-22ヒューリスティックな彩色k-degenerationグラフの順序で彩色してやれば、最大出次数+1以...2017-06-02最大クリーク問題(改)最大クリーク問題をいま全面的に書き直していて、すごくおもし...2017-04-04最大クリークの計算量とか修正しました。Vacation月別アーカイブはてなブログをはじめよう!tinsep19さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。