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  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
angelika
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 08. 02. 2011. (17:26:51)
Postovi: (5F)16
Sarma = la pohva - posuda
= 3 - 1

PostPostano: 12:10 sub, 5. 1. 2013    Naslov: Citirajte i odgovorite

[quote="R2-D2"]Nema dalje, to je to :) . Ne traže te oblik iz kojeg možeš vidjeti opći član, nego samo zatvorenu formulu za funkciju, tj oblik u koji možeš uvrstiti x i izračunati f(x) tako da koristiš konačno mnogo operacija.[/quote]

da ziher pa je to sve...a ja se mučim to raspisivati #-o
hvala :D
R2-D2 (napisa):
Nema dalje, to je to Smile . Ne traže te oblik iz kojeg možeš vidjeti opći član, nego samo zatvorenu formulu za funkciju, tj oblik u koji možeš uvrstiti x i izračunati f(x) tako da koristiš konačno mnogo operacija.


da ziher pa je to sve...a ja se mučim to raspisivati d'oh!
hvala Very Happy


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


Pridružen/a: 25. 10. 2011. (20:04:19)
Postovi: (3D)16
Sarma = la pohva - posuda
= 1 - 0

PostPostano: 14:18 uto, 8. 1. 2013    Naslov: Citirajte i odgovorite

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

ako može netko 4.? hvala
http://web.math.pmf.unizg.hr/nastava/komb/kol/dm1112kol2.pdf

ako može netko 4.? hvala


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


Pridružen/a: 22. 01. 2007. (18:33:54)
Postovi: (138)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
53 = 55 - 2
Lokacija: Spljit

PostPostano: 15:59 uto, 8. 1. 2013    Naslov: Citirajte i odgovorite

Možda bi ovako išlo:
definirajmo
[dtex]A=\{a_1,\dots,a_m\} \ , \ B=\{b_1,\dots,b_n\} \;.[/dtex]

Desna strana je broj k-članih podskupova skupa A.
Lijeva strana je isto, ali preko FUI-a tako da tražimo
broj k-članih podskupova skupa [tex]A\cup B[/tex] koji ne sadrže
niti jedan element iz B.
Definirajmo
[dtex]S_i:=\{C\subseteq A\cup B \ | \ b_i\not\in C \} \;.[/dtex]

Nas zanima [tex]|S_1\cup\dots\cup S_n|[/tex]
Možda bi ovako išlo:
definirajmo
[dtex]A=\{a_1,\dots,a_m\} \ , \ B=\{b_1,\dots,b_n\} \;.[/dtex]

Desna strana je broj k-članih podskupova skupa A.
Lijeva strana je isto, ali preko FUI-a tako da tražimo
broj k-članih podskupova skupa [tex]A\cup B[/tex] koji ne sadrže
niti jedan element iz B.
Definirajmo
[dtex]S_i:=\{C\subseteq A\cup B \ | \ b_i\not\in C \} \;.[/dtex]

Nas zanima [tex]|S_1\cup\dots\cup S_n|[/tex]


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


Pridružen/a: 10. 09. 2011. (16:08:19)
Postovi: (F4)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
10 = 17 - 7

PostPostano: 19:30 uto, 8. 1. 2013    Naslov: Citirajte i odgovorite

[url=http://web.math.pmf.unizg.hr/nastava/komb/kol/dm0910kol2.pdf]Kolokvij 2009./10.[/url]
2.b) Kako da [latex]e(x) = (1+x+\frac {x^2}{2!} + ... + \frac {x^{10}} {10!})(1+x+\frac {x^2}{2!} + ... + \frac {x^{15}} {15!}) (1+x+\frac {x^2}{2!} + ... + \frac {x^{20}} {20!}) [/latex] razvijem u red?
5. Što je pjesnik htio reći, tj. nije mi nimalo jasan zadatak. :?
Kolokvij 2009./10.
2.b) Kako da razvijem u red?
5. Što je pjesnik htio reći, tj. nije mi nimalo jasan zadatak. Confused



_________________
With great power comes great electricity bill.
n!!!!
Theorem 2: Alexander the Great did not exist and he had an infinite number of limbs.
[Vrh]
Korisnički profil Pošaljite privatnu poruku
Loo
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 11. 06. 2012. (16:02:07)
Postovi: (D0)16
Spol: žensko
Sarma = la pohva - posuda
84 = 85 - 1

PostPostano: 19:39 uto, 8. 1. 2013    Naslov: Citirajte i odgovorite

5. broj surjekcija s n-članog u k-člani skup
prouči u kojem su odnosu djeca i sladoledi, pa će bit jasnije :wink:

2.b) i mene zanima :roll:
5. broj surjekcija s n-članog u k-člani skup
prouči u kojem su odnosu djeca i sladoledi, pa će bit jasnije Wink

2.b) i mene zanima Rolling Eyes


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


Pridružen/a: 10. 09. 2011. (16:08:19)
Postovi: (F4)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
10 = 17 - 7

PostPostano: 16:53 sri, 9. 1. 2013    Naslov: Citirajte i odgovorite

Hvala!
Zna li tko riješiti [url=http://web.math.pmf.unizg.hr/nastava/komb/pdf/2008-09/08kol2.pdf]1. i 2. u drugoj grupi[/url], te [url=http://web.math.pmf.unizg.hr/nastava/komb/pdf/2007-08/DM2007kol2.pdf]2.B[/url]?

Problemi su mi redom:
1) Bračne parove rješavam preko FUI, ali ne znam baš kako presjeke odrediti (ispadalo mi je nešto jako komplicirano već za presjek 2 skupa, da sam nastavila bi bio užas, pa nekako mislim da je krivo :) )
2) Je l ovo treba preko EFI? Ako da, radim li, i ako da, kako to prebaciti u red?
[latex]f(x) = (1+x+\frac {x^2}{2}+...+\frac {x^7}{7!})^4[/latex]?
3) Nemam blage kako uopće ovo prikazati preko FUI. :?
Hvala!
Zna li tko riješiti 1. i 2. u drugoj grupi, te 2.B?

Problemi su mi redom:
1) Bračne parove rješavam preko FUI, ali ne znam baš kako presjeke odrediti (ispadalo mi je nešto jako komplicirano već za presjek 2 skupa, da sam nastavila bi bio užas, pa nekako mislim da je krivo Smile )
2) Je l ovo treba preko EFI? Ako da, radim li, i ako da, kako to prebaciti u red?
?
3) Nemam blage kako uopće ovo prikazati preko FUI. Confused



_________________
With great power comes great electricity bill.
n!!!!
Theorem 2: Alexander the Great did not exist and he had an infinite number of limbs.
[Vrh]
Korisnički profil Pošaljite privatnu poruku
quark
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 22. 10. 2011. (16:47:39)
Postovi: (DA)16
Spol: muško
Sarma = la pohva - posuda
20 = 26 - 6

PostPostano: 19:01 sri, 9. 1. 2013    Naslov: Citirajte i odgovorite

[quote="PermutiranoPrase"]Hvala!
Zna li tko riješiti [url=http://web.math.pmf.unizg.hr/nastava/komb/pdf/2008-09/08kol2.pdf]1. i 2. u drugoj grupi[/url], te [url=http://web.math.pmf.unizg.hr/nastava/komb/pdf/2007-08/DM2007kol2.pdf]2.B[/url]?

Problemi su mi redom:
1) Bračne parove rješavam preko FUI, ali ne znam baš kako presjeke odrediti (ispadalo mi je nešto jako komplicirano već za presjek 2 skupa, da sam nastavila bi bio užas, pa nekako mislim da je krivo :) )
2) Je l ovo treba preko EFI? Ako da, radim li, i ako da, kako to prebaciti u red?
[latex]f(x) = (1+x+\frac {x^2}{2}+...+\frac {x^7}{7!})^4[/latex]?
3) Nemam blage kako uopće ovo prikazati preko FUI. :?[/quote]

1.) Hint: deranžmani

2.) Neka je [tex]|A_i|[/tex] broj odabira takav da [tex]x_i[/tex] zadovoljava traženo svojstvo; u zadatku se traži [tex]| \bigcap A_i|[/tex], a to izračunaš preko FUI.
Probaj s time, ali mislim da bi se moglo i preko EFI-ja :D

3.) Neka je [tex]|A_i|[/tex] broj brojeva koji dijeli [tex]i[/tex]-ti zadani broj; tebe zanima [tex]| \bigcup A_i |[/tex]
PermutiranoPrase (napisa):
Hvala!
Zna li tko riješiti 1. i 2. u drugoj grupi, te 2.B?

Problemi su mi redom:
1) Bračne parove rješavam preko FUI, ali ne znam baš kako presjeke odrediti (ispadalo mi je nešto jako komplicirano već za presjek 2 skupa, da sam nastavila bi bio užas, pa nekako mislim da je krivo Smile )
2) Je l ovo treba preko EFI? Ako da, radim li, i ako da, kako to prebaciti u red?
?
3) Nemam blage kako uopće ovo prikazati preko FUI. Confused


1.) Hint: deranžmani

2.) Neka je [tex]|A_i|[/tex] broj odabira takav da [tex]x_i[/tex] zadovoljava traženo svojstvo; u zadatku se traži [tex]| \bigcap A_i|[/tex], a to izračunaš preko FUI.
Probaj s time, ali mislim da bi se moglo i preko EFI-ja Very Happy

3.) Neka je [tex]|A_i|[/tex] broj brojeva koji dijeli [tex]i[/tex]-ti zadani broj; tebe zanima [tex]| \bigcup A_i |[/tex]


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


Pridružen/a: 10. 09. 2011. (16:08:19)
Postovi: (F4)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
10 = 17 - 7

PostPostano: 19:19 sri, 9. 1. 2013    Naslov: Citirajte i odgovorite

Hvala! :) I da, napisah krivo, 2.B znam, 2.A je problem. :D
Hvala! Smile I da, napisah krivo, 2.B znam, 2.A je problem. Very Happy



_________________
With great power comes great electricity bill.
n!!!!
Theorem 2: Alexander the Great did not exist and he had an infinite number of limbs.
[Vrh]
Korisnički profil Pošaljite privatnu poruku
quark
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 22. 10. 2011. (16:47:39)
Postovi: (DA)16
Spol: muško
Sarma = la pohva - posuda
20 = 26 - 6

PostPostano: 19:22 sri, 9. 1. 2013    Naslov: Citirajte i odgovorite

Taj me zadatak već dvoje ljudi danas upitalo :P

Mi tražimo [tex]A_i=[/tex]{broj rješenja t.d. [tex]x_i[/tex] iz traženog segmenta}

Nama treba presjek svih takvih rješenja:

[dtex]
|\bigcap_{i=1}^4A_i|=|\Omega|-|A_1^C|-\ldots+|\bigcap_{i=1}^4A_i^C|
[/dtex]

[tex]|\Omega|[/tex] je, naravno, broj svih rješenja (bez uvjeta na [tex]x_i[/tex])

Sada ti slijedi samo čisto tehničko računanje koristeći princip kuglica i štapića.

P.S. Primijeti da [tex]A_3^c[/tex] sadrži sve [tex]x_i \geq 51[/tex] pa takva rješenja nisu moguća, tj. ima ih [tex]0[/tex].
Taj me zadatak već dvoje ljudi danas upitalo Razz

Mi tražimo [tex]A_i=[/tex]{broj rješenja t.d. [tex]x_i[/tex] iz traženog segmenta}

Nama treba presjek svih takvih rješenja:

[dtex]
|\bigcap_{i=1}^4A_i|=|\Omega|-|A_1^C|-\ldots+|\bigcap_{i=1}^4A_i^C|
[/dtex]

[tex]|\Omega|[/tex] je, naravno, broj svih rješenja (bez uvjeta na [tex]x_i[/tex])

Sada ti slijedi samo čisto tehničko računanje koristeći princip kuglica i štapića.

P.S. Primijeti da [tex]A_3^c[/tex] sadrži sve [tex]x_i \geq 51[/tex] pa takva rješenja nisu moguća, tj. ima ih [tex]0[/tex].


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


Pridružen/a: 06. 10. 2010. (16:07:02)
Postovi: (17)16
Sarma = la pohva - posuda
= 3 - 3

PostPostano: 19:50 sri, 9. 1. 2013    Naslov: Citirajte i odgovorite

1. preko FUI
http://web.math.pmf.unizg.hr/nastava/komb/pdf/2008-09/08kol2.pdf

grupa A
Ai = { i-ti par sjedi jedan do drugog } i=1,...,10
preko FUI se traži k(presjek komplemenata skupova Ai)

k(Ai)= 2*(2n-2)! {od 2n ljudi promatramo 1 par kao blok i raspoređujemo 2n-1 ljudi za okrugli stol na (2n-2)! načina te permutiramo supružnike}

k(Ai & Aj) =2^2 *(2n-3)!

k( svi presjeci)=2^n *(n-1)! {raspored gdje svaki muž sjedi pored svoje žene }

k(univerzalan skup)=(2n-1)! {raspored svih 2n ljudi za okrugli stol}



grupa B
Ai={ i-ti muž pleše s i-tom ženom} i=1,...,10
preko FUI se (opet) traži k(presjek komplemenata skupova Ai)

k(Ai)=9! {i-ti pleše s i-tom ženom ostale raspoređujemo na 9! načina}
k(Ai & Aj)=8!
k (svi presjeci)=1

k(univerzalan skup)=10!

Na koji način se ovo mislilo rješiti preko deranžmana? :P

Može pomoć oko 3. (kako uopće modelirati problem?)
http://web.math.pmf.unizg.hr/nastava/komb/kol/dm1112kol2.pdf

i 1B
http://web.math.pmf.unizg.hr/nastava/komb/pdf/2007-08/DM2007kol2.pdf
1. preko FUI
http://web.math.pmf.unizg.hr/nastava/komb/pdf/2008-09/08kol2.pdf

grupa A
Ai = { i-ti par sjedi jedan do drugog } i=1,...,10
preko FUI se traži k(presjek komplemenata skupova Ai)

k(Ai)= 2*(2n-2)! {od 2n ljudi promatramo 1 par kao blok i raspoređujemo 2n-1 ljudi za okrugli stol na (2n-2)! načina te permutiramo supružnike}

k(Ai & Aj) =2^2 *(2n-3)!

k( svi presjeci)=2^n *(n-1)! {raspored gdje svaki muž sjedi pored svoje žene }

k(univerzalan skup)=(2n-1)! {raspored svih 2n ljudi za okrugli stol}



grupa B
Ai={ i-ti muž pleše s i-tom ženom} i=1,...,10
preko FUI se (opet) traži k(presjek komplemenata skupova Ai)

k(Ai)=9! {i-ti pleše s i-tom ženom ostale raspoređujemo na 9! načina}
k(Ai & Aj)=8!
k (svi presjeci)=1

k(univerzalan skup)=10!

Na koji način se ovo mislilo rješiti preko deranžmana? Razz

Može pomoć oko 3. (kako uopće modelirati problem?)
http://web.math.pmf.unizg.hr/nastava/komb/kol/dm1112kol2.pdf

i 1B
http://web.math.pmf.unizg.hr/nastava/komb/pdf/2007-08/DM2007kol2.pdf


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


Pridružen/a: 22. 10. 2011. (16:47:39)
Postovi: (DA)16
Spol: muško
Sarma = la pohva - posuda
20 = 26 - 6

PostPostano: 22:09 sri, 9. 1. 2013    Naslov: Citirajte i odgovorite

Stranica 3. skripte:

[quote]Primjer 0.1.1 (Deranžmani): Ukoliko imamo n pisama (muževa) i n adresiranih omotnica (žena), na koliko
načina možemo staviti pisma u omotnice (spariti muža i ženu), tako da ni jedno pismo ne dođe u odgovarajuću
omotnicu (nijedan muž ne pleše sa svojom ženom)?

Rješenje: Odgovor na gornje pitanje je najbliži cijeli broj broju n!/e.
[/quote]
Ako imam pogrešku u razmišljanju, slobodno ukažite :D
Stranica 3. skripte:

Citat:
Primjer 0.1.1 (Deranžmani): Ukoliko imamo n pisama (muževa) i n adresiranih omotnica (žena), na koliko
načina možemo staviti pisma u omotnice (spariti muža i ženu), tako da ni jedno pismo ne dođe u odgovarajuću
omotnicu (nijedan muž ne pleše sa svojom ženom)?

Rješenje: Odgovor na gornje pitanje je najbliži cijeli broj broju n!/e.

Ako imam pogrešku u razmišljanju, slobodno ukažite Very Happy


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


Pridružen/a: 31. 01. 2011. (18:42:32)
Postovi: (3A)16
Sarma = la pohva - posuda
= 6 - 5

PostPostano: 11:56 čet, 10. 1. 2013    Naslov: Citirajte i odgovorite

@27re možda može pomoći ...

http://fly.srk.fer.hr/~gizmo/Radovi/written/seminari%20i%20dokumentacije/TEORIJA%20GRAFOVA.pdf
@27re možda može pomoći ...

http://fly.srk.fer.hr/~gizmo/Radovi/written/seminari%20i%20dokumentacije/TEORIJA%20GRAFOVA.pdf


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


Pridružen/a: 13. 09. 2012. (20:48:55)
Postovi: (9)16
Sarma = la pohva - posuda
= 1 - 1

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

da li moze netko rijesiti 2.zadatak http://web.math.pmf.unizg.hr/nastava/komb/kol/dm1112kol2.pdf
da li moze netko rijesiti 2.zadatak http://web.math.pmf.unizg.hr/nastava/komb/kol/dm1112kol2.pdf


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


Pridružen/a: 31. 01. 2011. (18:42:32)
Postovi: (3A)16
Sarma = la pohva - posuda
= 6 - 5

PostPostano: 14:40 čet, 10. 1. 2013    Naslov: Citirajte i odgovorite

Broj područja označimo sa r pa je r=53 i broj vrhova sa p i broj bridova sa q. Svako područje je omeđeno sa [i]barem[/i] 5 bridova, to znači da je suma suma područja barem 5(stupanj područja-broj bridova koji omeđuju to područje). Suma stupnjeva područja je je jednaka 2-strukom broju bridova=> 2*q>=5*53 => q>=265/2, q>=133 i još Eulerov tm. po kojem vrijedi:
p-q+r=2 , p=2-r+q>=2-53+133=82
Broj područja označimo sa r pa je r=53 i broj vrhova sa p i broj bridova sa q. Svako područje je omeđeno sa barem 5 bridova, to znači da je suma suma područja barem 5(stupanj područja-broj bridova koji omeđuju to područje). Suma stupnjeva područja je je jednaka 2-strukom broju bridova⇒ 2*q>=5*53 ⇒ q>=265/2, q>=133 i još Eulerov tm. po kojem vrijedi:
p-q+r=2 , p=2-r+q>=2-53+133=82


[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: 15:07 čet, 10. 1. 2013    Naslov: Citirajte i odgovorite

Može li mi netko reći ideju... kako bih dokazao da ne postoji jednostavan bipartitan graf sa t.d. je svaki vrh stupnja većeg ili jednakog od 4 ??? Treba li nekako dokazat da ima cikluse neparne duljine ili sl.??? Unaprijed se zahvaljujem na bilo kakvoj ideji !!!

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

Ja se ispričavam jer nisam naveo da je graf [b]planaran[/b] !!!
Može li mi netko reći ideju... kako bih dokazao da ne postoji jednostavan bipartitan graf sa t.d. je svaki vrh stupnja većeg ili jednakog od 4 ??? Treba li nekako dokazat da ima cikluse neparne duljine ili sl.??? Unaprijed se zahvaljujem na bilo kakvoj ideji !!!

Added after 17 minutes:

Ja se ispričavam jer nisam naveo da je graf planaran !!!


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


Pridružen/a: 06. 07. 2011. (20:30:12)
Postovi: (2E)16
Sarma = la pohva - posuda
= 1 - 1

PostPostano: 15:26 čet, 10. 1. 2013    Naslov: Citirajte i odgovorite

[quote="Pavlek"]Može li mi netko reći ideju... kako bih dokazao da ne postoji jednostavan bipartitan graf sa t.d. je svaki vrh stupnja većeg ili jednakog od 4 ??? Treba li nekako dokazat da ima cikluse neparne duljine ili sl.??? Unaprijed se zahvaljujem na bilo kakvoj ideji !!!

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

Ja se ispričavam jer nisam naveo da je graf [b]planaran[/b] !!![/quote]

Pokažeš da svaki takav graf ima K3,3 za podgraf ili je njegova subdivizija - po tmu Kuratowskog on je neplanaran. Kontradikcija.
Pavlek (napisa):
Može li mi netko reći ideju... kako bih dokazao da ne postoji jednostavan bipartitan graf sa t.d. je svaki vrh stupnja većeg ili jednakog od 4 ??? Treba li nekako dokazat da ima cikluse neparne duljine ili sl.??? Unaprijed se zahvaljujem na bilo kakvoj ideji !!!

Added after 17 minutes:

Ja se ispričavam jer nisam naveo da je graf planaran !!!


Pokažeš da svaki takav graf ima K3,3 za podgraf ili je njegova subdivizija - po tmu Kuratowskog on je neplanaran. Kontradikcija.


[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: 15:37 čet, 10. 1. 2013    Naslov: Citirajte i odgovorite

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!
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!


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


Pridružen/a: 15. 05. 2010. (18:46:07)
Postovi: (164)16
Sarma: -

PostPostano: 15:52 čet, 10. 1. 2013    Naslov: Citirajte i odgovorite

@Pavlek: Pretpostavimo da tvrdnja zadatka vrijedi. Neka je [tex]n[/tex] broj vrhova u grafu, a [tex]q[/tex] broj bridova.
Pretpostavimo sada da je graf povezan. (*) Po zadatku [tex]9.16[/tex] s vježbi slijedi da je [tex]q \leq 2n-4[/tex].
Nadalje, u grafu vrijedi da je suma stupnjeva svih vrhova jednaka dvostrukom broju bridova (naime, svaki brid prebrojiš dvaput, za svaki od dva vrha koja povezuje). Zbog pretpostavke iz zadatka, slijedi [tex]2q \geq 4n[/tex], odnosno [tex]q \geq 2n[/tex].
Ukupno, dobili smo [tex]2n \leq q \leq 2n-4[/tex], što je kontradikcija.

Još bih trebao prokomentirati pretpostavku (*), odnosno reći što ako graf nije povezan. Tada graf promatramo kao kolekciju više grafova obzirom na komponente povezanosti (poslije zadatka [tex]3.3[/tex] s predavanja). Za svaki od tih grafova, označimo ih s [tex]G_1,G_2,...,G_k[/tex], pri čemu je [tex]k[/tex] broj "podgrafova", vrijede iste pretpostavke kao i u zadatku, uz dodatnu pretpostavku da je svaki od tih grafova povezan. Sada dalje dobivamo slično rješenje: [tex]2n_i \leq q_i \leq 2n_i-4[/tex], pri čemu su [tex]n_i, q_i[/tex], respektivno, broj vrhova i bridova u [tex]i[/tex]-tom podgrafu.
Zbrojimo li tih [tex]k[/tex] nejednakosti po [tex]i[/tex], dobivamo prijašnji, željeni rezultat: [tex]2n \leq q \leq 2n-4[/tex].
(Vjerojatno sam neprecizno i olako koristio neke pojmove, na čemu se ispričavam, ali ipak pišem ovo rješenje "na brzinu". :P)

Zapravo, na kraju drugog paragrafa nisam trebao ni sumirati po "podgrafovima" kada je kontradikcija dobivena već u jednom od njih, pa je i tu zadatak gotov. No, to sam raspisao jer mi se čini kao zgodna ideja za rješavanje nekih drugih zadataka koji su se znali pojavljivati za vježbu ili u kolokviju (najčešće, kada nemaš pretpostavku o povezanosti grafa, a trebaš je da bi iskoristio željene rezultate s predavanja ili vježbi).

Nadam se da nisam nešto pobrkao. :)
@Pavlek: Pretpostavimo da tvrdnja zadatka vrijedi. Neka je [tex]n[/tex] broj vrhova u grafu, a [tex]q[/tex] broj bridova.
Pretpostavimo sada da je graf povezan. (*) Po zadatku [tex]9.16[/tex] s vježbi slijedi da je [tex]q \leq 2n-4[/tex].
Nadalje, u grafu vrijedi da je suma stupnjeva svih vrhova jednaka dvostrukom broju bridova (naime, svaki brid prebrojiš dvaput, za svaki od dva vrha koja povezuje). Zbog pretpostavke iz zadatka, slijedi [tex]2q \geq 4n[/tex], odnosno [tex]q \geq 2n[/tex].
Ukupno, dobili smo [tex]2n \leq q \leq 2n-4[/tex], što je kontradikcija.

Još bih trebao prokomentirati pretpostavku (*), odnosno reći što ako graf nije povezan. Tada graf promatramo kao kolekciju više grafova obzirom na komponente povezanosti (poslije zadatka [tex]3.3[/tex] s predavanja). Za svaki od tih grafova, označimo ih s [tex]G_1,G_2,...,G_k[/tex], pri čemu je [tex]k[/tex] broj "podgrafova", vrijede iste pretpostavke kao i u zadatku, uz dodatnu pretpostavku da je svaki od tih grafova povezan. Sada dalje dobivamo slično rješenje: [tex]2n_i \leq q_i \leq 2n_i-4[/tex], pri čemu su [tex]n_i, q_i[/tex], respektivno, broj vrhova i bridova u [tex]i[/tex]-tom podgrafu.
Zbrojimo li tih [tex]k[/tex] nejednakosti po [tex]i[/tex], dobivamo prijašnji, željeni rezultat: [tex]2n \leq q \leq 2n-4[/tex].
(Vjerojatno sam neprecizno i olako koristio neke pojmove, na čemu se ispričavam, ali ipak pišem ovo rješenje "na brzinu". Razz)

Zapravo, na kraju drugog paragrafa nisam trebao ni sumirati po "podgrafovima" kada je kontradikcija dobivena već u jednom od njih, pa je i tu zadatak gotov. No, to sam raspisao jer mi se čini kao zgodna ideja za rješavanje nekih drugih zadataka koji su se znali pojavljivati za vježbu ili u kolokviju (najčešće, kada nemaš pretpostavku o povezanosti grafa, a trebaš je da bi iskoristio željene rezultate s predavanja ili vježbi).

Nadam se da nisam nešto pobrkao. Smile


[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:01 čet, 10. 1. 2013    Naslov: Citirajte i odgovorite

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.
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.


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


Pridružen/a: 06. 07. 2011. (20:30:12)
Postovi: (2E)16
Sarma = la pohva - posuda
= 1 - 1

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

[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:
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


[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  Sljedeće
Stranica 2 / 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