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 18. 06. 2011 20:00 — Editoval Berny (19. 06. 2011 11:04)
Homomorfismy mezi grafy
Ahoj, chtel bych poprosit o radu. Mam cca. takovydle zadani, a nevim si s ním rady.
Vím, že pokud dělam homorfismus mezi grafy. Tak kdyz existuje hrana mezi vrcholy A a B v grafu G , musi existovat i v Grafu H. ale jak to aplikovat, to nevím.
Najděte homomorfismy mezi grafy: 
Uploaded with ImageShack.us
U grafu 1 a 2, jedine co mi napada je todle:
A B E C D
1 2 3 4 5
Ale jen tipuju.
Díky moc za pomoc.
Offline
#5 03. 06. 2012 20:48 — Editoval OiBobik (03. 06. 2012 20:52)
- OiBobik
- Moderátor
- Místo: Brno/Praha
- Příspěvky: 1013
- Škola: MFF UK Mat. struktury
- Pozice: student
- Reputace: 82
Re: Homomorfismy mezi grafy
↑ hamii:
Žádné extra hezké řešení to pravděpodobně nemá...
Takové základní pozorování je, že v grafovém homomorfismu se musí trojúhelník zobrazit na trojúhelník.
To mi třeba už dost jasně určuje, jak vypadají homomorfismy v druhém případě:
Graf, do nějž mají homomorfismy vést, má trojúhelníky dva, ovšem snadno se nahlédne, že se na ně nemohou trojúhelníky vzorového grafu zobrazit prostě (tj. jeden na jeden a druhý na druhý) - třeba už jen proto, že vzorový graf má jen 4 vrcholy a kdyby obraz případného homomorfismu pokrýval oba trojúhelníky v grafu, kam má homomorfismus vést, nutně by zobrazoval 4 vrcholy na 5, přičemž takové zobrazení neexistuje.
Takže jediná možnost je: obraz uvažovaného grafu v libovolném homomorfismu je trojúhelník, přitom homomorfismus jistě nutně zobrazuje vrcholy A a D na nějaký společný vrchol a vrcholy B,C,D na tři různé vrcholy. Když se trochu započítá, tak dojdeme k počtu různých homomorfismů 2*3*2=12
(nejprve vyberu jeden ze dvou trojúhelníků, na který se graf zobrazí. Potom lze třemi způsoby vybrat vrchol, odpovídající A, následně vždy dvěma způsoby vrchol, odpovídající B a zbytek je určen jednoznačně).
No a první případ se bude dělat nějak analogicky.
"The first rule of Tautology Club is the first rule of Tautology Club." [xkcd]
Offline