| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
defar
Forumaš(ica)
Pridružen/a: 19. 01. 2004. (01:37:19)
Postovi: (152)16
|
 Postano: 22:03 čet, 2. 9. 2004 Naslov: generirajuce stablo grafa |
    |
|
|
generirajuce stablo grafa nije jedinstveno, oukej.
generirajuce stablo grafa nije jedinstveno cak niti za odredjen odabir korijena tog stabla(pocetnog cvora u jednom od dva na vjezbama prouCavana algoritma - nazvali smo ih "u sirinu" i "u dubinu", oba su rekurzivna..mogu kasnije raspisati ako bude potrebno.)
zadatak: dana je sahovska ploca 4*4, konj je na A1.
1. moze li se konj dovesti na A4?
2. na koja se sve polja konj moze dovesti (iz A1)?
3. pronadjite najmanji broj koraka u koji se konj moze dovesti na ta polja(iz gornjeg pitanja).
Izmodelirajte problem u teoriji grafova i odgovorite na pitanja!
polja ploce (A1, ..A4, B1...B4, ....D1..D4) su cvorovi grafa. odredi se jedno generirajuce stablo toga grafa.
iz grafa je "ocito" da se konj moze dovesti do A4, stovise, moze se dovesti do svih polja na ploci.
cini mi se i da je minimalni broj koraka u kojem se konj moze dovesti od odabranog pocetnog polja (korjena gen. stabla) do proizvoljno odabranog cvora grafa neovisan o izboru generirajuceg stabla. kao da su "isti cvorovi na istim nivoima u svakom generirajucem stablu".
ali mi nije potpuno jasno zasto bi bilo tako, ako je.
molim pomoc? :oops:
i, btw, ima li netko tko je redovito vodio biljeske na predavanjima prof. Caklovica, a tko bi iste ustupio na koji dan iduci tjedan (s poc. 06.09.)?
generirajuce stablo grafa nije jedinstveno, oukej.
generirajuce stablo grafa nije jedinstveno cak niti za odredjen odabir korijena tog stabla(pocetnog cvora u jednom od dva na vjezbama prouCavana algoritma - nazvali smo ih "u sirinu" i "u dubinu", oba su rekurzivna..mogu kasnije raspisati ako bude potrebno.)
zadatak: dana je sahovska ploca 4*4, konj je na A1.
1. moze li se konj dovesti na A4?
2. na koja se sve polja konj moze dovesti (iz A1)?
3. pronadjite najmanji broj koraka u koji se konj moze dovesti na ta polja(iz gornjeg pitanja).
Izmodelirajte problem u teoriji grafova i odgovorite na pitanja!
polja ploce (A1, ..A4, B1...B4, ....D1..D4) su cvorovi grafa. odredi se jedno generirajuce stablo toga grafa.
iz grafa je "ocito" da se konj moze dovesti do A4, stovise, moze se dovesti do svih polja na ploci.
cini mi se i da je minimalni broj koraka u kojem se konj moze dovesti od odabranog pocetnog polja (korjena gen. stabla) do proizvoljno odabranog cvora grafa neovisan o izboru generirajuceg stabla. kao da su "isti cvorovi na istim nivoima u svakom generirajucem stablu".
ali mi nije potpuno jasno zasto bi bilo tako, ako je.
molim pomoc? 
i, btw, ima li netko tko je redovito vodio biljeske na predavanjima prof. Caklovica, a tko bi iste ustupio na koji dan iduci tjedan (s poc. 06.09.)?
_________________
`To begin with, a dog's not mad. You grant that? 'Well, then,' the Cat went on, `you see, a dog growls when it's angry, and wags its tail when it's pleased. Now I growl when I'm pleased, and wag my tail when I'm angry. Therefore I'm mad.'
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (355F)16
Spol: 
Lokacija: /sbin/init
|
| Postano: 22:41 čet, 2. 9. 2004 Naslov: Re: generirajuce stablo grafa |
|
|
|
[quote="defar"]cini mi se i da je minimalni broj koraka u kojem se konj moze dovesti od odabranog pocetnog polja (korjena gen. stabla) do proizvoljno odabranog cvora grafa neovisan o izboru generirajuceg stabla. kao da su "isti cvorovi na istim nivoima u svakom generirajucem stablu".
ali mi nije potpuno jasno zasto bi bilo tako, ako je.[/quote]
Malo sam pozaboravljao te stvari :oops: ali cini mi se da nije tako. :|
Broj "1" oznacav korijen, "2" je cvor na koji smo skocili iz jedinice, itd. 8) Dakle, bridovi stabla su sve spojnice ([i]k[/i], [i]k[/i]+1). :D
[code:1]10 7 12 3
15 4 9 6
8 11 2 13
1 14 5 o
6 3 4 3
3 2 5 4
4 5 2 3
1 4 3 6[/code:1]
Dakle, u prvom imamo setnju, s jednim "promasenim" poljem u koje se lako skoci iz vrha 9 ili 11 :arrow: stablo. Broj koraka od 1 do 15 je 14. 8)
U drugom skocimo s 1 gdjegod mozemo i to su dvojke. Zatim iz svake dvojke gdjegod ide => trojke. Na taj nacin dobijemo pravi minimalni broj skokova od 1 do bilo kojeg polja (5). :D
A oba stabla su generirajuca jer sadrze sve vrhove grafa (ako sam dobro zapamtio definiciju generirajuceg stabla ;)).
| defar (napisa): | cini mi se i da je minimalni broj koraka u kojem se konj moze dovesti od odabranog pocetnog polja (korjena gen. stabla) do proizvoljno odabranog cvora grafa neovisan o izboru generirajuceg stabla. kao da su "isti cvorovi na istim nivoima u svakom generirajucem stablu".
ali mi nije potpuno jasno zasto bi bilo tako, ako je. |
Malo sam pozaboravljao te stvari ali cini mi se da nije tako. 
Broj "1" oznacav korijen, "2" je cvor na koji smo skocili iz jedinice, itd.  Dakle, bridovi stabla su sve spojnice (k, k+1). 
| Kod: | 10 7 12 3
15 4 9 6
8 11 2 13
1 14 5 o
6 3 4 3
3 2 5 4
4 5 2 3
1 4 3 6 |
Dakle, u prvom imamo setnju, s jednim "promasenim" poljem u koje se lako skoci iz vrha 9 ili 11  stablo. Broj koraka od 1 do 15 je 14.
U drugom skocimo s 1 gdjegod mozemo i to su dvojke. Zatim iz svake dvojke gdjegod ide ⇒ trojke. Na taj nacin dobijemo pravi minimalni broj skokova od 1 do bilo kojeg polja (5).
A oba stabla su generirajuca jer sadrze sve vrhove grafa (ako sam dobro zapamtio definiciju generirajuceg stabla  ).
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.  |
|
| [Vrh] |
|
defar
Forumaš(ica)
Pridružen/a: 19. 01. 2004. (01:37:19)
Postovi: (152)16
|
| Postano: 23:07 čet, 2. 9. 2004 Naslov: |
|
|
|
hm, ja sam se prebacila na jutarnji turnus (znaci sad mi je vec vrijeme za kakao i crtic prije spavanja), pa cu se tek ujutro upustit u detaljnije iscitavanje tvog odgovora na kojem iskreno zahvaljujem.
do tad...hm, generirajuce stablo je graf koji je stablo, ciji skup vrhova je jednak skupu vrhova zadanog grafa, ali i skup spojnica mu je podskup skupa spojniCa pocetnog grafa. ne znam jel ti to mijenja ista rezoniranje.
medjutim, ako je broj minimalnih koraka ovisan o izboru generirajuceg stabla, onda ne moze u biljeznici pisat kao odgovor na trece pitanje -"vidi s grafa" pored proizvoljnog gen. stabla (jerbo jedna zena ima u biljeznici jedno, a druga drugo) :/
ako postoji jedno na odredjeni nacin konstruirano g. stablo za koji je broj koraka do svakog cvora minimalan, onda super...al, uh, idem razmislit.
hm, ja sam se prebacila na jutarnji turnus (znaci sad mi je vec vrijeme za kakao i crtic prije spavanja), pa cu se tek ujutro upustit u detaljnije iscitavanje tvog odgovora na kojem iskreno zahvaljujem.
do tad...hm, generirajuce stablo je graf koji je stablo, ciji skup vrhova je jednak skupu vrhova zadanog grafa, ali i skup spojnica mu je podskup skupa spojniCa pocetnog grafa. ne znam jel ti to mijenja ista rezoniranje.
medjutim, ako je broj minimalnih koraka ovisan o izboru generirajuceg stabla, onda ne moze u biljeznici pisat kao odgovor na trece pitanje -"vidi s grafa" pored proizvoljnog gen. stabla (jerbo jedna zena ima u biljeznici jedno, a druga drugo) 
ako postoji jedno na odredjeni nacin konstruirano g. stablo za koji je broj koraka do svakog cvora minimalan, onda super...al, uh, idem razmislit.
_________________
`To begin with, a dog's not mad. You grant that? 'Well, then,' the Cat went on, `you see, a dog growls when it's angry, and wags its tail when it's pleased. Now I growl when I'm pleased, and wag my tail when I'm angry. Therefore I'm mad.'
|
|
| [Vrh] |
|
defar
Forumaš(ica)
Pridružen/a: 19. 01. 2004. (01:37:19)
Postovi: (152)16
|
| Postano: 23:15 čet, 2. 9. 2004 Naslov: |
|
|
|
ah, shvacam otprilike sto si htio reci, i ima mi smisla...mislis, ovaj "lepezasti" algoritam gdje se obradjuje "nivo po nivo" producira stablo s minimalnim brojem koraka do svakog cvora...al jos uvijek mi je sve to modeliranje tako "u zraku", pola toga ne znam kako da nazovem ili kazem...no, hvala puno, za sada smo na dobrom tragu, a uostalom, cini mi se da se kasnije i definiraju tocnije "minimalna stabla" i svasta.
ah, shvacam otprilike sto si htio reci, i ima mi smisla...mislis, ovaj "lepezasti" algoritam gdje se obradjuje "nivo po nivo" producira stablo s minimalnim brojem koraka do svakog cvora...al jos uvijek mi je sve to modeliranje tako "u zraku", pola toga ne znam kako da nazovem ili kazem...no, hvala puno, za sada smo na dobrom tragu, a uostalom, cini mi se da se kasnije i definiraju tocnije "minimalna stabla" i svasta.
_________________
`To begin with, a dog's not mad. You grant that? 'Well, then,' the Cat went on, `you see, a dog growls when it's angry, and wags its tail when it's pleased. Now I growl when I'm pleased, and wag my tail when I'm angry. Therefore I'm mad.'
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (355F)16
Spol:
Lokacija: /sbin/init
|
| Postano: 23:19 čet, 2. 9. 2004 Naslov: |
|
|
|
[quote="defar"]do tad...hm, generirajuce stablo je graf koji je stablo, ciji skup vrhova je jednak skupu vrhova zadanog grafa, ali i skup spojnica mu je podskup skupa spojniCa pocetnog grafa. ne znam jel ti to mijenja ista rezoniranje.[/quote]
Tocno takvoga sam ga i ja upamtio. :D
Spojnice u grafu su izmedju vrhova izmedju kojih konj moze doci u jednom skoku, ne? :)
[quote="defar"]medjutim, ako je broj minimalnih koraka ovisan o izboru generirajuceg stabla, onda ne moze u biljeznici pisat kao odgovor na trece pitanje -"vidi s grafa" pored proizvoljnog gen. stabla (jerbo jedna zena ima u biljeznici jedno, a druga drugo) :/[/quote]
Kad nacrtas moje grafove... Mozda sam negdje pogrijesio, ali ne vidim gdje... :? Sigurna si da nema jos neki uvjet na to stablo (ne opcenito generirajuce, nego bas u ovom slucaju)? :-k
[quote="defar"]ako postoji jedno na odredjeni nacin konstruirano g. stablo za koji je broj koraka do svakog cvora minimalan, onda super...al, uh, idem razmislit.[/quote]
Pa, to bi bilo ovo koje sam drugo generirao, a objasnih postupak. 8) Generiranje "u sirinu" (ono prvo je "u dubinu"). :D
| defar (napisa): | | do tad...hm, generirajuce stablo je graf koji je stablo, ciji skup vrhova je jednak skupu vrhova zadanog grafa, ali i skup spojnica mu je podskup skupa spojniCa pocetnog grafa. ne znam jel ti to mijenja ista rezoniranje. |
Tocno takvoga sam ga i ja upamtio.
Spojnice u grafu su izmedju vrhova izmedju kojih konj moze doci u jednom skoku, ne? 
| defar (napisa): | | medjutim, ako je broj minimalnih koraka ovisan o izboru generirajuceg stabla, onda ne moze u biljeznici pisat kao odgovor na trece pitanje -"vidi s grafa" pored proizvoljnog gen. stabla (jerbo jedna zena ima u biljeznici jedno, a druga drugo) |
Kad nacrtas moje grafove... Mozda sam negdje pogrijesio, ali ne vidim gdje...  Sigurna si da nema jos neki uvjet na to stablo (ne opcenito generirajuce, nego bas u ovom slucaju)? 
| defar (napisa): | | ako postoji jedno na odredjeni nacin konstruirano g. stablo za koji je broj koraka do svakog cvora minimalan, onda super...al, uh, idem razmislit. |
Pa, to bi bilo ovo koje sam drugo generirao, a objasnih postupak. Generiranje "u sirinu" (ono prvo je "u dubinu").
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju. |
|
| [Vrh] |
|
defar
Forumaš(ica)
Pridružen/a: 19. 01. 2004. (01:37:19)
Postovi: (152)16
|
| Postano: 23:21 čet, 2. 9. 2004 Naslov: |
|
|
|
aha, ovo ti je ploca!! :lol: :boliglava:
pa da, ustvari si ti to sasvim dobro primjerom objasnio.
stovise, dokazao da minimalan broj koraka ovisi o izboru generirajuceg stabla,
i naslutio da Se za bas tako kakojeopisano konstr. stablo dobije pravi min. br. skokova. :D
hvala, i laku nocicu. :morning:
p.s. nemas pojma koliko pocinjem cijeniti ungarov cjelokupni trud oko jasnoce i funkcionalnosti oznaka, ukljucujuci i opsezan predgovor s citavim grckim alfabetom na drugoj stranici :)
aha, ovo ti je ploca!!  
pa da, ustvari si ti to sasvim dobro primjerom objasnio.
stovise, dokazao da minimalan broj koraka ovisi o izboru generirajuceg stabla,
i naslutio da Se za bas tako kakojeopisano konstr. stablo dobije pravi min. br. skokova.
hvala, i laku nocicu. 
p.s. nemas pojma koliko pocinjem cijeniti ungarov cjelokupni trud oko jasnoce i funkcionalnosti oznaka, ukljucujuci i opsezan predgovor s citavim grckim alfabetom na drugoj stranici
_________________
`To begin with, a dog's not mad. You grant that? 'Well, then,' the Cat went on, `you see, a dog growls when it's angry, and wags its tail when it's pleased. Now I growl when I'm pleased, and wag my tail when I'm angry. Therefore I'm mad.'
|
|
| [Vrh] |
|
|
