Tutteho polynom násobné hrany

Úloha číslo: 3286

Určete Tutteho polynom pro dva vrcholy spojené \(k\) hranami.

  • Nápověda

    Použijte rekurentní vztah pro výpočet Tutteho polynomu.

  • Řešení

    Označme dva vrcholy spojené \(k\) hranami \(B_k\). Dále označme vrchol s \(k\) smyčkami jako \(L_k\).

    V prvním kroku se použije poslední možnost, neboli \(T_{B_k} = T_{B_{k-1}} + T_{L_{k-1}}\).

    Odebíráním smyček zjistíme, že \(T_{L_{k-1}} = y^{k-1}\).

    Rekurence se zastaví po provedení na bigon (dva vrcholy spojené dvěma hranami). Vznikne pak cesta \(P_1\) a použije se první pravidlo, kde vyjde \(T_{P_1} = x\).

  • Odpověď

    Tutteho polynom násobné hrany je \(T_{B_k}(x,y) =x+y^{k-1}+y^{k-2}+ \cdots+y^2+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