Izomorfismus (graf)

V teorii grafů řekneme, že jsou dva grafy izomorfní, pokud $\exists \ F\colon V(G)\to V(G'):\{x,y\}\in E(G)\Leftrightarrow \{f(x),f(y)\}\in E(G')$ .

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

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 $n$ . Pokud jsou grafy izomorfní, tak mají stejný počet uzlů stupně $n$ .

Další slabou podmínkou je stejná mohutnost množin uzlů a hran.

Externí odkazy editovat

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.

Pahýl

Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.