Počet acyklických orientací
Úloha číslo: 4316
Spočítejte, kolik má úplný graf na \(n\) vrcholech acyklických orientací.
Řešení
Vrcholy grafu očíslujeme od 1 do \(n\). Sestrojíme bijekci mezi permutacemi na množině \(\{1,\ldots,n\}\) a acyklickými orientacemi grafu.
Každou acyklickou orientaci lze topologicky uspořádat, což dá permutaci vrcholů. Jelikož každé dva vrcholy jsou spojeny hranou, topologické uspořádání je určeno jednoznačně.
Každá permutace \(\pi\) určuje orientaci: pro dvojici vrcholů \(\{i,j\}\) se podíváme, na kolikáté pozici leží v permutaci, a hranu zorientujeme z menší pozice do větší.
Odpověď
Úplný graf \(K_n\) má \(n!\) acyklických orientací.
