Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#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