Prethodna tema :: Sljedeća tema |
Autor/ica |
Poruka |
Luuka Forumaš(ica)
Pridružen/a: 13. 02. 2007. (20:34:54) Postovi: (925)16
Spol:
Lokacija: Hakuna Matata
|
|
[Vrh] |
|
sun Forumaš(ica)
Pridružen/a: 07. 04. 2006. (13:57:24) Postovi: (A8)16
Spol:
|
|
[Vrh] |
|
desire Forumaš(ica)
Pridružen/a: 06. 09. 2007. (07:46:21) Postovi: (133)16
Spol:
|
Postano: 16:11 čet, 14. 2. 2008 Naslov: |
|
|
E kad smo vec kod toga, aj vi meni recite cemu ta 2 teorema sluze (Dirac i Ore). Jer gledajuci ove zadatke sa vjezbi, niti jedan od njih ne vrijedi, a graf ipak je Hamiltonov. A sta ce mi onda uopce ovi teoremi kad su skoro pa neprimjenjivi. :?
I jos nesto. Moze li mi netko napisati kako se dokazuje jedan teorem sa predavanja, ostavljeno nam je to za dz:
Graf je stablo ako i samo ako ne sadrzi cikluse, ali dodavanjem bilo kojeg novog brida dobivamo ciklus.
Hvala
E kad smo vec kod toga, aj vi meni recite cemu ta 2 teorema sluze (Dirac i Ore). Jer gledajuci ove zadatke sa vjezbi, niti jedan od njih ne vrijedi, a graf ipak je Hamiltonov. A sta ce mi onda uopce ovi teoremi kad su skoro pa neprimjenjivi.
I jos nesto. Moze li mi netko napisati kako se dokazuje jedan teorem sa predavanja, ostavljeno nam je to za dz:
Graf je stablo ako i samo ako ne sadrzi cikluse, ali dodavanjem bilo kojeg novog brida dobivamo ciklus.
Hvala
_________________
|
|
[Vrh] |
|
Luuka Forumaš(ica)
Pridružen/a: 13. 02. 2007. (20:34:54) Postovi: (925)16
Spol:
Lokacija: Hakuna Matata
|
Postano: 16:22 čet, 14. 2. 2008 Naslov: |
|
|
@sun Hvala! :karma:
[quote="desire"]Graf je stablo ako i samo ako ne sadrzi cikluse, ali dodavanjem bilo kojeg novog brida dobivamo ciklus.[/quote]
-> graf je stablo. Pošto je graf stablo, onda nema ciklusa i povezan je(iz definicije). Pošto je povezan ima samo 1 komponentu povezanosti, dakle postoji put između svaka 2 vrha. Uzmimo a,b nesusjedne vrhove. Ubacimo e=(a,b) u graf i dobivamo ciklus jer postoji put između a i b. (a,v1,v2,..,vn,b,a) pa graf više nije stablo.
<- ono drugo vrijedi. Želimo dokazati da je graf stablo. Po prep nema ciklusa, još treba dokazati da je povezan. Da bi bio povezan mora imati jednu komp povezanosti. P.S. da ima više komp povezanosti, A1 i A2 (može i više, pa one druge stavimo u uniju koju nazovemo A2). Uzmemo a iz A1 i b iz A2. Ne postoji put između njih (razl komp povezanosti). Dodamo brid (a,b). Nismo dobili ciklus što je u kontardikciji s pretpostavkom.
@sun Hvala!
desire (napisa): | Graf je stablo ako i samo ako ne sadrzi cikluse, ali dodavanjem bilo kojeg novog brida dobivamo ciklus. |
→ graf je stablo. Pošto je graf stablo, onda nema ciklusa i povezan je(iz definicije). Pošto je povezan ima samo 1 komponentu povezanosti, dakle postoji put između svaka 2 vrha. Uzmimo a,b nesusjedne vrhove. Ubacimo e=(a,b) u graf i dobivamo ciklus jer postoji put između a i b. (a,v1,v2,..,vn,b,a) pa graf više nije stablo.
← ono drugo vrijedi. Želimo dokazati da je graf stablo. Po prep nema ciklusa, još treba dokazati da je povezan. Da bi bio povezan mora imati jednu komp povezanosti. P.S. da ima više komp povezanosti, A1 i A2 (može i više, pa one druge stavimo u uniju koju nazovemo A2). Uzmemo a iz A1 i b iz A2. Ne postoji put između njih (razl komp povezanosti). Dodamo brid (a,b). Nismo dobili ciklus što je u kontardikciji s pretpostavkom.
_________________ "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
|
|
[Vrh] |
|
desire Forumaš(ica)
Pridružen/a: 06. 09. 2007. (07:46:21) Postovi: (133)16
Spol:
|
|
[Vrh] |
|
buzov5 Forumaš(ica)
Pridružen/a: 01. 12. 2006. (13:30:32) Postovi: (4D)16
Lokacija: zg
|
|
[Vrh] |
|
Luuka Forumaš(ica)
Pridružen/a: 13. 02. 2007. (20:34:54) Postovi: (925)16
Spol:
Lokacija: Hakuna Matata
|
Postano: 16:48 čet, 14. 2. 2008 Naslov: |
|
|
Nije kriza.Imam predavanja, samo mi te neke ograde fale, al sun ih je napisala...ak još koja fali, napiši tu. Tnx
Nije kriza.Imam predavanja, samo mi te neke ograde fale, al sun ih je napisala...ak još koja fali, napiši tu. Tnx
_________________ "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
|
|
[Vrh] |
|
betty Forumaš(ica)
Pridružen/a: 23. 02. 2006. (19:17:18) Postovi: (2D)16
|
|
[Vrh] |
|
Luuka Forumaš(ica)
Pridružen/a: 13. 02. 2007. (20:34:54) Postovi: (925)16
Spol:
Lokacija: Hakuna Matata
|
|
[Vrh] |
|
buzov5 Forumaš(ica)
Pridružen/a: 01. 12. 2006. (13:30:32) Postovi: (4D)16
Lokacija: zg
|
|
[Vrh] |
|
amorphis Forumaš(ica)
Pridružen/a: 10. 02. 2007. (23:15:13) Postovi: (101)16
Lokacija: zg
|
|
[Vrh] |
|
Luuka Forumaš(ica)
Pridružen/a: 13. 02. 2007. (20:34:54) Postovi: (925)16
Spol:
Lokacija: Hakuna Matata
|
|
[Vrh] |
|
betty Forumaš(ica)
Pridružen/a: 23. 02. 2006. (19:17:18) Postovi: (2D)16
|
|
[Vrh] |
|
ivanzub Forumaš(ica)
Pridružen/a: 08. 02. 2006. (11:16:46) Postovi: (CC)16
|
|
[Vrh] |
|
Luuka Forumaš(ica)
Pridružen/a: 13. 02. 2007. (20:34:54) Postovi: (925)16
Spol:
Lokacija: Hakuna Matata
|
Postano: 19:41 čet, 14. 2. 2008 Naslov: |
|
|
Stablo je bipartitan graf jer nema ciklusa. Zašto? Uzmimo jedan list stabla i označimo ga s A. Krećimo se po stablu i svaki idući vrh na kojeg naiđemo označimo naizmjenično s B i A. Pošto stablo nema ciklusa, neće se desit da postoji brid AA ili BB. Vjerojatno se to može i ljepše ispričat...
Recimo: Uzmimo vrh čiji je stupanj bar 2 i recimo nek je on korijen i označimo ga s A. Njegovu djecu označimo sa B. Djecu njegove djece ponovo s A itd. Dobili smo sve bridove AB (i BA) jer nema ciklusa.
Stablo je bipartitan graf jer nema ciklusa. Zašto? Uzmimo jedan list stabla i označimo ga s A. Krećimo se po stablu i svaki idući vrh na kojeg naiđemo označimo naizmjenično s B i A. Pošto stablo nema ciklusa, neće se desit da postoji brid AA ili BB. Vjerojatno se to može i ljepše ispričat...
Recimo: Uzmimo vrh čiji je stupanj bar 2 i recimo nek je on korijen i označimo ga s A. Njegovu djecu označimo sa B. Djecu njegove djece ponovo s A itd. Dobili smo sve bridove AB (i BA) jer nema ciklusa.
_________________ "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
|
|
[Vrh] |
|
ivanzub Forumaš(ica)
Pridružen/a: 08. 02. 2006. (11:16:46) Postovi: (CC)16
|
|
[Vrh] |
|
j.b.i.n.s.h. Forumaš(ica)
Pridružen/a: 24. 06. 2007. (10:28:11) Postovi: (1B)16
|
|
[Vrh] |
|
lyra Forumaš(ica)
Pridružen/a: 17. 07. 2006. (21:23:44) Postovi: (63)16
Spol:
|
|
[Vrh] |
|
j.b.i.n.s.h. Forumaš(ica)
Pridružen/a: 24. 06. 2007. (10:28:11) Postovi: (1B)16
|
|
[Vrh] |
|
lyra Forumaš(ica)
Pridružen/a: 17. 07. 2006. (21:23:44) Postovi: (63)16
Spol:
|
Postano: 20:23 čet, 14. 2. 2008 Naslov: |
|
|
e onda ovak..
"Uvjet povezanosti je očito nužan. Promatramo graf s Eulerovom turom. Krećući se stazom, svaki put kada dođemo do nekog vrha pomoću nekog brida, moramo ga napustiti drugim bridom, dakle iskoristit ćemo dva brida iz tog vrha. Budući da posjetimo svaki brid tog vrha, stupanj mora biti paran."
evo, sad sam se čak uspjela natjerat da ovo pročitam. jupii :D
e onda ovak..
"Uvjet povezanosti je očito nužan. Promatramo graf s Eulerovom turom. Krećući se stazom, svaki put kada dođemo do nekog vrha pomoću nekog brida, moramo ga napustiti drugim bridom, dakle iskoristit ćemo dva brida iz tog vrha. Budući da posjetimo svaki brid tog vrha, stupanj mora biti paran."
evo, sad sam se čak uspjela natjerat da ovo pročitam. jupii
_________________ - Hey, Rachel, how many hipsters does it take to screw in a lightbulb?
- Gee, Jess, how many?
- You don't KNOW?
|
|
[Vrh] |
|
|