2015年8月30日日曜日

CodeForces #306 Div2 D : D. Regular Bridge

問題:
橋を持つk-正則グラフを作れ。ただし作れないときはNOと答えよ。

解法:
明らかにk=2のときはグラフはCycleとなるのでNO.
一般に、kが偶数であるときはNOとなる。
(証明)
kが偶数のときにk-正則グラフに橋が存在すると仮定する。
すると、その橋を取り除くことによって二つのグラフに分解することが出来る。
しかし、それぞれのグラフについて、次数の和は奇数となってしまうので矛盾。

以上よりkが偶数の時はNOと答えれば良い。ではkが奇数の時はどのようにして構成出来るか?

kが奇数の時は
完全二部グラフK(k-1,k-1)を構成し、それぞれの頂点集合をA,Bとする。
Aの各頂点マッチングを結ぶ(k-1は偶数なので存在する)
頂点vを新たに一つ用意し、vとBの各頂点を結ぶ。
このように構成したグラフの次数について見ていくと、vの次数はk-1で、そのほかの次数はkとなる。
よってこのグラフを二つ用意しそれぞれのv同士を結べばその辺が橋になり、しかもグラフはk-正則となる。

ソースコード:
https://gist.github.com/knewknowl/4c17af4dde6f43e9bdc7

解の個数を減らす帰着 (Valiant--Vaziraniの定理)

2月に 冬のLA に参加してこれまで5,6年くらい常に取り組みようやく身を結んだ共同研究を発表してきました. 2月のLAではD2辺りからずっと取り組んでいた個人的未解決問題がある程度解決できたことについて発表させていただきます。 — Nobutaka Shimizu (@kn...