Forum@DeGiorgi :: Pogledajte temu - nejasnoća u vezi Kruskala

through

[^/[Print]\]
Idite na 1, 2 Sljedeće :| |:
Forum@DeGiorgi -> Diskretna matematika

#1: nejasnoća u vezi Kruskala Autor/ica: amorphis, Lokacija: zg

Postano: 22:14 pet, 8. 2. 2008
—
prvo se odredi brid minimalne težine (bilo koji ako ih je više s istom težinom) i u svakom drugom koraku se od preostalih bira novi brid opet minimalne težine, na vježbama su težine bile tako raspoređene da su bridovi uvijek bili povezani kako su im težine rasle, zanima me ako imam npr težine 3&4 ali ti bridovi nemaju zajednički vrh, krenem od brida 3 i da li onda uzimam brid 4 ili biram onaj minimalne težine, ali koji kreće iz onog brida težine 3 odnosno koji ima zajednički vrh sa bridom težine 3?

(nadam se da kužite što želim pitat)

#2: Autor/ica: Ančica,

Postano: 0:08 sub, 9. 2. 2008
—
Ja sam to tako rjesavala da gledas sve najmanje, ne moraju oni biti iz istog vrha pa povecavas, a na kraju dobijes povezan bez ciklusa..

#3: Autor/ica: ma,

Postano: 11:38 sub, 9. 2. 2008
—

Ančica (napisa):

Ja sam to tako rjesavala da gledas sve najmanje, ne moraju oni biti iz istog vrha pa povecavas, a na kraju dobijes povezan bez ciklusa..

da. mislim da je tako. uzimaš redom najmanje težine, pritom pazeći da ne zatvoriš ciklus.

npr - u nekom slučaju, prva dva odabrana brida ne moraju imati zajednički vrh

#4: Autor/ica: Luuka, Lokacija: Hakuna Matata

Postano: 16:58 sub, 9. 2. 2008
—
Ja krenuh sa tim stablima polako i odmah naiđoh na nejasnoću...u attachment stavljam zadatak sa vježbi, prvi primjer kod Kruskala. Tamo smo našli 2 rješenja, al ja nađoh i treće...(pretp da sam dobro prepisao s ploče Smile

). Jesu li 2 grafa u 2.redu kao jednaka jer su izomorfni? Gore lijevo je cijeli graf.

DSC00035.JPG

Description:

Filesize:

22.74 KB

Viewed:

222 Time(s)

#5: Autor/ica: ma,

Postano: 17:08 sub, 9. 2. 2008
—
pa ja baš ne bi govorio o izomorfnosti kad bridovi imaju težinu. ne mislim da su jednaki... Confused

#6: Autor/ica: Luuka, Lokacija: Hakuna Matata

Postano: 17:11 sub, 9. 2. 2008
—
Ne znam da li se kod izomorfnosti spominje težina bridova...samo da je jednak broj vrhova, bridova, čuva se susjedstvo, stupanj vrhova itd. Zbunjen sam... Confused

#7: Autor/ica: ma,

Postano: 17:52 sub, 9. 2. 2008
—

Luuka (napisa):

Ne znam da li se kod izomorfnosti spominje težina bridova...samo da je jednak broj vrhova, bridova, čuva se susjedstvo, stupanj vrhova itd. Zbunjen sam... Confused

pa samo želim reć da mi je glupo govorit o izomorfnosti kad bridove ne gledamo jednako.

ona tvoja dva grafa u dnu iz attachmenta jesu izomorfna, ali ja ih ne bih smatrao jednim rješenjem samo zato što su izomorfni. Confused

po meni su to dva različita rješenja, jer su drugi bridovi u igri (bridove razlikujemo), a to što je tu slučajno ispalo da su i njihove cijene jednake, to je drugo...

ako uzmeš još i podgraf onog početnog grafa s bridovima {{A,B},{B,E},{B,C},{C,D}}, on jest izomorfan s ona tvoja donja dva, ali upravo zbog drukčije cijene, ne bih rekao da su 'jednaki'.. Rolling Eyes

#8: Autor/ica: Luuka, Lokacija: Hakuna Matata

Postano: 18:03 sub, 9. 2. 2008
—
Ne bih ni ja rekao da su izomorfni, baš zbog težine bridova, al razlog mojoj zbunjenosti je taj da smo na vježbama našli 2 razapinjujuća stabla s najmanjom težinom, a ja sam našo i treće koristeći isti algoritam...sve 3 su stabla, imaju istu težinu, a različiti su pa si pokušavam objasnit zašt ja imam 3 a Maroje na vježbama našo 2...jel to on fulo ili ja negdje griješim ? Confused

#9: Autor/ica: ma,

Postano: 18:26 sub, 9. 2. 2008
—

Luuka (napisa):

Ne bih ni ja rekao da su izomorfni, baš zbog težine bridova, al razlog mojoj zbunjenosti je taj da smo na vježbama našli 2 razapinjujuća stabla s najmanjom težinom, a ja sam našo i treće koristeći isti algoritam...sve 3 su stabla, imaju istu težinu, a različiti su pa si pokušavam objasnit zašt ja imam 3 a Maroje na vježbama našo 2...jel to on fulo ili ja negdje griješim ? Confused

aha. to te muči Smile

pa kolko sam vidio - to tvoje mi se čini ok. možda maroje nije ni htio ispisati sva rješenja nego samo naglasiti tim primjerom da ih može biti i više od jednog. Vidra

#10: Autor/ica: Luuka, Lokacija: Hakuna Matata

Postano: 18:41 sub, 9. 2. 2008
—
I primovim alg sam dobio 3 stabla...(ustvari 4 al 2 su ista)....dakle Maroje je zaboravio napomenut da su tri...sad mi je lakše pri srcu Laughing

#11: Autor/ica: amorphis, Lokacija: zg

Postano: 13:13 ned, 10. 2. 2008
—
a što ako imam više bridova iste težine, ali koji nisu međusobno spojeni (npr 1.zd iz zadaće), svaki brid duljine 4 uzimam ponovo (ako ne tvore ciklus) ili kad uzmem jedan 4 onda ih sve iste težine 'eliminiram' dalje?

(možda je glupo pitanje, ali stvarno ne želim ništa pretpostavljat prije kolokvija)

#12: Autor/ica: napraviculom, Lokacija: Scranton

Postano: 13:26 ned, 10. 2. 2008
—
http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/PrimApp.shtml?demo3
http://students.ceid.upatras.gr/~papagel/project/kruskal.htm

ovo ce pomoc

#13: Autor/ica: Luuka, Lokacija: Hakuna Matata

Postano: 13:46 ned, 10. 2. 2008
—

amorphis (napisa):

a što ako imam više bridova iste težine, ali koji nisu međusobno spojeni (npr 1.zd iz zadaće), svaki brid duljine 4 uzimam ponovo (ako ne tvore ciklus) ili kad uzmem jedan 4 onda ih sve iste težine 'eliminiram' dalje?

(možda je glupo pitanje, ali stvarno ne želim ništa pretpostavljat prije kolokvija)

Nije bitno jel su ti u tom trenutku povezani. Povezanost je bitna kod Prima. Kruskal uzima brid najmanje težine pazeći da se ne dobije ciklus i to se radi dok graf nije povezan. Prim gleda povezanost u svakom koraku. Bar sam ja to tak skužio

#14: Autor/ica: desire,

Postano: 12:22 pon, 11. 2. 2008
—
Da ne otvaram novu temu... Imam pitanje u vezi 2 zadatka sa vježbi.

1. Koliko ima svih mulitgrafova čiji je skup vrhova

, a svi imaju točno m bridova.

Rj: dvočlanih multiskupova skupa

ima

Svaki brid mozemo prodruziti multiskupu.

Dobivamo (n+1 povrh 2 + m -1) povrh m (ne ide mi bas latex danas pa pisem dalje ovak, sorry Smile

)

Ne kuzim zasto gledamo dvoclane multiskupove, i zasto ih ima bas toliko. Jasno mi je da je ovo n kraju samo br rjesenja jednadzebe, ali kako uopce dodjemo do nje? Confused

2. Pokazite da jednostavan graf s p vrhova, gdje svi vrhovi imaju stupanj >=1/2*(p-1) mora biti povezan.

Rj: Pretp suprorno: postoji nepovezan graf sa ovim svojstvom
neka su

komponetne povezanosti
postoji

t.d. je broj vrhova od

Uzmimo vrh x iz

Ukupno vrhova u

ima

Uopce ne kuzim sto smo mi tu dokazivali ni kako pa ako mi netko moze objasniti zasto to ovako ide....

Tnx Smile

#15: Autor/ica: amorphis, Lokacija: zg

Postano: 14:52 pon, 11. 2. 2008
—
Maroje je definirao multiskup M kao M={V,E}={n,m} (jer je u grafu n vrhova i m bridova) , dozvolio je petlje i višestruko ponavljanje bridova u grafu nakon čega je prebrojavao koliko bridova različite vrste postoji; bridova ima (n povrh 2) komada (jer svaki brid 'radi' sa 2 vrha), petlji ima (n povrh 1) komada (jer svaka petlja 'radi' samo sa jednim vrhom) što kad se sumira daje kao ukupan broj bridova upravo ((n+1) povrh 2), nakon toga Maroje tvrdi da je x1=broj brodova 1. vrste (npr petlje), x2=br. bridova 2. vrste (npr višestruki bridovi) odnosno xi=br. bridova i-te vrste i kad ih sumira (x1+x2+...+xi) mora ih biti točno m (jer je to uvijet zadatka), a to se onda riješi isto kao i zd. tipa 'koliko ima cijelobrojnih rješenja jdžbe' (imaš sličan zd na vježbama od 31.10.2007.) i (dobiješ (m+(n+1 povrh 2)-1)povrh m)

#16: Autor/ica: amorphis, Lokacija: zg

Postano: 15:27 pon, 11. 2. 2008
—
za drugi zadatak;

pretpostavi se suprotno, tj. postoji graf sa zadanim svojstvom, ali koji nije povezan, ako nije povezan znači da postoje komponente povezanosti (v1, v2, ..., vn) i među njima mora biti barem jedna čiji je broj vrhova manji od (ili jednak) 'najmanjem cijelom od P/2' jer ako bi sve komponente imale više od toliko vrhova onda bi i ukupna suma vrhova bila veća od P, a što ne smije biti zbog uvjeta zadatka, neka je dalje stupanj (proizvoljnog) vrha x>=(P-1)/2, neka je taj x iz komponente v1, jer je |v1|<=P/2 znači da x smije imati najviše 'najmanje cijelo od P/2' susjeda što znači da je 'najmanje cijelo od (P/2)' - 1<=(P-1)/2 što je kontradikcija s uvjetom zadatka i vrijedi da graf zbilja mora biti povezan

#17: Autor/ica: sun,

Postano: 19:47 pon, 11. 2. 2008
—

Luuka (napisa):

Ja krenuh sa tim stablima polako i odmah naiđoh na nejasnoću...u attachment stavljam zadatak sa vježbi, prvi primjer kod Kruskala. Tamo smo našli 2 rješenja, al ja nađoh i treće...(pretp da sam dobro prepisao s ploče Smile

). Jesu li 2 grafa u 2.redu kao jednaka jer su izomorfni? Gore lijevo je cijeli graf.

Luuka krivo si prepisao brid CD ti je tezine 3

#18: Autor/ica: Luuka, Lokacija: Hakuna Matata

Postano: 19:56 pon, 11. 2. 2008
—
Onda ok. Laughing

I mislio sam da je tak nešto posrijedi...

A jel netko zna rješenje onog što gore upitah ?

edit: tamo gore= http://degiorgi.math.hr/forum/viewtopic.php?p=93222#93222

Wink

Zadnja promjena: Luuka; 21:26 pon, 11. 2. 2008; ukupno mijenjano 1 put.

#19: Autor/ica: desire,

Postano: 21:00 pon, 11. 2. 2008
—
Hvala amorphis. Sarma ++. Smile

#20: Autor/ica: buzov5, Lokacija: zg

Postano: 10:50 čet, 14. 2. 2008
—
malo kasnim al valjda nije bad.
zar nije kod kruskala da se uzimaju bridovi
najmanje tezine ali iz razlicitih komponenti
povezanosti? ako je, kako vi to onda pazite
da ne zatvorite ciklus? a ono sto neko kaze
da su bili povezani kako su im tezine rasle,
sta nije to primov algoritam?

Forum@DeGiorgi -> Diskretna matematika

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

Idite na 1, 2 Sljedeće :| |: Stranica 1 / 2.