問題：
橋を持つ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
-
概要 焼きなまし法 は遺伝的アルゴリズムなどと並ぶ最適化問題の発見的解法の一つとして有名であり, 競技プログラミングの文脈ではマラソン(厳密解を求めるのが困難とされる一つの最適化問題に長時間取り組み最も最適値に近い解を得るという種目) においては常套手段の一つとして用いられていま... -
競プロで道具として用いられる様々な賢いアルゴリズムやデータ構造の多くは, 非常に賢い研究者たちによって発見されており, ほとんどは理論計算機科学の論文として国際学会の会議録や学術雑誌の形として出版されています. ここではアルゴリズム系の研究論文がよく出てくる様々な国際会議を紹介し...
-
0. 概要 グラフマイナー定理とは 有限グラフの全体は, マイナー順序によってよい擬順序になっている (well-quasi-ordered) という定理です. ...さてこれは何を言ってるんでしょうか. 本記事では現代のグラフ理論において最も重要な定理の一つで...
0 件のコメント:
コメントを投稿