[問題案] Chromatic Polynomial

[maspypy]

問題概要

$N$ 頂点 $M$ 辺のグラフが与えられる．彩色多項式を出力せよ．

制約

• $1\leq N\leq 20$
• $0\leq M \leq 500$
• ループあり、多重辺あり

解法

https://github.com/yosupo06/library-checker-problems/issues/975 を使うと、非空独立集合 $k$ 個に分割する方法が数えられるのでできる。

関連

• https://github.com/yosupo06/library-checker-problems/issues/975
• https://codeforces.com/blog/entry/92183
• https://atcoder.jp/contests/abc294/tasks/abc294_h

[maspypy]

https://en.wikipedia.org/wiki/Chromatic_polynomial ループがある場合にも定義しているのかが分からなかったが、ループがない前提で書かれている場所が多そう。

なので、単純グラフにしました。

[noshi91]

多重辺はあっても良さそうです。 http://lealgorithm.blogspot.com/2016/11/tutte.html Tutte 多項式の特殊な場合と考えると自己ループもあって良さそうです (実用的にも、自己ループは出てきてもおかしくはないかも)。ただし monic な n 次多項式という性質は失われるので難しいかも。

[maspypy]

グラフは、(自明な変形(自己ループ削除 / 多重辺は重みの最大を1本残す)で答えが変わらない AND 単純じゃないと出力に不具合が生じる)時のみ単純

の思想に従うと多重辺はなしでいいかなと思っています。 ループは入れて、 $M\leq N(N+1)/2$ でどうでしょうか。

[noshi91]

単純じゃないと出力に不具合が生じる

これを満たしてない (= 不具合が生じない) 気がしました

[maspypy]

ああ、なるほど。理解しました。

$M\leq 500$ みたいにしておくかあ。

[maspypy]

作業者募集。