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