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 27. 01. 2010 15:14

pawell
Zelenáč
Příspěvky: 10
Reputace:   
 

Izomorfismus stromů

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ěď.

Offline

  • (téma jako vyřešené označil(a) pawell)

#2 27. 01. 2010 18:05

Kondr
Veterán
Místo: Linz, Österreich
Příspěvky: 4247
Škola: FI MU 2013
Pozice: Vývojář, JKU
Reputace:   38 
 

Re: Izomorfismus stromů

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.


BRKOS - matematický korespondenční seminář pro střední školy

Offline

 

#3 28. 01. 2010 21:31

petrkovar
Veterán
Místo: Ostrava/Krmelín
Příspěvky: 1012
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: Izomorfismus stromů

↑ 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).

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson