Izomorfismus (graf)

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

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.

Reference[editovat | editovat zdroj]

  • KOLÁŘ, Josef. Teoretická informatika. Praha: [s.n.], 2004. ISBN 80-900853-8-5. Kapitola 2.1, s. 18.