Крайній випадок

У теорії графів, парування або незалежна множина ребер у графі G = (V, E) — це множина ребер M \subseteq E, така, що жодні два ребра в паруванні $M$ не мають спільної вершини.

Нещодавно ви дізналися з новин, що "Премію Шведського національного банку з економічних наук пам'яті Альфреда Нобеля" (неофіційно, Нобелівська премія з економіки) за $2012$ рік було присуджено Алвіну Е. Роту та Ллойду С. Шеплі за їхній алгоритм для знаходження парування, яке задовольняє певні критерії у двочастковому графі. Оскільки ви також чули, що парування в циклічних графах мають застосування в хімії, ваші думки зосереджуються на плані прекрасного майбутнього, де ваші різдвяні покупки будуть розкішнішими, ніж будь-коли!

Циклічний граф, C_n, n \geq 3, — це простий неорієнтований граф на множині вершин \{1, \ldots, n\}, з множиною ребер E(C_n) = \{(a, b) \mid |a-b| \equiv 1 \mod n\}. Він є $2$-регулярним і містить $n$ ребер. Графи C_3, C_4, C_5 та C_6 зображені на Рисунку 1.

Рисунок 1: Графи C_3, C_4, C_5 та C_6.

Ваш перший крок до слави Нобелівської премії — це вміти обчислювати кількість парувань у циклічному графі C_n. На Рисунку 2 зображено сім парувань графа C_4.

Рисунок 2: Парування графа C_4. Ребра, що є частиною відповідного парування, зафарбовані зеленим, тоді як ребра, що не входять до парування, позначені пунктиром. M_1 = \emptyset, M_2 = \{\{2, 1\}\}, M_3 = \{\{3, 2\}\}, M_4 = \{\{4, 3\}\}, M_5 = \{\{1, 4\}\}, M_6 = \{\{2, 1\},\{4, 3\}\}, і M_7 = \{\{3, 2\},\{1, 4\}\}.