Izomorfismus (graf)
V teorii grafů řekneme, že jsou dva grafy izomorfní, pokud .
Graf je jedním z příkladů množiny (vrcholů) a nějaké relace (množiny hran) na této množině, proto se opět jedná o zvláštní případ obecné definice izomorfismu.
Izomorfismus zachovává všechny důležité vlastnosti grafu – zobrazuje každý podgraf na izomorfní podgraf, cestu opět na cestu, kružnici opět na kružnici, izomorfní graf lze obarvit stejným způsobem, jako původní graf.
Slabé podmínky[editovat | editovat zdroj]
Podmínky využijeme při posuzování vlastnosti izomorfismu u dvou grafů. Podmínky jsou označovány jako slabé, protože jejich splnění nezaručuje vlastnost izomorfismu.
Uvažujme libovolné přirozené číslo . Pokud jsou grafy izomorfní, tak mají stejný počet uzlů stupně .
Další slabou podmínkou je stejná mohutnost množin uzlů a hran.
Externí odkazy[editovat | editovat zdroj]
- Obrázky, zvuky či videa k tématu Izomorfismus na Wikimedia Commons
- KOLÁŘ, Josef. Teoretická informatika. Praha: [s.n.], 2004. ISBN 80-900853-8-5. Kapitola 2.1, s. 18.