Izomorfismus tří grafů
Úloha číslo: 3568
Rozhodněte, zdali jsou si dva následující grafy \(G\) a \(H\) navzájem izomorfní:
Dále rozhodněte, který z nich je izomorfní třetímu grafu \(F\), danému předpisem: \( V_F=\binom{\{1,…,5\}}2\), \(E_F=\{(A,B): A\cap B=\emptyset\}\).
Nápověda
Nejprve otestujte nutné podmínky pro existenci izomorfismu. Poté zkuste izomorfismus zkonstruovat rozborem případů.
Graf \(F\) si nakreslete.
Řešení
Všechny tři grafy mají stejný počet vrcholů – 10, stejný počet hran – 15, i vrcholy stejných stupňů – ve všech mají všechny vrcholy stupeň 3.
Nutné nikoli však postačující podmínky jsou splněny.
Izomorfismus obecných grafů je obecně obtížná úloha a není ani pro ni znám efektivní algoritmus. V této úloze se ho můžeme pokusit najít „hrubou silou“, t.j. rozborem případů.
Zkusíme prostě zobrazit vrchol č. 1 v \(G\) a jeho tři sousedy na libovolný vrchol v \(H\) a jeho tři sousedy. (V našem případě vyjde libovolná volba, obecně by bylo třeba vyzkoušet všechny možnosti volby těchto čtyř obrazů v \(H\).)
Všimneme si, že vrcholy 1, 2, 5, 8 a 4 tvoří cyklus v \(G\), najdeme tedy v \(H\) cyklus délky pět, který obsahuje obrazy 1, 2 a 4 a na něj položíme obrazy vrcholů 5 a 8. V našem případě jsou dvě takové možnosti a obě vedou k výsledku. To obecně platit nemusí a pokud by některá volba selhala, je třeba vyzkoušet i ostatní.
Zbytek už je dán jednoznačně, protože doposud neobsazený soused obrazu 2 musí být obrazem 6. Podobně pro 4 a 9; 5 a 7; 8 a 10.
Zbývá mechanicky ověřit, zdali nalezené zobrazení zachovává hrany. V konstrukci jsme již využli 10 hran, postačí, ověříme-li, že je zachováno i zbývajících pět: \((5{,}7),(7{,}9),(9{,}6),(6{,}10),(10{,}5)\).
Fakt, že jsou zachovány nehrany plyne z toho, že zobrazení je prosté a oba grafy mají stejný počet hran.
Pro graf \(F\) postupujeme podobně, jen je nejprve vhodné si graf nakreslit.
Izomorfismus mezi \(F\) a \(H\) dostaneme např. složením izomorfismů mezi \(F\) a \(G\) a mezi \(G\) a \(H\). Můžeme si též uvědomit, že relace „být si izomorfní“ je ekvivalence (nejen na grafech).
Odpověď
Ano, všechny tři grafy jsou si navzájem izomorfní, jde o tzv. Petersenův graf.
Mezi \(G\) a \(H\) lze nalézt např. následující izomorfismus:
Jeden z možných izomorfismů \(f: G\to F\) lze popsat např. tabulkou:
\( \begin{array}{c|cccccccccc} u &1&2&3&4&5&6&7&8&9&10 \\ f(u) & \{1{,}2\} & \{3{,}4\} & \{3{,}5\} & \{4{,}5\} & \{1{,}5\} & \{2{,}5\} & \{2{,}4\} & \{2{,}3\} & \{1{,}3\} & \{1{,}4\} \end{array} \)
