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

eulerov, Hamiltonov, planaran graf
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
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: 11:28 čet, 14. 2. 2008    Naslov: eulerov, Hamiltonov, planaran graf Citirajte i odgovorite
Imam jednu malu zamolbu...

izgleda da nisam bio na nekim vježbama (ili zakasnio) pa nemam sve u bilježnici... :oops:

jel bi mogli tu napisat glavne 'teoreme' što se tiču gore navedenih svojstava grafa? Neke ograde na broj bridova, stupanj vrhova, područja i sl...nešto poput [url=http://degiorgi.math.hr/forum/viewtopic.php?t=10652]ovog[/url] kaj je rafaelm napiso...

hvala... :)
Imam jednu malu zamolbu...

izgleda da nisam bio na nekim vježbama (ili zakasnio) pa nemam sve u bilježnici... Embarassed

jel bi mogli tu napisat glavne 'teoreme' što se tiču gore navedenih svojstava grafa? Neke ograde na broj bridova, stupanj vrhova, područja i sl...nešto poput ovog kaj je rafaelm napiso...

hvala... Smile



_________________
"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
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: 16:06 čet, 14. 2. 2008    Naslov: Citirajte i odgovorite
tm. p-q+r=2
tm. suma d(f)=2*E(G)

zad. jedn.povezan planaran graf s n vrhova ima najvise 3n-6 bridova
zad. ocjena za bipartitne q<=2n-4

Euler:

tm. ono sa a) i b) mulitgraf bez izoliranih je eul akko.. to imas u pred
tm(Ore)
korolar (Dirac)
zad. graf sa n vrhova i 2+1/2 * (n-2)(n-1) bridova je hamiltonov

mislim da je to to.... :)
tm. p-q+r=2
tm. suma d(f)=2*E(G)

zad. jedn.povezan planaran graf s n vrhova ima najvise 3n-6 bridova
zad. ocjena za bipartitne q<=2n-4

Euler:

tm. ono sa a) i b) mulitgraf bez izoliranih je eul akko.. to imas u pred
tm(Ore)
korolar (Dirac)
zad. graf sa n vrhova i 2+1/2 * (n-2)(n-1) bridova je hamiltonov

mislim da je to to.... Smile


[Vrh]
Korisnički profil Pošaljite privatnu poruku
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: 16:11 čet, 14. 2. 2008    Naslov: Citirajte i odgovorite
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. Confused

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



_________________
Namigujem ti, a ti ne gledas...
[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:22 čet, 14. 2. 2008    Naslov: Citirajte i odgovorite
@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! karma++

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 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: 16:26 čet, 14. 2. 2008    Naslov: Citirajte i odgovorite
Hvala. :karma:
Hvala. karma++



_________________
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 = 1 - 0
Lokacija: zg
PostPostano: 16:47 čet, 14. 2. 2008    Naslov: Citirajte i odgovorite
@ luuka: sve tm sa vjezbi imas na predavanjima, ona ograda je bila zadatak.
ak ti je kriza napisi izmedju kojih zadataka ti je rupa u biljeznici pa
ti skeniram
@ luuka: sve tm sa vjezbi imas na predavanjima, ona ograda je bila zadatak.
ak ti je kriza napisi izmedju kojih zadataka ti je rupa u biljeznici pa
ti skeniram



_________________
tko je ikada naučio od poraza?
[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:48 čet, 14. 2. 2008    Naslov: Citirajte i odgovorite
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 Very Happy
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
betty
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 02. 2006. (19:17:18)
Postovi: (2D)16
Sarma = la pohva - posuda
2 = 3 - 1
PostPostano: 17:13 čet, 14. 2. 2008    Naslov: Citirajte i odgovorite
jel mi može neko napisati samo prvu rečenicu iz dokaza prop.3.3.1. (planarnost), jer ja imam nešto nebulozno:?: :roll:
jel mi može neko napisati samo prvu rečenicu iz dokaza prop.3.3.1. (planarnost), jer ja imam nešto nebulozno:?: Rolling Eyes


[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:15 čet, 14. 2. 2008    Naslov: Citirajte i odgovorite
[quote="predavanja"]Odaberemo neki pravac p i označimo vrhove grafa točkama na pravcu p. ...[/quote]

Eto. ;)
predavanja (napisa):
Odaberemo neki pravac p i označimo vrhove grafa točkama na pravcu p. ...


Eto. 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
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
buzov5
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 01. 12. 2006. (13:30:32)
Postovi: (4D)16
Sarma = la pohva - posuda
1 = 1 - 0
Lokacija: zg
PostPostano: 17:20 čet, 14. 2. 2008    Naslov: Citirajte i odgovorite
ja ne pisem brojeve, al jedina prop. u dijelu o planarnosti
mi je da se svaki graf moze uloziti u R^3,
ak je to to dokaz kaze:
povucemo pravac u R^3, na pravcu oznacimo toliko
tocaka koliko graf ima vrhova. buduci da je pravac presjek
beskonacno mnogo ravnina za svaki brid odaberemo jednu od tih
ravnina i polukruznicom spojimo dvije tocke koje oznavaju vrhove
tog brida.

EDIT: preso me
ja ne pisem brojeve, al jedina prop. u dijelu o planarnosti
mi je da se svaki graf moze uloziti u R^3,
ak je to to dokaz kaze:
povucemo pravac u R^3, na pravcu oznacimo toliko
tocaka koliko graf ima vrhova. buduci da je pravac presjek
beskonacno mnogo ravnina za svaki brid odaberemo jednu od tih
ravnina i polukruznicom spojimo dvije tocke koje oznavaju vrhove
tog brida.

EDIT: preso me



_________________
tko je ikada naučio od poraza?
[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
8 = 19 - 11
Lokacija: zg
PostPostano: 17:21 čet, 14. 2. 2008    Naslov: Citirajte i odgovorite
koji je raspis izraza (-n povrh x)?

thnx
koji je raspis izraza (-n povrh x)?

thnx



_________________
We strongly recommend using Firefox to fully enjoy this site.
[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:25 čet, 14. 2. 2008    Naslov: Citirajte i odgovorite
[latex] { -k \choose n } = (-1)^n \cdot {n+k-1 \choose n} [/latex]

;)


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
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
betty
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 02. 2006. (19:17:18)
Postovi: (2D)16
Sarma = la pohva - posuda
2 = 3 - 1
PostPostano: 17:26 čet, 14. 2. 2008    Naslov: Citirajte i odgovorite
zahvaljujem.. :D
zahvaljujem.. Very Happy


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


Pridružen/a: 08. 02. 2006. (11:16:46)
Postovi: (CC)16
Sarma = la pohva - posuda
3 = 6 - 3
PostPostano: 19:36 čet, 14. 2. 2008    Naslov: Citirajte i odgovorite
da ne otvaram novu temu..

kako dokazat da Primov algoritam generira razapinjuce stablo minimalne tezine?

i kako dokazat da su stabla bipartitni grafovi?
da ne otvaram novu temu..

kako dokazat da Primov algoritam generira razapinjuce stablo minimalne tezine?

i kako dokazat da su stabla bipartitni grafovi?


[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:41 čet, 14. 2. 2008    Naslov: Citirajte i odgovorite
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 Very Happy
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
ivanzub
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 08. 02. 2006. (11:16:46)
Postovi: (CC)16
Sarma = la pohva - posuda
3 = 6 - 3
PostPostano: 19:47 čet, 14. 2. 2008    Naslov: Citirajte i odgovorite
hvala puno..

jel zna netko ovaj s primovim algoritmom?
hvala puno..

jel zna netko ovaj s primovim algoritmom?


[Vrh]
Korisnički profil Pošaljite privatnu poruku
j.b.i.n.s.h.
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 24. 06. 2007. (10:28:11)
Postovi: (1B)16
Sarma = la pohva - posuda
11 = 11 - 0
PostPostano: 20:13 čet, 14. 2. 2008    Naslov: Citirajte i odgovorite
evo velikog problema:

multigraf bez izoliranih vrhova je eulerov akko je povezan i svaki vrh je parnog stupnja.

i sad, meni je u našoj skriptarnici netko toliko lijepo kopirao da ne vidim pročitati prvu rečenicu dokaza. ima možda neka dobra duša da se sažali nad mojom sudbinom? :beg:
može čak i Luuka :D
evo velikog problema:

multigraf bez izoliranih vrhova je eulerov akko je povezan i svaki vrh je parnog stupnja.

i sad, meni je u našoj skriptarnici netko toliko lijepo kopirao da ne vidim pročitati prvu rečenicu dokaza. ima možda neka dobra duša da se sažali nad mojom sudbinom? Molim, kumim i preklinjem!
može čak i Luuka Very Happy



_________________
...joined because i needed some help...
[Vrh]
Korisnički profil Pošaljite privatnu poruku
lyra
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 17. 07. 2006. (21:23:44)
Postovi: (63)16
Spol: žensko
Sarma = la pohva - posuda
14 = 14 - 0
PostPostano: 20:15 čet, 14. 2. 2008    Naslov: Citirajte i odgovorite
u mojim kopijama piše "Uvjet povezanosti je očito nužan." :lol:
u mojim kopijama piše "Uvjet povezanosti je očito nužan." Laughing



_________________
- Hey, Rachel, how many hipsters does it take to screw in a lightbulb?
- Gee, Jess, how many?
- You don't KNOW?
[Vrh]
Korisnički profil Pošaljite privatnu poruku
j.b.i.n.s.h.
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 24. 06. 2007. (10:28:11)
Postovi: (1B)16
Sarma = la pohva - posuda
11 = 11 - 0
PostPostano: 20:19 čet, 14. 2. 2008    Naslov: Citirajte i odgovorite
onda mi još nešto nedostaje...
prvo što vidim je: ...stupanj mora biti paran. isto vrijedi i za početni vrh
onda mi još nešto nedostaje...
prvo što vidim je: ...stupanj mora biti paran. isto vrijedi i za početni vrh



_________________
...joined because i needed some help...
[Vrh]
Korisnički profil Pošaljite privatnu poruku
lyra
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 17. 07. 2006. (21:23:44)
Postovi: (63)16
Spol: žensko
Sarma = la pohva - posuda
14 = 14 - 0
PostPostano: 20:23 čet, 14. 2. 2008    Naslov: Citirajte i odgovorite
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 Very Happy



_________________
- Hey, Rachel, how many hipsters does it take to screw in a lightbulb?
- Gee, Jess, how many?
- You don't KNOW?
[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