Matematické Fórum

Zdravím, moje zadání bylo:

Nakreslete všechny neizomorfní stromy se šesti vrcholy.

--------------------------------------------------------------------------------------------------------------------------------------------------------------

Po nějakém zkoušení jsem dokázal všech 6 neizomorfních stromů nakreslit, ale potřeboval bych nějak odvodit že jich je právě 6 a ne více !

Vím, že všech stromů je 6^4 = 1296

Na netu jsem našel, že součet

[mathjax] 6! / Aut(G) [/mathjax]

pro každý neizomorfní graf dá počet všech izomorfních grafů, takže bych měl potvrzeno že jich není více.


Aut(G) je velikost automorfismu stromu. Potřeboval bych nějaký vzoreček na výpočet automorfismu pro každý neizomorfní strom s 6 vrcholy. (případně i srozumitelné vysvětlení o co se jedná, z načtených anglických skript jsem trošku jelen :) )

Znám výsledky :
Aut(G1) = 120     zde jsem odvodil, že jde o 5! neboli (n-1)!      n-počet vrcholů
Aut(G2) = 6
Aut(G3) = 2
Aut(G4) = 8
Aut(G5) = 2
Aut(G6) = 2

Poté hodíme každou hodnotu do výše uvedeného vzorečku např pro 120:    6! / 120 = 6

a hodnoty sečteme:
6 + 120 + 360 + 90 + 360 + 360 = 1296 = 6^4       tím je ověřeno, že jsou všechny a žádný graf jsem nevynechal.

Konkrétní řešení v angličtině

Předem děkuji za váš čas.