Ekvivalence podle izomorfismu
Úloha číslo: 3574
Ukažte, že izomorfismus dává ekvivalenci na grafech s \(V_G=\{1,…,n\}\).
Zjistěte pro jaké grafy má jeho třída ekvivalence nejvíce prvků a nalezněte příklad takového grafu pro vhodné \(n\).
Řešení
Relace "být" izomorfní je
- reflexivní – každý graf je izomorfní sám sobě přes identitu
- symetrická – je li \(f: G\to H\) izomorfismus, potom zobrazení \(f^{-1}: H\to G\) je také izomorfismem (k bijekci existuje inverzní zobrazení, a zachovávání hran i nehran u \(f\) vede k zachovávání hran i nehran u \(f^{-1}\))
-
tranzitivní – jsou-li \(f: F\to G\) a \(g: G\to H\) izomorfismy, potom jejich složení \(g\circ f\) je bijekce, co zachovává hrany i nehrany a tedy izomorfismus.
(Formálně \((u,v)\in E_F \Leftrightarrow (f(u),f(v))\in E_G \Leftrightarrow (g(f(u)),g(f(v)))=((g\circ f)(u),(g\circ f)(v))\in E_H\).)
Nejvíce izomorfních grafů, konkrétně \(n!\), na množině \(\{1,…,n\}\) nalezneme u strnulých grafů, protože každé očíslování vrcholů dává jiný graf.
Příkladem strnulého grafu pro \(n\ge 6\) je \(P_n\cup\{(2{,}4)\}\), tedy cesta na vrcholech, kde druhý a čtvrtý vrchol jsou spojené hranou.
1 se musí zobrazit sám na sebe, protože je jediný stupně jedna sousedící s vrcholem stupně tři, díky němu se 2 zobrazí sám na sebe, 4 také sám na sebe, protože nezbývá jiný vrchol stupně tři, atd.
Rozborem případů se lze přesvědčit, že na nejvýše pěti vrcholech žádné strnulé grafy nejsou s vyjímkou \(K_1\).
