Prethodna tema :: Sljedeća tema |
Autor/ica |
Poruka |
Pavlek Forumaš(ica)
Pridružen/a: 30. 11. 2011. (21:05:53) Postovi: (E)16
Spol:
|
Postano: 16:41 čet, 10. 1. 2013 Naslov: |
|
|
[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 |
Ma nema veze, Hvala ti što si odvojio malo vremena za moje pitanje. Tko radio, taj i griješi!
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] |
|
Shaman Forumaš(ica)
Pridružen/a: 24. 09. 2011. (22:21:43) Postovi: (76)16
Spol:
|
|
[Vrh] |
|
student_92 Forumaš(ica)
Pridružen/a: 17. 09. 2011. (16:31:46) Postovi: (B9)16
|
Postano: 16:57 čet, 10. 1. 2013 Naslov: |
|
|
@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.
|
|
[Vrh] |
|
Pavlek Forumaš(ica)
Pridružen/a: 30. 11. 2011. (21:05:53) Postovi: (E)16
Spol:
|
|
[Vrh] |
|
nuclear Forumaš(ica)
Pridružen/a: 13. 11. 2011. (17:40:12) Postovi: (74)16
Spol:
|
Postano: 18:45 čet, 10. 1. 2013 Naslov: |
|
|
Ž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] |
|
student_92 Forumaš(ica)
Pridružen/a: 17. 09. 2011. (16:31:46) Postovi: (B9)16
|
Postano: 18:51 čet, 10. 1. 2013 Naslov: |
|
|
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] |
|
Pavlek Forumaš(ica)
Pridružen/a: 30. 11. 2011. (21:05:53) Postovi: (E)16
Spol:
|
|
[Vrh] |
|
aj_ca_volin_te Forumaš(ica)
Pridružen/a: 22. 11. 2011. (20:18:49) Postovi: (6F)16
|
|
[Vrh] |
|
aptx Forumaš(ica)
Pridružen/a: 11. 01. 2013. (00:15:01) Postovi: (15)16
|
|
[Vrh] |
|
student_92 Forumaš(ica)
Pridružen/a: 17. 09. 2011. (16:31:46) Postovi: (B9)16
|
|
[Vrh] |
|
BlameGame Forumaš(ica)
Pridružen/a: 14. 09. 2011. (19:17:53) Postovi: (6C)16
|
|
[Vrh] |
|
|