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

2.kolokvij
WWW:
Idite na Prethodno  1, 2, 3
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
Pavlek
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 30. 11. 2011. (21:05:53)
Postovi: (E)16
Spol: muško
Sarma = la pohva - posuda
= 8 - 1

PostPostano: 16:41 čet, 10. 1. 2013    Naslov: Citirajte i odgovorite

[quote="krki"][quote="Pavlek"]Oprosti, ali zamolio bih, da ako nije problem, da malčice konkretnije objasniš kako dokazati da je K,3,3 podgraf od ovog grafa, jer u K3.3, ako imaš vremena! I hvala na ideji, razmislit ću![/quote]

EDIT: nije mi dobra ideja, našao sam si grešku :oops:[/quote]

Ma nema veze, Hvala ti što si odvojio malo vremena za moje pitanje. [i]Tko radio, taj i griješi[/i]! ;)

[size=9][color=#999999]Added after 16 minutes:[/color][/size]

[quote="student_92"]Može uputa? Valjda nije već netko pitao.
ZADATAK: Pokažite da u svakom jednostavnom planarnom grafu postoji vrh čiji stupanj je manji od 6.[/quote]

Pozdrav kolega. Ja sam to nešto radio i dobio sam sljedeći rezultat...
Graf prvo podjeliš na komponente povezanosti G1,G2 ... Gk, nek su ti pi vrhovi i qi bridovi na Gi
Znamo da je 2qi = suma stupnjeva vrhova na Gi>=6pi iz čega slijedi qi >=3pi
Znamo da je Gi povezan i planaran => (Zad 9.14) qi <=3pi-6 pa slijedi 3pi <=3pi - 6 =><=
krki (napisa):
Pavlek (napisa):
Oprosti, ali zamolio bih, da ako nije problem, da malčice konkretnije objasniš kako dokazati da je K,3,3 podgraf od ovog grafa, jer u K3.3, ako imaš vremena! I hvala na ideji, razmislit ću!


EDIT: nije mi dobra ideja, našao sam si grešku Embarassed


Ma nema veze, Hvala ti što si odvojio malo vremena za moje pitanje. Tko radio, taj i griješi! Wink

Added after 16 minutes:

student_92 (napisa):
Može uputa? Valjda nije već netko pitao.
ZADATAK: Pokažite da u svakom jednostavnom planarnom grafu postoji vrh čiji stupanj je manji od 6.


Pozdrav kolega. Ja sam to nešto radio i dobio sam sljedeći rezultat...
Graf prvo podjeliš na komponente povezanosti G1,G2 ... Gk, nek su ti pi vrhovi i qi bridovi na Gi
Znamo da je 2qi = suma stupnjeva vrhova na Gi>=6pi iz čega slijedi qi >=3pi
Znamo da je Gi povezan i planaran ⇒ (Zad 9.14) qi ⇐3pi-6 pa slijedi 3pi ⇐3pi - 6 ⇒⇐


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


Pridružen/a: 24. 09. 2011. (22:21:43)
Postovi: (76)16
Spol: muško
Sarma = la pohva - posuda
= 9 - 4

PostPostano: 16:45 čet, 10. 1. 2013    Naslov: Citirajte i odgovorite

pretpostavi suprotno, svaki vrh je stupnja barem 6.
2q= suma stupnjeva svih vrhova >= 6p tj q/3>=p
2q= suma stupnjeva svih podrucja >= 3r (jednostavan graf) tj 2q/3>=r

iz planarnosti slijedi p+r=2+q slijedi q/3+2q/3>=2+q slijedi 0>=2 sto je kontradikcija.

slicno se rijesi za za bipartitan graf, 2q>=4r jer nema neparnih cikulsa i jednostavan je graf, 2q>=4p slijedi da je 2q>=2(r+p) tj q>=r+p tj
p-q+r<=0 sto je kontradikcija s planarnoscu.

[size=9][color=#999999]Added after 1 minutes:[/color][/size]

uf sry ja sam za povezan graf...
pretpostavi suprotno, svaki vrh je stupnja barem 6.
2q= suma stupnjeva svih vrhova >= 6p tj q/3>=p
2q= suma stupnjeva svih podrucja >= 3r (jednostavan graf) tj 2q/3>=r

iz planarnosti slijedi p+r=2+q slijedi q/3+2q/3>=2+q slijedi 0>=2 sto je kontradikcija.

slicno se rijesi za za bipartitan graf, 2q>=4r jer nema neparnih cikulsa i jednostavan je graf, 2q>=4p slijedi da je 2q>=2(r+p) tj q>=r+p tj
p-q+r⇐0 sto je kontradikcija s planarnoscu.

Added after 1 minutes:

uf sry ja sam za povezan graf...



_________________
it was merely a setback
[Vrh]
Korisnički profil Pošaljite privatnu poruku
student_92
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 17. 09. 2011. (16:31:46)
Postovi: (B9)16
Sarma = la pohva - posuda
10 = 16 - 6

PostPostano: 16:57 čet, 10. 1. 2013    Naslov: Citirajte i odgovorite

@Pavlek, @Shaman
Hvala, razmislit ću. Ali ima tu jedna stvar koja mi onako, visi u zraku: smijemo li koristiti tvrdnje iz teorema [tex]8.29[/tex] i zadataka [tex]8.14[/tex] i [tex]8.16[/tex] s vježbi i u slučaju kada se ne radi o povezanom grafu? Još nisam našao kontraprimjer kada imam nepovezani graf (nije baš ni da sam se pravo pomučio da ih nađem) pa zato pitam. Jer, nekako me navodi da smijemo jer ako je dan nepovezan graf, onda [b]npr.[/b] sumu stupnjeva područja toga grafa mogu gledati kao suma stupnjeva područja njegovih kompomenti. Mislim, vjerojatno sam u krivu pa neka me netko pravovremeno ispravi da ne pišem sutra gluposti na kolokviju. :)
@Pavlek, @Shaman
Hvala, razmislit ću. Ali ima tu jedna stvar koja mi onako, visi u zraku: smijemo li koristiti tvrdnje iz teorema [tex]8.29[/tex] i zadataka [tex]8.14[/tex] i [tex]8.16[/tex] s vježbi i u slučaju kada se ne radi o povezanom grafu? Još nisam našao kontraprimjer kada imam nepovezani graf (nije baš ni da sam se pravo pomučio da ih nađem) pa zato pitam. Jer, nekako me navodi da smijemo jer ako je dan nepovezan graf, onda npr. sumu stupnjeva područja toga grafa mogu gledati kao suma stupnjeva područja njegovih kompomenti. Mislim, vjerojatno sam u krivu pa neka me netko pravovremeno ispravi da ne pišem sutra gluposti na kolokviju. Smile


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


Pridružen/a: 30. 11. 2011. (21:05:53)
Postovi: (E)16
Spol: muško
Sarma = la pohva - posuda
= 8 - 1

PostPostano: 17:35 čet, 10. 1. 2013    Naslov: Citirajte i odgovorite

A za to baš nisam siguran jer kako je stupanj područja definiran pomoću šetnje po bridovima oko tog područja ... A kod nepovezanih grafova, ne možemo napraviti šetnju po svim vrhovima oko tog područja... primjer zad. 9.4 vježbe, treća slika !!!
A za to baš nisam siguran jer kako je stupanj područja definiran pomoću šetnje po bridovima oko tog područja ... A kod nepovezanih grafova, ne možemo napraviti šetnju po svim vrhovima oko tog područja... primjer zad. 9.4 vježbe, treća slika !!!


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


Pridružen/a: 13. 11. 2011. (17:40:12)
Postovi: (74)16
Spol: žensko
Sarma = la pohva - posuda
10 = 20 - 10

PostPostano: 18:45 čet, 10. 1. 2013    Naslov: Citirajte i odgovorite

Žalosti me stanje studenata na drugoj godini inžinjerskog smjera. Skripte su pune grešaka (zbog kojih sam puno puta mislila da sam poludila kad piše jedno, primjer pokazuje drugo, teorem govori treće...), izvora iz kojih mogu provježbati svoje znanje je minimalno ili ih nema, gradivo je olako objašnjeno i treba mi triput više vremena da shvatim što je pjesnik htio reći jer je dosta toga izostavljeno iz dokaza jer je "očito" ili profesori/asistenti moraju proletjeti, doslovno (iz nekih kolegija nismo ni prošli određene naslove)... I onda se čude što toliko ljudi pada. Eto, samo to sam htjela spomenuti



dodatak: Da ne spominjem razliku u težini između zadataka s vježbi i zadataka na ispitu. Što se mene tiče, možemo komotno i ukinuti vježbe jer me nisu ništa pripremile za ispit, nimalo. Sve što sam naučila, naučila sam jer sam se namučila tražeći po internetu alternative.
Žalosti me stanje studenata na drugoj godini inžinjerskog smjera. Skripte su pune grešaka (zbog kojih sam puno puta mislila da sam poludila kad piše jedno, primjer pokazuje drugo, teorem govori treće...), izvora iz kojih mogu provježbati svoje znanje je minimalno ili ih nema, gradivo je olako objašnjeno i treba mi triput više vremena da shvatim što je pjesnik htio reći jer je dosta toga izostavljeno iz dokaza jer je "očito" ili profesori/asistenti moraju proletjeti, doslovno (iz nekih kolegija nismo ni prošli određene naslove)... I onda se čude što toliko ljudi pada. Eto, samo to sam htjela spomenuti



dodatak: Da ne spominjem razliku u težini između zadataka s vježbi i zadataka na ispitu. Što se mene tiče, možemo komotno i ukinuti vježbe jer me nisu ništa pripremile za ispit, nimalo. Sve što sam naučila, naučila sam jer sam se namučila tražeći po internetu alternative.




Zadnja promjena: nuclear; 21:52 čet, 10. 1. 2013; ukupno mijenjano 1 put.
[Vrh]
Korisnički profil Pošaljite privatnu poruku
student_92
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 17. 09. 2011. (16:31:46)
Postovi: (B9)16
Sarma = la pohva - posuda
10 = 16 - 6

PostPostano: 18:51 čet, 10. 1. 2013    Naslov: Citirajte i odgovorite

Evo ovako pa, ako se nekome da, neka prekontrolira ispravnost postupka:

[b]Zad.[/b] Pokažite da u svakom jednostavnom planarnom grafu postoji vrh čiji stupanj je manji od 6.

[b]Rj.[/b] Pretpostavimo suprotno, tj. da su svi vrhovi u grafu [tex]\mathcal{G}[/tex] stupnja [tex]\geq 6[/tex]. Neka su [tex]\mathcal{G_1, G_2, ..., G_m}[/tex] komponente povezanosti toga grafa. Pogledajmo jednu od njih, neka je to [tex]\mathcal{G_k}[/tex], za neki [tex]k \in \{1,2,...m\}[/tex]. To je jednostavan, povezan, planaran graf pa možemo primijeniti neke već poznate rezultate. Označimo s [tex]V_k[/tex] skup vrhova, [tex]E_k[/tex] skup bridova i [tex]F_k[/tex] skup područja grafa [tex]\mathcal{G_k}[/tex]. Budući da se radi o jednostavnom grafu, svako od njegovih područja ima barem stupanj [tex]3[/tex], a prema teoremu [tex]8.29[/tex] s vježbi slijedi [tex]2|E_k| = \displaystyle \sum_{f\in F_k} d(f) \geq 3|F_k|[/tex]. Nadalje, u povezanom grafu je suma stupnjeva vrhova jednaka dvostrukom broju bridova pa je po pretpostavci [tex]2|E_k| = \displaystyle \sum_{v\in V_k} d(v) \geq 6|V_k|[/tex]. I sada, graf [tex]\mathcal{G_k}[/tex] je planaran pa vrijedi Eulerova forumula, pa koristeći nju i prethodne dvije nejednakosti dobijemo [tex]2+|E_k| = |V_k|+|E_k| \leq \frac{1}{3} |E_k| + \frac{2}{3} |E_k| = |E_k|[/tex], a iz toga slijedi [tex]2 \leq 0[/tex], što je kontradikcija.
Dakle, vrijedi tvrdnja zadatka.
Evo ovako pa, ako se nekome da, neka prekontrolira ispravnost postupka:

Zad. Pokažite da u svakom jednostavnom planarnom grafu postoji vrh čiji stupanj je manji od 6.

Rj. Pretpostavimo suprotno, tj. da su svi vrhovi u grafu [tex]\mathcal{G}[/tex] stupnja [tex]\geq 6[/tex]. Neka su [tex]\mathcal{G_1, G_2, ..., G_m}[/tex] komponente povezanosti toga grafa. Pogledajmo jednu od njih, neka je to [tex]\mathcal{G_k}[/tex], za neki [tex]k \in \{1,2,...m\}[/tex]. To je jednostavan, povezan, planaran graf pa možemo primijeniti neke već poznate rezultate. Označimo s [tex]V_k[/tex] skup vrhova, [tex]E_k[/tex] skup bridova i [tex]F_k[/tex] skup područja grafa [tex]\mathcal{G_k}[/tex]. Budući da se radi o jednostavnom grafu, svako od njegovih područja ima barem stupanj [tex]3[/tex], a prema teoremu [tex]8.29[/tex] s vježbi slijedi [tex]2|E_k| = \displaystyle \sum_{f\in F_k} d(f) \geq 3|F_k|[/tex]. Nadalje, u povezanom grafu je suma stupnjeva vrhova jednaka dvostrukom broju bridova pa je po pretpostavci [tex]2|E_k| = \displaystyle \sum_{v\in V_k} d(v) \geq 6|V_k|[/tex]. I sada, graf [tex]\mathcal{G_k}[/tex] je planaran pa vrijedi Eulerova forumula, pa koristeći nju i prethodne dvije nejednakosti dobijemo [tex]2+|E_k| = |V_k|+|E_k| \leq \frac{1}{3} |E_k| + \frac{2}{3} |E_k| = |E_k|[/tex], a iz toga slijedi [tex]2 \leq 0[/tex], što je kontradikcija.
Dakle, vrijedi tvrdnja zadatka.


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


Pridružen/a: 30. 11. 2011. (21:05:53)
Postovi: (E)16
Spol: muško
Sarma = la pohva - posuda
= 8 - 1

PostPostano: 19:18 čet, 10. 1. 2013    Naslov: Citirajte i odgovorite

[quote="student_92"][tex]2+|E_k| = |V_k|+|E_k| \leq ...[/tex][/quote]
Sve je okay, samo ovdje [tex]2+|E_k|=|V_k|+|F_k|\leq ...[/tex] ... al to ti nije ništa opasno... ;)
student_92 (napisa):
[tex]2+|E_k| = |V_k|+|E_k| \leq ...[/tex]

Sve je okay, samo ovdje [tex]2+|E_k|=|V_k|+|F_k|\leq ...[/tex] ... al to ti nije ništa opasno... Wink


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


Pridružen/a: 22. 11. 2011. (20:18:49)
Postovi: (6F)16
Sarma = la pohva - posuda
20 = 22 - 2

PostPostano: 23:17 čet, 10. 1. 2013    Naslov: Citirajte i odgovorite

Pavlek ne pilaj

[size=9][color=#999999]Added after 20 seconds:[/color][/size]

:P
Pavlek ne pilaj

Added after 20 seconds:

Razz


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


Pridružen/a: 11. 01. 2013. (00:15:01)
Postovi: (15)16
Sarma = la pohva - posuda
= 0 - 0

PostPostano: 0:17 pet, 11. 1. 2013    Naslov: Citirajte i odgovorite

Kako doći do n-tog koeficijenta u ovakvom izrazu?
(razvoj u red mi se ne čini sasvim trivijalnim..)

(1+x^3 + x^6 +...)^3
Kako doći do n-tog koeficijenta u ovakvom izrazu?
(razvoj u red mi se ne čini sasvim trivijalnim..)

(1+x^3 + x^6 +...)^3


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


Pridružen/a: 17. 09. 2011. (16:31:46)
Postovi: (B9)16
Sarma = la pohva - posuda
10 = 16 - 6

PostPostano: 0:32 pet, 11. 1. 2013    Naslov: Citirajte i odgovorite

[quote="aptx"]Kako doći do n-tog koeficijenta u ovakvom izrazu?
(razvoj u red mi se ne čini sasvim trivijalnim..)

(1+x^3 + x^6 +...)^3[/quote]

Po meni, ovako: [tex](1+x^3+x^6+x^9+...)^3 = (1+(x^3)^1 + (x^3)^2+(x^3)^3+...)^3 = \displaystyle (\frac{1}{1-x^3})^3 = (1-x^3)^{-3} = \sum_{k=0}^\infty \binom {-3}{k} (-x^3)^k = \sum_{k=0}^\infty \binom {k+2}{k} x^{3k}[/tex].
aptx (napisa):
Kako doći do n-tog koeficijenta u ovakvom izrazu?
(razvoj u red mi se ne čini sasvim trivijalnim..)

(1+x^3 + x^6 +...)^3


Po meni, ovako: [tex](1+x^3+x^6+x^9+...)^3 = (1+(x^3)^1 + (x^3)^2+(x^3)^3+...)^3 = \displaystyle (\frac{1}{1-x^3})^3 = (1-x^3)^{-3} = \sum_{k=0}^\infty \binom {-3}{k} (-x^3)^k = \sum_{k=0}^\infty \binom {k+2}{k} x^{3k}[/tex].


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


Pridružen/a: 14. 09. 2011. (19:17:53)
Postovi: (6C)16
Sarma = la pohva - posuda
= 4 - 3

PostPostano: 3:37 pet, 11. 1. 2013    Naslov: Citirajte i odgovorite

http://web.math.pmf.unizg.hr/nastava/komb/kol/dm1112kol2.pdf

Mze netko 2., 3., i 8.? Molim vas
http://web.math.pmf.unizg.hr/nastava/komb/kol/dm1112kol2.pdf

Mze netko 2., 3., i 8.? Molim vas


[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 Prethodno  1, 2, 3
Stranica 3 / 3.

 
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