Forum@DeGiorgi :: Pogledajte temu - generirajuce stablo grafa

through

[^/[Print]\]

Forum@DeGiorgi -> Matematičko modeliranje

#1: generirajuce stablo grafa Autor/ica: defar,

Postano: 22:03 čet, 2. 9. 2004
—
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? Embarassed

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

#2: Re: generirajuce stablo grafa Autor/ica: vsego, Lokacija: /sbin/init

Postano: 22:41 čet, 2. 9. 2004
—

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 Embarassed

ali cini mi se da nije tako. Neutral

Broj "1" oznacav korijen, "2" je cvor na koji smo skocili iz jedinice, itd. Cool

Dakle, bridovi stabla su sve spojnice (k, k+1). Very Happy

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. Cool

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). Very Happy

A oba stabla su generirajuca jer sadrze sve vrhove grafa (ako sam dobro zapamtio definiciju generirajuceg stabla Wink

#3: Autor/ica: defar,

Postano: 23:07 čet, 2. 9. 2004
—
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) Ehm?

ako postoji jedno na odredjeni nacin konstruirano g. stablo za koji je broj koraka do svakog cvora minimalan, onda super...al, uh, idem razmislit.

#4: Autor/ica: defar,

Postano: 23:15 čet, 2. 9. 2004
—
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.

#5: Autor/ica: vsego, Lokacija: /sbin/init

Postano: 23:19 čet, 2. 9. 2004
—

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. Very Happy

Spojnice u grafu su izmedju vrhova izmedju kojih konj moze doci u jednom skoku, ne? Smile

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) Ehm?

Kad nacrtas moje grafove... Mozda sam negdje pogrijesio, ali ne vidim gdje... Confused

Sigurna si da nema jos neki uvjet na to stablo (ne opcenito generirajuce, nego bas u ovom slucaju)? Think

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. Cool

Generiranje "u sirinu" (ono prvo je "u dubinu"). Very Happy

#6: Autor/ica: defar,

Postano: 23:21 čet, 2. 9. 2004
—
aha, ovo ti je ploca!! Laughing

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. Very Happy

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 Smile

Forum@DeGiorgi -> Matematičko modeliranje

output generated using printer-friendly topic mod. Vremenska zona: GMT + 01:00.

Stranica 1 / 1.