Nadřazené | Kódování a modelování » Modelování pomocí grafů » Izomorfní grafy |
Předcházející | Grafy sousednosti, Stejné vzory |
Cvičení
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).
Rozhodovačka
Rychlé procvičování výběrem ze dvou možností.
Izomorfní grafy (těžké)
76 zadání
Typicky zabere: 7 min
