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í.
Obtížnost: Středně těžká úloha
Úloha řešená úvahou
En translation
	Zaslat komentář k úloze