Matematické Fórum

Qeekin · 24. 01. 2015 20:17

Ahoj, z tohoto článku vyplývá, že graf S4 (druhá sada obrázků) má celkem 6 automorfismů.

Definice automorfismu říká, že se jedná o izomorfismus sám na sebe. Izomorfismus je definován $(u,v)\in E_{1} \Leftrightarrow (f(u), f(v))\in E_{2}$ , pro grafy $G_{1} = (V_{1},E_{1})$ a $G_{2} = (V_{2},E_{2})$ , kde f je zobrazení.

Vycházím z grafu

Pak zobrazení f (prohození uzlu 1 a 4):
f(1) = 4
f(4) = 1
f(2) = 2
f(3) = 3

není automorfismem, ale pokud si to dosadím do definice, tak mi vychází že je.

Může mi někdo vysvětlit kde dělám chybu?

o.neill

Podmínka musí platit pro každou dvojci vrcholů z grafu. Ve tvém příkladě je třeba
$(2,4)\in E,\quad\text{ale}\quad(f(2),f(4))=(2,1)\not\in E$

Qeekin · 27. 01. 2015 13:40

Ale hrany v neorientovaném grafu jsou množina dvouprvkových množin. Tedy přesněji
$\{2,4\}\in E_{1}\quad\text{a}\quad\{f(2),f(4)\}=\{2,1\}\in E_{2}\quad\text{protože}\quad\{2,1\} = \{1,2\}$

o.neill · 27. 01. 2015 14:07

No dobře, to jsem napsal špatně, koukal jsem na definici ve tvém úvodním příspěvku, nicméně zdůvodnění je stejné. Hrana {2,1} v tom grafu přece není. A zobrazujeme graf sám na sebe, takže zde není žádné E₁ a E₂, ale jenom jedna množina E.

Matematické Fórum

#1 24. 01. 2015 20:17

Automorfismus grafů

#2 25. 01. 2015 14:44 — Editoval o.neill (25. 01. 2015 14:45)

Re: Automorfismus grafů

#3 27. 01. 2015 13:40

Re: Automorfismus grafů

#4 27. 01. 2015 14:07

Re: Automorfismus grafů

Zápatí