Matematické Fórum

pawell · 27. 01. 2010 15:14

Dobrý den,
chtěl bych poprosit někoho o radu.
Když mám zadáno: minimální kód stromu a obrázek s grafem stromu => mám porovnat izomorfismus mezi nimi. Tak jak se má postupovat?
Mám si zjistit minimální kód toho stromu na obrázku a porovnat s se zadaným minimálním kódem?
Nebo nakreslit strom se zadným minimálním kódem a porovnat s obrázkem? Ale nevím jak se zpětně kreslí strom když znám minimální kód.
Předem dík za odpověď.

Kondr · 27. 01. 2010 18:05

http://www.fi.muni.cz/~hlineny/Vyuka/GT … ect--4.pdf , algoritmus 4.12 -- podle něj sestav kód k obrázku a porovnej kódy.

petrkovar · 28. 01. 2010 21:31

↑ pawell:Ono to na písemce ;-) šlo řešit oběma způsoby. To, co zmiňuje Kondr, je nejjednodušší a samozřejmě preferovaný postup. Mimochodem odkaz vede na skripta, která používáme v DiM taky, tak stačilo nalistovat v literatuře, která je uvedená v sylabu na webu našeho předmětu.
Druhý zmíněny způsob řešení (nejprve nakreslit a pak porovnávat obrázky) vyžaduje, abychom podle definice isomorfismu našli isomorfismus, označený třeba f. To znamená, že v každém obrázku se pojmenují vrcholy, popíše se bijekce, která vrcholy jednoho stromu převede na vrcholy druhého stromu a ověří se hlavní vlastnost isomorfismu (zobrazení f) a sice že zachovává sousednost.
Konzultační hodiny mám v pondělí a ve čtvrtek (pokud není zkouška).

Matematické Fórum

#1 27. 01. 2010 15:14

Izomorfismus stromů

#2 27. 01. 2010 18:05

Re: Izomorfismus stromů

#3 28. 01. 2010 21:31

Re: Izomorfismus stromů

Zápatí