joisino https://blog.hatena.ne.jp/joisino/ ｼﾞｮｲｼﾞｮｲｼﾞｮｲ https://joisino.hatenablog.com/ SRM717 の Hard で出題されて気になったので書き留めておきます。 Chromatic Polynomial について まず、無向グラフの頂点から色への対応を彩色、隣接する頂点が同じ色にならないような彩色のことを正しい彩色ということにします。これはこの記事限定用語です。 以下無向グラフ を 色で正しい彩色する場合の数を と表します。 Chromatic Polynomial はこの のことです。 これは、色数 の多項式になります。 まずはこの多項式を具体的に構成しましょう。 は以下の性質を持ち、また逆に、以下の性質を持つ関数は となります。 を 1 頂点からなるグラフとすると の連結成… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fjoisino.hatenablog.com%2Fentry%2F2017%2F07%2F04%2F213328" title="Chromatic Polynomial と Acyclic Orientation - ｼﾞｮｲｼﾞｮｲｼﾞｮｲ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://chart.apis.google.com/chart?cht=tx&chl=%20G Hatena Blog https://hatena.blog 2017-07-04 21:33:28 rich https://joisino.hatenablog.com/entry/2017/07/04/213328 1.0 100%