完全グラフ \(K_{2N}\) を \(N-1\) 個のハミルトン閉路と \(1\) 個の完全マッチングに分解する
今回は、記事の名前の通り「完全グラフ \(K_{2N}\) を \(N-1\) 個のハミルトン閉路と \(1\) 個の完全マッチングに分解」していこうと思います。
まず、この分解の意味について。具体的には Doofish Matrix という問題を解くときにこれを調べててヒットしなくてなかなか困ったのですが、やりたいこととしてはざっと以下のような感じです。
完全グラフ \(K_{2N}\) の辺数は \(N(2N-1)\) だが、もし辺を余すことなく完全マッチングに分解できるなら、ここから \(2N-1\) 個のマッチングが取れるはず…?
ここで、とりあえず辺をダブらないようにいい感じにとる話として、
Complete GraphのHamilton cycle(path)への分割 - YKK++ という記事が存在するのが記憶にありました。
この記事内では、「完全グラフ \(K_{2N}\) を \(N\) 個のハミルトンパスに分解する」「完全グラフ \(K_{2N-1}\) を \(N\) 個のハミルトン閉路に分解する」方法が示されています。これも競プロでよく見る内容なので、覚えておきたいものですが、今回はこちらを適用することは残念ながらできなさそうです。
さらにいろいろ資料をあたった結果、 ハミルトン路 - Wikipedia に、
完全グラフ \(K_{2N}\) は、 \(N-1\) 個のハミルトン閉路と 1-正則な全域部分グラフ (すなわち、 \(1\) 個の完全マッチング) に分解できる。
という記述がありました。少し考えると、以下のようなことがわかります。
\(K_{2N}\) のハミルトン閉路の長さは当然ながら \(2N\) 。これは偶数なので、交互に辺を取っていくと \(2\) つのマッチングが取れる。
ということは、\(N-1\) 個のハミルトン閉路と 1-正則な全域部分グラフ (すなわち、 \(1\) 個の完全マッチング) に分解できるなら、\(2 \times (N-1) + 1 = 2N-1\) 個のマッチングを取れることにもなる。
ただ、Wikiには結論しか書かれておらず、肝心の手段は書いていませんでした。う～む、こんな時に限って使えない…
そこで、検索言語を英語まで広げてなんとかたどり着いた記事が graph theory - Simple decomposition of \(K_{2n}-I\) into hamiltonian cycles - MathOverflow 。
但し、ここには概略しか書いていないので、以下で僕なりに解釈して編み出した具体的な構成法を示します。
まず、頂点に \(-(N-1) , -(N-2) , ... , -1 , 0 , +1 , ... , +(N-2) , +(N-1)\) という番号を付けた後、余る \(1\) つの頂点を特別な頂点 \(sp\) とします。(これは最初に引用した記事の番号付けの仕方と同じです)
この上で、 \(0\) と \(\pm 1\) を結びます。次に、 \(\pm 1\) と \(\mp 2\) とを結びます。(複号同順です) これ以降は、 \(\pm k\) と \(\mp k\) とをどんどん結んでいきます。
最後に、 \(\pm (N-1)\) と \(sp\) とを結んで \(1\) つのハミルトン閉路が完成。
これを、時計回りに \(2\) 頂点ぶん回したグラフ (図では \(0\) の部分を \(+2,+4,-3\) に対応させる感じ) を次々に取っていけば、最後に \(1\) つのマッチングが残ります。
<ざっくりとした証明>
図は \(N=5\) ( \(10\) 頂点)の場合ですが、まず、「辺の長さ」を(周上で何頂点離れた頂点を結んでいるか?)で定義します。
すると、図の分解だと、
- \(-1,0\) を起点とする長さ \(1\) の辺
- \(+3,+4\) を起点とする長さ \(2\) の辺
- \(-2,-1\) を起点とする長さ \(3\) の辺
- \(+2,+3\) を起点とする長さ \(4\) の辺
- \(+4,-4\) を起点とする頂点 \(sp\) につながる辺
というように隣り合った \(2\) 頂点を起点として辺を分類できます。言葉で言うなら図のクロスしている辺を1単位と見ている感じ。これを \(2\) 頂点ずつずらしてとっていくと、辺がダブらないのは自然な感じがしますよね。
で、これを \(N-1\) 個分とると辺が尽きます。一度ハミルトン閉路を取るたびに各頂点の次数は \(2\) ずつ減少します。辺が尽きたときの全ての頂点の次数は \(1\) です。このとき、「すべての頂点が次数 \(1\) である頂点数 \(2N\) のグラフ」は、「 \(1\) つの完全マッチング」であることがわかります。
というわけで、この方法はうまくいきます。完全(無向)グラフの辺を余すところなく使う分解は、「完全グラフ \(K_{2N}\) を \(N\) 個のハミルトンパスに分解する」「完全グラフ \(K_{2N}\) を \(N-1\) 個のハミルトン閉路と \(1\) 個の完全マッチングに分解する」「完全グラフ \(K_{2N-1}\) を \(N\) 個のハミルトン閉路に分解する」あたりでほぼ網羅だと思うので、全て理解しておくと構築問題などで役に立つでしょう。ちなみに、 完全有向グラフはハミルトンパスを持つ - フィボナッチ・フリーク というような話題もあったりするので、こちらも押さえておくと吉です。
追記 2021/03/03
Start of the season もほぼ同じ問題で、こちらでもVerify可能です(問題タイトルが表記揺れしています…)
