Izomorfismus (graf)

Tento článek potřebuje úpravy.

Můžete Wikipedii pomoci tím, že ho vylepšíte. Jak by měly články vypadat, popisují stránky Vzhled a styl, Encyklopedický styl a Odkazy.

---

Konkrétní problémy: definice uvádí matem. symboly bez vysvětlení jejich významu; vysvětlit symboly a celý pojem též slovně, uvést příklad izomorf. grafů (viz wiki-en)

V teorii grafů řekneme, že jsou dva grafy izomorfní, pokud ${\displaystyle \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.

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

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

• Obrázky, zvuky či videa k tématu izomorfismus grafů na Wikimedia Commons
• KOLÁŘ, Josef. Teoretická informatika. Praha: [s.n.], 2004. ISBN 80-900853-8-5. Kapitola 2.1, s. 18. 

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.