Izomorfní grafy

umime.to/MZG

Nadřazené	Kódování a modelování » Modelování pomocí grafů » Izomorfní grafy
Předcházející	Grafy sousednosti, Stejné vzory

Cvičení

Rozhodovačka

Pexeso

Grafy jsou izomorfní, pokud mají stejný počet vrcholů a „stejná spojení“. Zde nebudeme rozebírat přesnou matematickou definici (tu najdete třeba zde), ale jen intuitivní představu. Představme si vrcholy grafu jako dřevěné kolíčky a hrany jako gumičky mezi nimi. S kolíčky a gumačkami můžeme hýbat a pořád je to „stejný graf“, protože vztah spojení zůstává zachován. Izomorfismus grafů se týká právě tohoto typu „stejnosti“. Můžeme s jedním grafem hýbat tak, až z něj dostaneme ten druhý?

Cvičení na izomorfní grafy nejsou užitečná ani tak kvůli pojmu samotnému, ale především jako trénink abstrakce. Při hledání izomorfních grafů musíme odhlédnout od detailů (jak přesně jsou hrany zakresleny) a soustředit se pouze na důležité vztahy (kdo je s kým spojen).