Izomorfismus (graf)

Z Wikipedie, otevřené encyklopedie

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]