Pitanja iz matematike PDF - Matematika

PITANJA U GRUPI A (i „neformalni“ odgovori) 1. Diricheltov prinicp – slaba forma. Dokažite. Ako n  1 predmet smještamo u n kutija, onda barem jedna kutija sadrži barem dva predmeta. Dokaz: Pretpostavimo protivno da je u svakoj kutiji najviše jedan predmet. Onda bi ukupno bilo najviše n predmeta, a...

PITANJA U GRUPI A (i „neformalni“ odgovori) 1. Diricheltov prinicp – slaba forma. Dokažite. Ako n  1 predmet smještamo u n kutija, onda barem jedna kutija sadrži barem dva predmeta. Dokaz: Pretpostavimo protivno da je u svakoj kutiji najviše jedan predmet. Onda bi ukupno bilo najviše n predmeta, a to je kontradikcija. 2. Dirichletov prinicip - jaka forma. Dokažite.  n  1 Ako m predmeta smještamo u n kutija, onda barem jedna kutija sadrži barem  1  m  predmet.  n  1 Dokaz: Pretpostavimo protivno da je u svakoj kutiji najviše  predmeta. Onda bi  m   n 1 n 1 ukupan broj predmeta bio: m     m  n  1 što je kontradikcija.  m  m 3. Koja su osnova pravila prebrojavanja? Pravilo sume, pravilo jednakosti i pravilo zbroja. 4. Pravilo jednakosti Dva (konačna) skupa imaju isti broj elemenata ako i samo ako postoji bijekcija među njima. 5. Pravilo zbroja Neka su S1 , S 2 ,..., S n konačni i u parovima disjunktni skupovi (tj. Si  S j   za svaki i, j  1,..., n , i  j ) onda je i njihova unija konačan skup i vrijedi: card  S1  S2 ...  S n   card  S1   card  S 2  ...  card  S n . 6. Pravilo produkta Neka su S1 , S 2 ,..., S n konačni skupovi, onda je i njihov kartezijev produkt konačan skup i vrijedi: card  S1  S 2 ...  S n   card  S1   card  S 2  ...  card  S n . 7. Što je r-kombinacija bez ponavljanja elemenata skupa S? To je svaki njegov r -člani podskup. 8. Koliko ima r-kombinacija n-članog skupa? n n! Ima ih   .  r  r !  n  r  ! 9. Što je r-kombinacija s ponavljanjem elemenata skupa S? To je r  člani multiskup čiji su elemeti iz S. 10. Koliko ima r-kombinacija s ponavljanjem n-članog skupa elemenata?   n    n  r  1 Ima ih       .  r   r  11. Što je to r-permutacija (varijacija) s ponavljanjem elemenata skupa S? To je uređena r -torka elemenata iz S pri čemu se elementi smiju ponavljati. 12. Koliko ima r-permutacija (varijacija) s ponavljanja n-članog skupa? Dokaz Ima ih n r. Ideja dokaza: Za prvi član r -torke imamo n izbora, za drugi člane r -torke imamo ponovo n izbora, isto i za treći i nadalje, pa po principu produkta je broj svih r -torki jednak n r. 13. Što je to r-permutacija (varijacija) bez ponavljanja elemenata skupa S? To je uređena r -torka elemenata is S pri čemu se elementi ne smiju ponvaljati. 14. Koliko ima r-permutacija (varijacija) bez ponavljanja n-članog skupa? Ima ih n r  n   n  1 ...   n   r  1 . Ideja dokaza: Za prvi član r -torke imamo n mogućnosti, za drugi člane r -torke imamo n  1 mogućnost, jer se prvi član ne smije ponoviti, za treći imamo n  2 mogućnosti i tako dalje, pa po principu produkta je broj svih r -torki jednak n r. 15. Pascalova formula i njen kombinatorni dokaz  n   n  1  n  1    .  r   r 1  r  n Dokaz: Od n jabuka možemo odabrati njih r na   načina. Zamislimo da je jedna r jabuka trula, pa se broj izbora particionira u dvije klase: 1) kada nismo izabrali trulu jabuku, već smo od preostalih n  1 jabuka izabrali njih r  n  1 (što možemo učiniti na   načina)  r  2) kada smo izabrali trulu jabuku i od preostalih n  1 jabuka izabrali još r  1 (što  n  1 možemo učiniti na   načina)  r  1  n   n  1  n  1 Po principu sume dobivamo:        r   r 1  r  16. Binomni teorem n n  x  y      x k y nk n k 0  k  17. Linearna homogena rekurzija s konstantim koeficijentima ima karakterističnu jednadžbu  x  2    x  4   0. Napišite opće rješenje: 2 3 an  1  2n   2  n  2n  1  4n   2  n  4 n   3  n 2  4n 18. Particija U parovima disjunktni skupovi S1 , S 2 ,..., S n (tj. Si  S j   za svaki i, j  1,..., n , i  j ) tvore particiju skupa S ako vrijedi S  S1  S2 ...  S n. 19. Indukcija. Neka je S   ako vrijedi: 1) 1  S (baza indukcije); 2) k  S  k  1  S za svaki k   (korak indukcije), onda je S  . 20. Formalna definicija algoritma Algoritam je uređena četvorka  Q, U , I , f  gdje je: 1) neprazan skup Q skup svih računalnskih stanja; 2) U  Q skup ulaza 3) I  Q skup izlaza  4) f : Q Q funkcija računanja za koju vrijedi: ¸ f  i   i za svaki i  I za svaki u  U postoji niz q0 , q1 , q2 ,..., qn takav da je q0  u , q1  f  q0  , q2  f  q1  ,…, qn  f  qn 1  i qn  I 21. Kardinalnost partitivnog skupa n-članog skupa. Dokaz Kardinalnost je: 2n. Ideja dokaza: Za svaki element postoje dvije mogućnosti, da jest ili nije u partitivnom skupu. Primjenom principa produkta dobivamo da je broj mogućnosti 2n. 22. Prebrojavanje funkcija. Dokaz Broj funkcija iz a -članog u b -člani skup je b a. Ideja dokaza: Označimo elemente domene s x1 , x2 ,..., xa. x1 se može preslikati u bilo koji od b elemenata kodomene, pa tu imamo b mogućnosti i x2 se može preslikati u bilo koji od b elemenata kodomene, pa tu imamo b mogućnosti. Analogno vrijedi i za x3 , x4 ,…, xa , pa je po principu produkta broj funkcija jednak b a. 23. Prebrojavanje injekcija Broj injekcija iz a -članog u b -člani skup je b a  b   b  1 ...  b   a  1 . Ideja dokaza: Označimo elemente domene s x1 , x2 ,..., xa. x1 se može preslikati u bilo koji od b elemenata kodomene, pa tu imamo b mogućnosti; x2 se može preslikati u bilo koji od preostalih b  1 elemenata kodomene (osim onog u kojeg se preslikao x1 ) , pa tu imamo b  1 mogućnosti; x2 se može preslikati u bilo koji od preostalih b  2 elemenata kodomene (osim onih u koje su se preslikali x1 i x2 ), pa tu imamo b  2 mogućnosti; Analogno vrijedi i za x3 , x4 ,…, xa , pa je po principu produkta broj funkcija jednak b a. 24. Što je slabi rastav prirodnog broja n u r dijelova. Koliko ih ima? To je uređena r  torka prirodnih brojeva  x1 , x2 ,..., xr  takvih da vrijedi  n  1 x1  x2 ...  xr  n. Njihov broj je:  .  r  1 25. Što je jaki rastav prirodnog broja n u r dijelova. Koliko ih ima? To je uređena r  torka ne-negativnih cijelih brojeva  x1 , x2 ,..., xr  takvih da vrijedi  n  r  1 x1  x2 ...  xr  n. Njihov broj je:  .  r 1  26. Multiskup Multiskup je uređeni par  S , m  gdje je S skup, a m : S  funkcija koja svakom elementu skupa S pridružuje njegovu kratnost (broj ponavljanja). 27. Podmultiskup Multiskup  S , m1  je podmultiskup multiskupa  S , m2  ako vrijedi m1  x   m2  x  za svaki x  S.  28. Koliko ima permutacija multiskupa x1n1 , x2 n2 ,..., xk nk ?   n1  n2 ...  nk   n1  n2 ...  nk  !    n1 , n2 ,..., nk  n1 ! n2 !...  nk ! 29. Multinomni teorem   n  n1 n2  x1 ...  xk   n    x1  x2 ...  xk nk n1 , n2 ,..., nk  0 n ,  1 2 n ,..., nk  n1  n2 ... nk  n 30. Graf, incidentan, susjedan Graf je uređeni par V , E  skupa vrhova V i skupa bridova E pri čemu svaki brid spaja dva ne nužno različita vrha. Ako brid e  E spaja vrhove v1 i v2 onda kažemo da je e incidentan s v1 i v2 , te da su mu v1 i v2 krajevi, a za vrhove v1 i v2 kažemo da su susjedni. 31. Red, veličina Red grafa v  G   card V  G   je broj njegovih vrhova, a veličina grafa e  G   card  E  G   je broj njegovih bridova. 32. Karika, petlja, višestruki brid Pravi brid ili karika je brid kojemu su krajevi različiti. Petlja je brid kojemu se krajevi podudaraju. Višestruki brid tvore dva ili više bridova koji imaju iste krajeve. 33. Jednostavan graf, potpun graf.. Jednostavan graf je graf bez višestrukih bridova i petlji. Potpun graf je jednostavan graf u kojem su svaka dva vrha susjedna. Potpun graf s n vrhova označavamo s K n. 34. Broj bridova potpunog grafa. Dokaz  v  Kn   e  Kn    .  2  Dokaz: Dovoljno je uočiti da je broj bridova jednak broju dvočlanih podskupova skupa vrhova. 35. Bipartitan graf, potpun bipartitan graf Bipartitan graf je graf čiji se vrhovi mogu podijeliti u dvije klase A i B tako da svaki brid ima jedan kraj u A , a drugi u B. Potpun bipartitan graf je jednostavan graf čiji se vrhovi mogu podijeliti u dvije klase A i B tako da svaki brid ima jedan kraj u A , a drugi u B , te je svaki vrh iz A susjedan svakom vrhu iz B. Potpun bipartitan graf koji u jednoj klasi ima m , a u drugoj n vrhova označavamo s K m,n. 36. Broj bridova potpunog bipartitnog grafa e  K m ,n   m  n. Ideja dokaza: Broj bridova potpunog bipartitnog grafa je jednak broju uređenih parova kojemu je prvi element iz jedne klase biparticije, a drugi iz druge klase biparticije. Po principu produkta broj takvih uređenih parova je m  n. 37. Matrica incidencije grafa To je pravokutna n  m matrica M   mij  gdje je mij broj koliko puta su vrh vi i brid e j incidentni. 38. Matrica susjedstva grafa To je kvadratna n  n matrica A   aij  gdje je aij broj bridova s krajevima vi i v j. 39. Podgraf, nadgraf, razapinjuči podgraf. Za graf G1  V1 , E1  kažemo da je podgraf grafa G2  V2 , E2  ako vrijedi V1  V2 i E1  E2 , te svaki brid iz E1 ima iste krajeve i u G1 i u G2. Pišemo G1  G2. Tada kažemo da je G2 nadgraf od G1 i pišemo G2  G1. Graf G1 je razapinjuči podgraf od G2 ako je G1  G2 i V  G1   V  G2 . 40. Uklanjanje brida Neka je G  V , E  graf i neka je e njegov brid. Tada je G \ e graf sa skupom vrhova V , a skupom bridova E \ e. 41. Uklanjanje vrha Neka je G  V , E  graf i neka je v njegov vrh. Tada je G \ v graf sa skupom vrhova V \ v , a skupom bridova E \ S gdje je S skup bridova incidentnih vrhu v. 42. Stupanj vrha To je broj bridova incidentnih tom vrhu pri čemu petlje brojimo dvaput. 43. Kontrakcija brida Brid kontrahiramo tako da ga uklonimo, a njegove krajeve identificiramo. 44. Minora grafa Minora grafa je graf dobiven operacijama uklanjanja vrhova, uklanjanja bridova i kontrahiranjem bridova. 45. Čemu je jednaka suma stupnjeva u grafu? Dvostrukom broju bridova. Dokaz: Dvaput ćemo zbrojiti sve elemente matrice incidencije i u oba slučaja moramo dobiti isti rezultat: 1) Prvo po retcima. Zbroj svakog retka je stupanj vrha, pa je zbroj svih elemenata matrice jednak zbroju stupnjeva u grafu 2) Sada po stupcima. Zbroj svakog stupca je 2, a broj stupaca je jednak broju bridova, pa je zbroj svih elemenata matrice jednak dvostrukom broju bridova. 46. Lema o rukovanju. Broj vrhova neparnog stupnja je paran broj. 47. Šetnja, staza, put. Šetnja je niz v0 e1v1e2 v2...ek vk vrhova v0 , v1 ,..., vk i bridova e1 ,..., ek pri čemu je brid ei incidentan s vrhovima vi 1 i vi. Staza je šetnja u kojoj se ne ponavljaju bridovi, a put je šetnja u kojoj se ne ponavljaju ni bridovi ni vrhovi. 48. Povezanost grafa i srodni pojmovi Dva vrha su povezana ako postoji put među njima. Graf je povezan ako su svaka dva vrha povezana. Komponenta povezanosti je maksimalni podgraf u kojem su svaka dva vrha povezana. Broj komponenti povezanosti grafa G označujemo s c  G . 49. Veza između broja bridova, vrhova i komponenti u šumi e G   v G   c G   0. 50. Veza između biparitinosti i ciklusa Graf je bipartitan ako i samo ako ne sadrži neparne cikluse. 51. Karakterizacija stabla Neka je G jednostavan graf. Tada su sljedeće tvrdnje ekvivalentne: 1) G je stablo; 2) Za svaka dva vrha u , v V  G  postoji jedinstveni  u , v  -put; 3) G je povezan, a uklanjanjem bilo kojeg brida postaje nepovezan;  V  4) G je acikličan, a dodavanjem bilo kojeg brida e    \ E  G  , graf G  e sadrži 2 ciklus; 5) G je povezan i vrijedi v  G   e  G   1 52. Rezni brid i njegova karakterizacija Rezni brid je brid čijim se uklanjanjem povećava broj komponenti grafa. Brid je rezni ako i samo ako nije sadržan u nijednom ciklusu 53. Neformalno objasnite pojam reznog vrha Rezni vrh je vrh čijim se uklanjanjem povećava broj komponenti grafa 54. Razapinjuće stablo Razapinjuće stablo grafa G je razapinjući podgraf od G koji je stablo. 55. Digraf Digraf G  V , A je uređeni par skupa vrhova V i skupa lukova A pri čemu svaki luk spaja početni i krajnji vrh. 56. Instupanj, outstupanj Instupanj vrha je broj lukova kojima je on krajnji vrh. Outstupanj vrha je broj lukova kojima je on početni vrh. 57. Lema o rukovanju za digrafove. Dokaz. Suma instupnjeva je jedanaka sumi outstupnjeva i one su jednake broju lukova. Ideja dokaza: Primijetimo da svaki luk doprinosi 1 i sumi instupnjeva i sumi outstupnjeva i broju lukova. 58. Korijensko stablo Usmjereno stablo koje ima jedan vrh (korijen) instupnja 0, a svi ostali vrhovi imaju instupanj 1. 59. Eulerov graf Graf je Eulerov ako dopušta Eulerovu turu. Eulerova tura je zatvorena staza koja sadrži svaki brid. 60. Karakterizacija Eulerovog grafa Graf je Eulerov ako i samo ako mu je svaki vrh parnog stupnja. 61. Hamiltonov put, Hamitonov ciklus, Hamiltonov graf Hamiltonov put je razapinjući put (put koji sadrži sve vrhove). Hamiltonov ciklus je razapinjuči ciklus (ciklus koji sadrži sve vrhove). Graf je Hamiltonov ako i samo ako sadrži Hamiltonov ciklus. 62. Bojenje vrhova. Kada je pravilno? Bojenje vrhova grafa G je funkcija f : V  G  C sa skupa vrhova grafa u skup boja C. Bojenje je pravilno ako susjedni vrhovi nisu obojeni istom bojom. 63. Bojenje bridova. Kada je pravilno? Bojenje bridova grafa G je funkcija f : E  G  C sa skupa bridova grafa u skup boja C. Bojenje je pravilno ako nikoja dva brida incidentan istom vrhu nisu obojeni istom bojom. 64. Planaran graf, ravninski graf Planaran graf je graf koji se može smjestiti u ravninu tako da se dva brida sijeku samo u vrhu koji je incidentan obojici. Graf koji je već tako smješten u ravninu se zove ravninski graf. 65. Eulerova formula   G   v  G   e  g   f  g   2 ,   G  je Eulerova karakteristika, a f  G  je broj strana grafa. PITANJA U GRUPI B 1. Koliko ima r -kombinacija bez ponavljanja n -članog skupa? Dokažite 2. Koliko ima r -kombinacija s ponavljanjem n -članog skupa? Dokažite 3. Algebarski dokaz Pascalove formule 4. Kombinatorni dokaz binomnog teorema 5. Oznake sume i produkta (induktivna definicija) 6. Fibonaccijevi brojevi 7. Izomorizam 8. Ciklus, put 9. Osnovni pojmovi o povezanosti grafova 10. Dokažite lemu o rukovanju 11. Iskažite i dokažite karakterizaciju reznih vrhova u stablima PITANJA U GRUPI C 1. Algebarski dokaz binomnog teorema 2. Algoritam (5 svojstava) 3. Koliko ima slabih rastava broja n u r dijelova? Dokažite! 4. Koliko ima jakih rastava broja n u r dijelova? Dokažite! 5. Koliko ima podmultiskupova danog skupa? Dokažite! 6. Koliko permutacija multiskupa s konačnim kratnostima? Dokažite! 7. Grafički niz, kada je niz grafički? (bez dokaza) 8. Iskažite i dokažite karakterizaciju stabla pomoću reznih bridova 9. Iskažite i dokažite vezu između broja bridova, vrhova i komponenti u šumi 10. Iskažite i dokažite odnos broja bridova i vrhova koji implicira postojanje ciklusa 11. Mengerov teorem (bez dokaza) 12. karakterizacija planarnih grafova (bez dokaza) PITANJA U GRUPI D 1. Leksikografski ispis permutacija (znati naći sljedeću) 2. Identiteti binomnih koeficijenata (Propozicija 8: a,b,c) 3. Rješavanje linearnih rekuzija (dvije propozicije) 4. Minimalni stupanj i duljina šetnje i ciklusa 5. Broj razapinjučih stabala 6. Whitneyev teorem 7. Posljedice Euleorve formule (3)