Search
 
 
  Engleski
 
 
 
Open in this window (click to change)
Forum@DeGiorgi: Početna
Forum za podršku nastavi na PMF-MO
Login Registracija FAQ Smajlići Članstvo Pretražnik Forum@DeGiorgi: Početna

nejasnoća u vezi Kruskala
WWW:
Idite na 1, 2  Sljedeće
Moja sarma
 
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji 2. godine -> Diskretna matematika
Prethodna tema :: Sljedeća tema  
Autor/ica Poruka
amorphis
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 10. 02. 2007. (23:15:13)
Postovi: (101)16
Sarma = la pohva - posuda
= 19 - 11
Lokacija: zg

PostPostano: 22:14 pet, 8. 2. 2008    Naslov: nejasnoća u vezi Kruskala Citirajte i odgovorite

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


[Vrh]
Korisnički profil Pošaljite privatnu poruku
Ančica
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 01. 12. 2006. (16:12:53)
Postovi: (F6)16
Spol: žensko
Sarma = la pohva - posuda
26 = 31 - 5

PostPostano: 0:08 sub, 9. 2. 2008    Naslov: Citirajte i odgovorite

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



_________________
..a jooooooj..
[Vrh]
Korisnički profil Pošaljite privatnu poruku
ma
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 27. 01. 2007. (12:06:50)
Postovi: (347)16
Spol: muško
Sarma = la pohva - posuda
58 = 89 - 31

PostPostano: 11:38 sub, 9. 2. 2008    Naslov: Citirajte i odgovorite

[quote="Ančica"]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..[/quote]

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



_________________
ima let u finish
[Vrh]
Korisnički profil Pošaljite privatnu poruku
Luuka
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 13. 02. 2007. (20:34:54)
Postovi: (925)16
Spol: muško
Sarma = la pohva - posuda
188 = 301 - 113
Lokacija: Hakuna Matata

PostPostano: 16:58 sub, 9. 2. 2008    Naslov: Citirajte i odgovorite

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 :) ). Jesu li 2 grafa u 2.redu kao jednaka jer su izomorfni? Gore lijevo je cijeli graf.
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.



_________________
"Bolje bi prolazio na faxu da sam na drogama nego na netu" - by a friend of mine
"Poslije spavanja doma spavanje bilo di mi je najdraža stvar" - by the same guy Very Happy



DSC00035.JPG
 Description:
 Filesize:  22.74 KB
 Viewed:  224 Time(s)

DSC00035.JPG


[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
ma
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 27. 01. 2007. (12:06:50)
Postovi: (347)16
Spol: muško
Sarma = la pohva - posuda
58 = 89 - 31

PostPostano: 17:08 sub, 9. 2. 2008    Naslov: Citirajte i odgovorite

pa ja baš ne bi govorio o izomorfnosti kad bridovi imaju težinu. ne mislim da su jednaki... :?
pa ja baš ne bi govorio o izomorfnosti kad bridovi imaju težinu. ne mislim da su jednaki... Confused



_________________
ima let u finish
[Vrh]
Korisnički profil Pošaljite privatnu poruku
Luuka
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 13. 02. 2007. (20:34:54)
Postovi: (925)16
Spol: muško
Sarma = la pohva - posuda
188 = 301 - 113
Lokacija: Hakuna Matata

PostPostano: 17:11 sub, 9. 2. 2008    Naslov: Citirajte i odgovorite

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



_________________
"Bolje bi prolazio na faxu da sam na drogama nego na netu" - by a friend of mine
"Poslije spavanja doma spavanje bilo di mi je najdraža stvar" - by the same guy Very Happy
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
ma
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 27. 01. 2007. (12:06:50)
Postovi: (347)16
Spol: muško
Sarma = la pohva - posuda
58 = 89 - 31

PostPostano: 17:52 sub, 9. 2. 2008    Naslov: Citirajte i odgovorite

[quote="Luuka"]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... :?[/quote]

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. :? 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'.. :roll:
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



_________________
ima let u finish
[Vrh]
Korisnički profil Pošaljite privatnu poruku
Luuka
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 13. 02. 2007. (20:34:54)
Postovi: (925)16
Spol: muško
Sarma = la pohva - posuda
188 = 301 - 113
Lokacija: Hakuna Matata

PostPostano: 18:03 sub, 9. 2. 2008    Naslov: Citirajte i odgovorite

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 ? :?
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



_________________
"Bolje bi prolazio na faxu da sam na drogama nego na netu" - by a friend of mine
"Poslije spavanja doma spavanje bilo di mi je najdraža stvar" - by the same guy Very Happy
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
ma
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 27. 01. 2007. (12:06:50)
Postovi: (347)16
Spol: muško
Sarma = la pohva - posuda
58 = 89 - 31

PostPostano: 18:26 sub, 9. 2. 2008    Naslov: Citirajte i odgovorite

[quote="Luuka"]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 ? :?[/quote]

aha. to te muči :) 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:
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



_________________
ima let u finish
[Vrh]
Korisnički profil Pošaljite privatnu poruku
Luuka
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 13. 02. 2007. (20:34:54)
Postovi: (925)16
Spol: muško
Sarma = la pohva - posuda
188 = 301 - 113
Lokacija: Hakuna Matata

PostPostano: 18:41 sub, 9. 2. 2008    Naslov: Citirajte i odgovorite

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 :lol:
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



_________________
"Bolje bi prolazio na faxu da sam na drogama nego na netu" - by a friend of mine
"Poslije spavanja doma spavanje bilo di mi je najdraža stvar" - by the same guy Very Happy
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
amorphis
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 10. 02. 2007. (23:15:13)
Postovi: (101)16
Sarma = la pohva - posuda
= 19 - 11
Lokacija: zg

PostPostano: 13:13 ned, 10. 2. 2008    Naslov: Citirajte i odgovorite

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


[Vrh]
Korisnički profil Pošaljite privatnu poruku
napraviculom
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 01. 02. 2007. (16:40:37)
Postovi: (71)16
Spol: muško
Sarma = la pohva - posuda
14 = 16 - 2
Lokacija: Scranton

PostPostano: 13:26 ned, 10. 2. 2008    Naslov: Citirajte i odgovorite

[url]http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/PrimApp.shtml?demo3[/url]
[url]http://students.ceid.upatras.gr/~papagel/project/kruskal.htm[/url]

ovo ce pomoc
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



_________________
"I'm the operator with my pocket calculator"
[Vrh]
Korisnički profil Pošaljite privatnu poruku
Luuka
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 13. 02. 2007. (20:34:54)
Postovi: (925)16
Spol: muško
Sarma = la pohva - posuda
188 = 301 - 113
Lokacija: Hakuna Matata

PostPostano: 13:46 ned, 10. 2. 2008    Naslov: Citirajte i odgovorite

[quote="amorphis"]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)[/quote]

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



_________________
"Bolje bi prolazio na faxu da sam na drogama nego na netu" - by a friend of mine
"Poslije spavanja doma spavanje bilo di mi je najdraža stvar" - by the same guy Very Happy
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
desire
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 06. 09. 2007. (07:46:21)
Postovi: (133)16
Spol: žensko
Sarma = la pohva - posuda
31 = 34 - 3

PostPostano: 12:22 pon, 11. 2. 2008    Naslov: Citirajte i odgovorite

Da ne otvaram novu temu... Imam pitanje u vezi 2 zadatka sa vježbi.

1. Koliko ima svih mulitgrafova čiji je skup vrhova [latex]V=\{v_1, v_2,..., v_n\}[/latex], a svi imaju točno m bridova.

Rj: dvočlanih multiskupova skupa [latex]V=\{v_1, v_2,..., v_n\}[/latex] ima [latex] \left( \begin{array}{cc}n+1 \\ 2 \\ \end{array} \right)[/latex]
Svaki brid mozemo prodruziti multiskupu.
[latex]x_1+x_2+...+x_{\left( \begin{array}{cc}n+1 \\ 2 \\ \end{array} \right)}=m, x_i\geq0[/latex]
Dobivamo (n+1 povrh 2 + m -1) povrh m (ne ide mi bas latex danas pa pisem dalje ovak, sorry :))

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? :?


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 [latex]v_1, v_2,...,v_n[/latex] komponetne povezanosti
postoji [latex]v_i[/latex] t.d. je broj vrhova od [latex]v_i\leq \lfloor \frac{p}{2}\rfloor[/latex]
Uzmimo vrh x iz [latex]v_i[/latex], [latex]d(x)\geq\frac{1}{2}(p-1)[/latex]
Ukupno vrhova u [latex]v_i[/latex] ima [latex]\leq \lfloor \frac{p}{2}\rfloor[/latex]
[latex] \frac{1}{2}(p-1)\geq\lfloor \frac{p}{2}\rfloor-1\geq d(x)[/latex]
[latex]\frac{1}{2}p-\frac{1}{2}\geq\lfloor \frac{p}{2}\rfloor-1[/latex]

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

Tnx :)
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



_________________
Namigujem ti, a ti ne gledas...
[Vrh]
Korisnički profil Pošaljite privatnu poruku
amorphis
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 10. 02. 2007. (23:15:13)
Postovi: (101)16
Sarma = la pohva - posuda
= 19 - 11
Lokacija: zg

PostPostano: 14:52 pon, 11. 2. 2008    Naslov: Citirajte i odgovorite

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


[Vrh]
Korisnički profil Pošaljite privatnu poruku
amorphis
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 10. 02. 2007. (23:15:13)
Postovi: (101)16
Sarma = la pohva - posuda
= 19 - 11
Lokacija: zg

PostPostano: 15:27 pon, 11. 2. 2008    Naslov: Citirajte i odgovorite

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


[Vrh]
Korisnički profil Pošaljite privatnu poruku
sun
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 07. 04. 2006. (13:57:24)
Postovi: (A8)16
Spol: žensko
Sarma = la pohva - posuda
22 = 23 - 1

PostPostano: 19:47 pon, 11. 2. 2008    Naslov: Citirajte i odgovorite

[quote="Luuka"]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 :) ). Jesu li 2 grafa u 2.redu kao jednaka jer su izomorfni? Gore lijevo je cijeli graf.[/quote]

Luuka krivo si prepisao brid CD ti je tezine 3
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


[Vrh]
Korisnički profil Pošaljite privatnu poruku
Luuka
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 13. 02. 2007. (20:34:54)
Postovi: (925)16
Spol: muško
Sarma = la pohva - posuda
188 = 301 - 113
Lokacija: Hakuna Matata

PostPostano: 19:56 pon, 11. 2. 2008    Naslov: Citirajte i odgovorite

Onda ok. :lol: I mislio sam da je tak nešto posrijedi...

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

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

;)
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



_________________
"Bolje bi prolazio na faxu da sam na drogama nego na netu" - by a friend of mine
"Poslije spavanja doma spavanje bilo di mi je najdraža stvar" - by the same guy Very Happy


Zadnja promjena: Luuka; 21:26 pon, 11. 2. 2008; ukupno mijenjano 1 put.
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
desire
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 06. 09. 2007. (07:46:21)
Postovi: (133)16
Spol: žensko
Sarma = la pohva - posuda
31 = 34 - 3

PostPostano: 21:00 pon, 11. 2. 2008    Naslov: Citirajte i odgovorite

Hvala amorphis. Sarma ++. :)
Hvala amorphis. Sarma ++. Smile



_________________
Namigujem ti, a ti ne gledas...
[Vrh]
Korisnički profil Pošaljite privatnu poruku
buzov5
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 01. 12. 2006. (13:30:32)
Postovi: (4D)16
Sarma = la pohva - posuda
= 1 - 0
Lokacija: zg

PostPostano: 10:50 čet, 14. 2. 2008    Naslov: Citirajte i odgovorite

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



_________________
tko je ikada naučio od poraza?
[Vrh]
Korisnički profil Pošaljite privatnu poruku
Prethodni postovi:   
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji 2. godine -> Diskretna matematika Vremenska zona: GMT + 01:00.
Idite na 1, 2  Sljedeće
Stranica 1 / 2.

 
Forum(o)Bir:  
Ne možete otvarati nove teme.
Ne možete odgovarati na postove.
Ne možete uređivati Vaše postove.
Ne možete izbrisati Vaše postove.
Ne možete glasovati u anketama.
You can attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2002 phpBB Group
Theme created by Vjacheslav Trushkin
HR (Cro) by Ančica Sečan