2.kolokvij

[angelika]

[sasha.f]

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

ako može netko 4.? hvala

[shimija]

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]

[PermutiranoPrase]

Kolokvij 2009./10.
2.b) Kako da razvijem u red?
5. Što je pjesnik htio reći, tj. nije mi nimalo jasan zadatak.

_________________
With great power comes great electricity bill.
n!!!!
Theorem 2: Alexander the Great did not exist and he had an infinite number of limbs.

[Loo]

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

2.b) i mene zanima

[PermutiranoPrase]

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

_________________
With great power comes great electricity bill.
n!!!!
Theorem 2: Alexander the Great did not exist and he had an infinite number of limbs.

[quark]

[PermutiranoPrase]

Hvala! I da, napisah krivo, 2.B znam, 2.A je problem.

_________________
With great power comes great electricity bill.
n!!!!
Theorem 2: Alexander the Great did not exist and he had an infinite number of limbs.

[quark]

Taj me zadatak već dvoje ljudi danas upitalo

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

[27re]

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?

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

[quark]

Stranica 3. skripte:

[homoviator]

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

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

[an5]

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

[homoviator]

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

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

Added after 17 minutes:

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

[krki]

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

[Phoenix]

@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". )

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.

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

[krki]