#1 28. 11. 2011 15:26
Teorie grafů - isomorfismus
Zadání: Určit které z grafů jsou isomorfní, viz obrázek.
Vždycky jsem podobné příklady dělal tak, že jsem si nakreslil Hamiltonovské cyklus, potom do něho doplnil hrany a podle těchto cyklů už jsem poznal které jsou isomorfní a které ne. Ale u grafu G1 a G2 buď Hamiltonovský cyklus není nebo ho nemůžu najít. Můžete mi prosím poradit jestli je tak kterými vrcholy vede a pokud není tak jak jinak se to dá ověřit? Předem děkuju.
Offline
#2 30. 11. 2011 21:39
Re: Teorie grafů - isomorfismus
Erendil napsal(a):
Vždycky jsem podobné příklady dělal tak, že jsem si nakreslil Hamiltonovské cyklus, potom do něho doplnil hrany a podle těchto cyklů už jsem poznal které jsou isomorfní a které ne. Ale u grafu G1 a G2 buď Hamiltonovský cyklus není nebo ho nemůžu najít. Můžete mi prosím poradit jestli je tak kterými vrcholy vede a pokud není tak jak jinak se to dá ověřit?
Tak to jste doposud měl štěstí na grafy, které byly hamiltonovské.
Grafy 
ani 
takový cyklus neobsahují.
Jak to ověřit? Těžko, jedná se obecně o problém, pro který není znám polynomiální algoritmus. V tomto konkrétním případě bych si uměl představit několik zdůvodnění, ale ani jedno "triviální" s využitím probraných pojmů. Pro úspěšné řešení ZADANÉHO příkladu to není potřeba. Stačí ověřit nebo vyvrátit existenci jednotlivých isomorfismů.
Offline