Izomorfismus (graf)
![ikona](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2c/Broom_icon.svg/48px-Broom_icon.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/11/Preferences-system.svg/16px-Preferences-system.svg.png)
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
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
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. |