Tutteho polynom cyklu
Úloha číslo: 3285
Určete Tutteho polynom pro cyklus délky \(k\).
Nápověda
Použijte rekurentní vztah pro výpočet Tutteho polynomu \(T_G(x,y)\).
\[T_G = \begin{cases} x\cdot T_{G-e} & \text{pokud $e$ je most,} \\ y\cdot T_{G-e} & \text{pokud $e$ je smyčka, } \\ T_{G-e} + T_{G/e} &\text{pokud $e$ není most ani smyčka.} \end{cases} \]Dále pro graf bez hran platí \(T_G = 1\).
Řešení
V prvním kroku se použije poslední možnost. Tedy \(T_{C_k} = T_{P_{k-1}} + T_{C_{k-1}}\).
Přes odebírání listu zjistíme, že \(T_{P_{k-1}} = x^{k-1}\), což vede na rekurenci \(T_{C_k} = x^{k-1} + T_{C_{k-1}}\)
Naposledy aplikujeme rekurenci na bigon, t.j. na dva vrcholy spojené dvěma hranami. Vznikne pak jeden vrchol smyčkou \(C_1\), kde \(T_{C_1} = y\).
Odpověď
Tutteho polynom cyklu je: \(T_{C_k}(x,y) = x^{k-1}+x^{k-2}+ \cdots+x^2+x+y\).