Prethodna tema :: Sljedeća tema |
Autor/ica |
Poruka |
amorphis Forumaš(ica)
![Forumaš(ica) Forumaš(ica)](dyck.php?id=2017&c=257)
![](images/avatars/66467247347b0b86be3c6e.png)
Pridružen/a: 10. 02. 2007. (23:15:13) Postovi: (101)16
Lokacija: zg
|
|
[Vrh] |
|
Ančica Forumaš(ica)
![Forumaš(ica) Forumaš(ica)](dyck.php?id=1875&c=246)
![](images/avatars/62910995746e421e62080a.png)
Pridružen/a: 01. 12. 2006. (16:12:53) Postovi: (F6)16
Spol: ![žensko žensko](images/gender/female.gif)
|
|
[Vrh] |
|
ma Forumaš(ica)
![Forumaš(ica) Forumaš(ica)](dyck.php?id=1954&c=839)
![](images/avatars/19103417334afa9865396cc.jpg)
Pridružen/a: 27. 01. 2007. (12:06:50) Postovi: (347)16
Spol: ![muško muško](images/gender/male.gif)
|
|
[Vrh] |
|
Luuka Forumaš(ica)
![Forumaš(ica) Forumaš(ica)](dyck.php?id=2041&c=2341)
![](images/avatars/7081767854d2efa77dc28b.jpg)
Pridružen/a: 13. 02. 2007. (20:34:54) Postovi: (925)16
Spol: ![muško muško](images/gender/male.gif)
Lokacija: Hakuna Matata
|
Postano: 16:58 sub, 9. 2. 2008 Naslov: |
|
|
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 ). 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](images/smiles/icon_biggrin.gif)
Description: |
|
Filesize: |
22.74 KB |
Viewed: |
224 Time(s) |
![DSC00035.JPG](files/thumbs/t_dsc00035_772.jpg)
|
|
|
[Vrh] |
|
ma Forumaš(ica)
![Forumaš(ica) Forumaš(ica)](dyck.php?id=1954&c=839)
![](images/avatars/19103417334afa9865396cc.jpg)
Pridružen/a: 27. 01. 2007. (12:06:50) Postovi: (347)16
Spol: ![muško muško](images/gender/male.gif)
|
|
[Vrh] |
|
Luuka Forumaš(ica)
![Forumaš(ica) Forumaš(ica)](dyck.php?id=2041&c=2341)
![](images/avatars/7081767854d2efa77dc28b.jpg)
Pridružen/a: 13. 02. 2007. (20:34:54) Postovi: (925)16
Spol: ![muško muško](images/gender/male.gif)
Lokacija: Hakuna Matata
|
|
[Vrh] |
|
ma Forumaš(ica)
![Forumaš(ica) Forumaš(ica)](dyck.php?id=1954&c=839)
![](images/avatars/19103417334afa9865396cc.jpg)
Pridružen/a: 27. 01. 2007. (12:06:50) Postovi: (347)16
Spol: ![muško muško](images/gender/male.gif)
|
Postano: 17:52 sub, 9. 2. 2008 Naslov: |
|
|
[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](images/smiles/icon_confused.gif) |
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'..
_________________ ima let u finish
|
|
[Vrh] |
|
Luuka Forumaš(ica)
![Forumaš(ica) Forumaš(ica)](dyck.php?id=2041&c=2341)
![](images/avatars/7081767854d2efa77dc28b.jpg)
Pridružen/a: 13. 02. 2007. (20:34:54) Postovi: (925)16
Spol: ![muško muško](images/gender/male.gif)
Lokacija: Hakuna Matata
|
Postano: 18:03 sub, 9. 2. 2008 Naslov: |
|
|
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 ?
_________________ "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](images/smiles/icon_biggrin.gif)
|
|
[Vrh] |
|
ma Forumaš(ica)
![Forumaš(ica) Forumaš(ica)](dyck.php?id=1954&c=839)
![](images/avatars/19103417334afa9865396cc.jpg)
Pridružen/a: 27. 01. 2007. (12:06:50) Postovi: (347)16
Spol: ![muško muško](images/gender/male.gif)
|
Postano: 18:26 sub, 9. 2. 2008 Naslov: |
|
|
[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](images/smiles/icon_confused.gif) |
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.
_________________ ima let u finish
|
|
[Vrh] |
|
Luuka Forumaš(ica)
![Forumaš(ica) Forumaš(ica)](dyck.php?id=2041&c=2341)
![](images/avatars/7081767854d2efa77dc28b.jpg)
Pridružen/a: 13. 02. 2007. (20:34:54) Postovi: (925)16
Spol: ![muško muško](images/gender/male.gif)
Lokacija: Hakuna Matata
|
|
[Vrh] |
|
amorphis Forumaš(ica)
![Forumaš(ica) Forumaš(ica)](dyck.php?id=2017&c=257)
![](images/avatars/66467247347b0b86be3c6e.png)
Pridružen/a: 10. 02. 2007. (23:15:13) Postovi: (101)16
Lokacija: zg
|
|
[Vrh] |
|
napraviculom Forumaš(ica)
![Forumaš(ica) Forumaš(ica)](dyck.php?id=1973&c=113)
Pridružen/a: 01. 02. 2007. (16:40:37) Postovi: (71)16
Spol: ![muško muško](images/gender/male.gif)
Lokacija: Scranton
|
|
[Vrh] |
|
Luuka Forumaš(ica)
![Forumaš(ica) Forumaš(ica)](dyck.php?id=2041&c=2341)
![](images/avatars/7081767854d2efa77dc28b.jpg)
Pridružen/a: 13. 02. 2007. (20:34:54) Postovi: (925)16
Spol: ![muško muško](images/gender/male.gif)
Lokacija: Hakuna Matata
|
Postano: 13:46 ned, 10. 2. 2008 Naslov: |
|
|
[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](images/smiles/icon_biggrin.gif)
|
|
[Vrh] |
|
desire Forumaš(ica)
![Forumaš(ica) Forumaš(ica)](dyck.php?id=2377&c=307)
![](images/avatars/23206495846e7c607a28b4.jpg)
Pridružen/a: 06. 09. 2007. (07:46:21) Postovi: (133)16
Spol: ![žensko žensko](images/gender/female.gif)
|
Postano: 12:22 pon, 11. 2. 2008 Naslov: |
|
|
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 )
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 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
_________________ ![Namigujem ti, a ti ne gledas...](images/smiles/wink.gif)
|
|
[Vrh] |
|
amorphis Forumaš(ica)
![Forumaš(ica) Forumaš(ica)](dyck.php?id=2017&c=257)
![](images/avatars/66467247347b0b86be3c6e.png)
Pridružen/a: 10. 02. 2007. (23:15:13) Postovi: (101)16
Lokacija: zg
|
Postano: 14:52 pon, 11. 2. 2008 Naslov: |
|
|
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] |
|
amorphis Forumaš(ica)
![Forumaš(ica) Forumaš(ica)](dyck.php?id=2017&c=257)
![](images/avatars/66467247347b0b86be3c6e.png)
Pridružen/a: 10. 02. 2007. (23:15:13) Postovi: (101)16
Lokacija: zg
|
Postano: 15:27 pon, 11. 2. 2008 Naslov: |
|
|
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] |
|
sun Forumaš(ica)
![Forumaš(ica) Forumaš(ica)](dyck.php?id=1377&c=168)
Pridružen/a: 07. 04. 2006. (13:57:24) Postovi: (A8)16
Spol: ![žensko žensko](images/gender/female.gif)
|
|
[Vrh] |
|
Luuka Forumaš(ica)
![Forumaš(ica) Forumaš(ica)](dyck.php?id=2041&c=2341)
![](images/avatars/7081767854d2efa77dc28b.jpg)
Pridružen/a: 13. 02. 2007. (20:34:54) Postovi: (925)16
Spol: ![muško muško](images/gender/male.gif)
Lokacija: Hakuna Matata
|
|
[Vrh] |
|
desire Forumaš(ica)
![Forumaš(ica) Forumaš(ica)](dyck.php?id=2377&c=307)
![](images/avatars/23206495846e7c607a28b4.jpg)
Pridružen/a: 06. 09. 2007. (07:46:21) Postovi: (133)16
Spol: ![žensko žensko](images/gender/female.gif)
|
|
[Vrh] |
|
buzov5 Forumaš(ica)
![Forumaš(ica) Forumaš(ica)](dyck.php?id=1873&c=77)
![](images/avatars/100436306645c482c9c0cd9.jpg)
Pridružen/a: 01. 12. 2006. (13:30:32) Postovi: (4D)16
Lokacija: zg
|
|
[Vrh] |
|
|