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\).

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na trénování výpočtu
En translation
	Zaslat komentář k úloze