Untitled

Diricheltov princip - slaba forma

• Ako se smjesti n+1 predmet u n kutija, barem jedna kutija sadrži barem dva predmeta.
• Dokaz: Ako je u svakoj kutiji najviše jedan predmet, ukupno bi bilo najviše n predmeta, što je kontradikcija.

Dirichletov princip - jaka forma

• Ako se smjesti m predmeta u n kutija, onda barem jedna kutija sadrži barem ⌈m/n⌉ predmeta.
• Dokaz: Ako je u svakoj kutiji najviše ⌊(n-1)/m⌋ predmeta, ukupan broj predmeta bi bio manji ili jednak m * ⌊(n-1)/m⌋ ≤ n-1, što je kontradikcija.

Osnovna pravila prebrojavanja

• Pravilo sume
• Pravilo jednakosti
• Pravilo zbroja

Pravilo jednakosti

• Dva konačna skupa imaju isti broj elemenata ako i samo ako postoji bijekcija (jedan-na-jedan i "na") preslikavanje među njima.

Pravilo zbroja

• Ako su S₁, S₂,..., Sₙ konačni i disjunktni skupovi (tj. Sᵢ ∩ Sⱼ = ∅ za svaki i ≠ j), onda je i njihova unija konačan skup i vrijedi: card(S₁ ∪ S₂ ∪ ... ∪ Sₙ) = card(S₁) + card(S₂) + ... + card(Sₙ).

Pravilo produkta

• Ako su S₁, S₂,..., Sₙ konačni skupovi, onda je i njihov Kartezijev produkt konačan skup i vrijedi: card(S₁ × S₂ × ... × Sₙ) = card(S₁) * card(S₂) * ... * card(Sₙ).

r-kombinacija bez ponavljanja

• r-kombinacija bez ponavljanja elemenata skupa S je svaki njegov r-člani podskup.

Broj r-kombinacija n-članog skupa

• Broj r-kombinacija n-članog skupa je (n r) = n!/[r!(n-r)!].

r-kombinacija s ponavljanjem

• r-kombinacija s ponavljanjem elemenata skupa S je r-člani multiskup čiji su elementi iz S.

Broj r-kombinacija s ponavljanjem n-članog skupa

• Broj r-kombinacija s ponavljanjem n-članog skupa je ((n r)) = (n+r-1 r).

r-permutacija (varijacija) s ponavljanjem

• r-permutacija (varijacija) s ponavljanjem elemenata skupa S je uređena r-torka elemenata iz S pri čemu se elementi smiju ponavljati.

Broj r-permutacija (varijacija) s ponavljanjem n-članog skupa

• Broj r-permutacija (varijacija) s ponavljanjem n-članoga skupa je nʳ.
• Objašnjenje: Za svaki od r mjesta u torki imamo n izbora, pa je ukupan broj mogućnosti nn...*n (r puta) = nʳ.

r-permutacija (varijacija) bez ponavljanja

• r-permutacija (varijacija) bez ponavljanja elemenata skupa S je uređena r-torka elemenata iz S pri čemu se elementi ne smiju ponavljati.

Broj r-permutacija (varijacija) bez ponavljanja

• Broj r-permutacija (varijacija) bez ponavljanja n-članog skupa je n(r) = n * (n-1) * ... * (n-(r-1)).
• Objašnjenje: Za prvi element imamo n mogućnosti, za drugi n-1 mogućnosti, za treći n-2 i tako dalje.

Pascalova formula

• Pascalova formula: (n r) = (n-1 r-1) + (n-1 r)
• Broj načina da se odabere r jabuka od n jabuka (gdje je jedna trula) može se podijeliti u dva slučaja:
  • Ne izaberemo trulu jabuku: tada od n-1 jabuka biramo r jabuka, što možemo učiniti na (n-1 r) načina
  • Izaberemo trulu jabuku: tada od n-1 jabuka moram izabrati još r-1 jabuka, što možemo učiniti na (n-1 r-1) načina

Binomni teorem

• Binomni teorem: (x + y)ⁿ = Σ (n k) xᵏ yⁿ⁻ᵏ (sumiranje po k od 0 do n).

Linearna homogena rekurzija s konstantnim koeficijentima

• Ako je karakteristična jednadžba (x-2)²(x-4)³ = 0, opće rješenje je: aₙ = α₁ * 2ⁿ + α₂ * n * 2ⁿ + β₁ * 4ⁿ + β₂ * n * 4ⁿ + β₃ * n² * 4ⁿ.

Particija

• Particija skupa S je skup disjunktnih skupova S₁, S₂,..., Sₙ takvi da je S = S₁ ∪ S₂ ∪ ... ∪ Sₙ.

Indukcija

• Neka je S ⊆ N. Ako vrijedi:
  • 1 ∈ S (baza indukcije)
  • k ∈ S ⇒ k+1 ∈ S za svaki k ∈ N (korak indukcije)
• Onda je S = N (cijeli skup prirodnih brojeva).

Formalna definicija algoritma

• Algoritam je uređena četvorka (Q, U, I, f) gdje je:
  • Q - neprazan skup svih računalnih stanja
  • U ⊆ Q - skup ulaza
  • I ⊆ Q - skup izlaza
  • f: Q → Q - funkcija računanja takva da:
  • f(i) = i za svaki i ∈ I
  • za svaki u ∈ U postoji niz q₀, q₁, q₂,..., qₙ takav da je q₀ = u, qᵢ₊₁=f(qᵢ),..., qₙ = f(qₙ₋₁) i qₙ ∈ I

Kardinalnost partitivnog skupa

• Kardinalnost partitivnog skupa n-članog skupa je 2ⁿ.
• Objašnjenje: Za svaki element postoji dvije opcije: ili je u podskupu ili nije (dva izbora za svaki od n elemenata). Dakle: 22...*2 (n puta)= 2ⁿ

Prebrojavanje funkcija

• Broj funkcija iz a-članog u b-člani skup je bª.
• Objašnjenje: Svaki od a elemenata domene može se preslikati u bilo koji od b elemenata kodomene. Dakle: bb...*b (a puta) = bª

Prebrojavanje injekcija

• Broj injekcija iz a-članog u b-člani skup je bª = b * (b-1) * ... * (b-(a-1)).
• Objašnjenje: Prvi element preslikavamo u bilo koji od b drugih, drugi element preslikavamo u bilo koji od b-1 elemenata (jer ne smije biti isti kao prvi), itd.

Slabi rastav prirodnog broja n u r dijelova

• Slabi rastav prirodnog broja n u r dijelova je uređena r-torka prirodnih brojeva (x₁, x₂,..., xᵣ) takvih da vrijedi x₁ + x₂ + ... + xᵣ = n.
• Njihov broj je (n+r-1 r-1).

Jaki rastav prirodnog broja n u r dijelova

• Jaki rastav prirodnog broja n u r dijelova je uređena r-torka pozitivnih cijelih brojeva (x₁, x₂,..., xᵣ) takvih da vrijedi x₁ + x₂ + ... + xᵣ = n.
• Njihov broj je (n-1 r-1).

Multiskup

• Multiskup je uređeni par (S, m) gdje je S skup, a m: S → N funkcija koja svakom elementu skupa S pridružuje njegovu kratnost (broj ponavljanja). Primer: S = {a,b}, m(a)=2, m(b) = 3, sto znaci da imamo multiskup koji sadrzi dva "a" i tri "b".

Podmultiskup

• Multiskup (S, m₁) je podmultiskup multiskupa (S, m₂) ako vrijedi m₁(x) ≤ m₂(x) za svaki x ∈ S.

Broj permutacija multiskupa

• Broj permutacija multiskupa (x₁ⁿ¹, x₂ⁿ² ,..., xₖⁿᵏ ) je (n₁ + n₂ + ... + nₖ)! / (n₁! * n₂! * ... * nₖ!).

Multinomni teorem

• Multinomni teorem: (x₁ + x₂ + ... + xₖ)ⁿ = Σ (n!/(n₁!n₂!...nₖ!))* x₁ⁿ¹x₂ⁿ²...xₖⁿᵏ zbroj se odnosi na sve moguće kombinacije n₁, n₂,..., nₖ takve da je zbroj tih članova jednak n..

Graf, incidentan, susjedan

• Graf je uređeni par (V, E):
  • V je skup vrhova
  • E je skup bridova
• Svaki brid spaja dva vrha (ne nužno različita).
• Ako brid e ∈ E spaja vrhove v₁ i v₂, onda je e incidentan s v₁ i v₂ i v₁ i v₂ su krajevi brida e. Vrhovi v₁ i v₂ su onda susjedni.

Red i veličina grafa

• Red grafa v(G) = card(V(G)) je broj vrhova.
• Veličina grafa e(G) = card(E(G)) je broj bridova.

Karika, petlja, višestruki brid

• Karika (pravi brid) -brid kojemu su krajevi različiti (ne spaja vrh sa samim sobom).
• Petlja - brid kojemu se krajevi podudaraju (spaja vrh sa samim sobom).
• Višestruki brid - dva ili više bridova koji imaju iste krajeve.

Jednostavan graf, potpun graf

• Jednostavan graf - graf bez višestrukih bridova i petlji.
• Potpun graf - jednostavan graf u kojem su svaka dva vrha susjedna. Potpun graf s n vrhova označavamo s Kₙ.

Broj bridova potpunog grafa

• Broj bridova potpunog grafa Kₙ: e(Kₙ) = (n 2) = n(n-1)/2. (jer imamo n vrhova i zanima nas dvoclani podskup tih vrhova).

Bipartitan graf

• Bipartitan graf - vrhovi se mogu podijeliti u dvije klase A i B tako da svaki brid ima jedan kraj u A, a drugi u B.
• Potpun bipartitan graf - jednostavan graf koji zadovoljava gornji uvjet i svaki vrh iz A je susjedan svakom vrhu iz B (označavamo s Kₘ,ₙ gdje je klasa A velicine m, klasa B velicine n).

Broj bridova potpunog bipartitnog grafa

• e(Kₘ,ₙ) = m * n (svaki element iz m se mora spojiti sa svakim elementom iz n).

Matrica incidencije grafa

• Pravokutna matrica n×m Matrica M = [mᵢⱼ] gdje je mᵢⱼ broj koliko puta su vrh vᵢ i brid eⱼ incidentni.

Matrica susjedstva grafa

• Kvadratna matrica n×n A = [aᵢⱼ] gdje je aᵢⱼ broj bridova s krajevima vᵢ i vⱼ.

Podgraf, nadgraf, razapinjući podgraf

• Za graf G₁ = (V₁, E₁) kažemo da je podgraf grafa G₂ = (V₂, E₂) ako vrijedi V₁ ⊆ V₂ i E₁ ⊆ E₂, te svaki brid iz E₁ ima iste krajeve i u G₁ iu G₂. Pišemo G₁ ⊆ G₂. U tom slucaju G₂ je nadgraf od G₁. Graf G₁ je razapinjuči podgraf od G₂ ako je G₁ podgraf od G₂ i V(G₁) = V(G₂).

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

Uklanjanje vrha

• Neka je G = (V, E) graf i neka je vrh 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.

Stupanj vrha

• Broj bridova incidentnih tom vrhu pri čemu petlje brojimo dvaput

Kontrakcija brida

• Brid kontrahiramo tako da ga uklonimo, a njegove krajeve identificiramo (spojimo vrhove koje spaja u jedan vrh).

Minora grafa

• Minora grafa je graf dobiven operacijama uklanjanja vrhova, uklanjanja bridova i kontrahiranjem bridova.

Suma stupnjeva u grafu

• Suma stupnjeva svih vrhova u grafu jednaka je dvostrukom broju bridova.
• Objašnjenje: Svaki brid doprinosi stupnju dva vrha (dva kraja ima).

Lema o rukovanju

• Broj vrhova neparnog stupnja je paran broj.

Setnja, staza, put: terminologija

• Setnja: niz vrhova i bridova koji se izmjenjuju (v₀, e₁, v₁, e₂, v₂,...). Brid eᵢ je incidentan s vrhovima vᵢ₋₁ i vᵢ
• Staza: šetnja u kojoj se ne ponavljaju bridovi.
• Put: šetnja u kojoj se ne ponavljaju ni bridovi, ni vrhovi.

Povezanost grafa

• Dva vrha povezana ako postoji put između njih.
• Graf povezan ako su svaka dva vrha povezana. Komponenta povezanosti je maksimalni povezani podgraf (ne moze se dodati niti jedan vrh tako da i dalje bude povezan podgraf).
• Broj komponenti povezanosti grafa G označujemo sa c(G).

Veza između broja bridova, vrhova i komponenti u šumi

• Za šumu vrijedi: e(G) - v(G) + c(G) = 0

Veza između bipartitnosti i ciklusa

• Graf je bipartitan ako i samo ako ne sadrži neparne cikluse (niti jedan ciklus u grafu ne smije biti duljine neparnog broja vrhova odnosno bridova).

Karakterizacija stabla

• Za jednostavni graf G, sljedeće tvrdnje su ekvivalentne:
  • G je stablo.
  • Za svaka dva vrha u, v ∈ V(G) postoji jedinstveni (u,v)-put.
  • G je povezan, a uklanjanjem bilo kojeg brida postaje nepovezan.
  • G je acikličan, a dodavanjem bilo kojeg brida ee (V(2(G)) \ E(G), graf G+e sadrži ciklus.
  • G je povezan i vrijedi v(G) = e(G) + 1

Rezni brid

• Rezni brid je brid čijim se uklanjanjem povecava broj komponenti grafa. Brid je rezni ako i samo ako nije sadržan ni u jednom ciklusu.

Rezni vrh

• Rezni vrh je vrh čijim se uklanjanjem povecava broj komponenti grafa.

Razapinjajuće stablo

• Razapinjajuće stablo grafa G je razapinjajući podgraf od G koji je stablo

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.

Instupanj, Outstupanj

• Instupanj vrha je broj lukova kojima je on krajnji vrh.
• Outstupanj vrha je broj lukova kojima je on početni vrh.

Lema o rukovanju za digrafove

• Suma instupnjeva je jednaka sumi outstupnjeva i one su jednake broju lukova.
• Primijetimo da svaki luk doprinosi 1 i sumi instupnjeva i sumi outstupnjeva i broju lukova.

Korijensko stablo

• Usmjereno stablo koje ima jedan vrh (korijen) instupnja 0, a svi ostali vrhovi imaju instupanj 1.

Eulerov graf

• Graf je Eulerov ako dopušta Eulerovu turu. Eulerova tura je zatvorena staza koja sadrži svaki brid.

Karakterizacija Eulerovog grafa

• Graf je Eulerov ako i samo ako mu je svaki vrh parnog stupnja.

Hamiltonov put, Hamiltonov ciklus, Hamiltonov graf

• Hamiltonov put (ciklus) je razapinjući put (ciklus): put (ciklus) koji sadrži sve vrhove.
• Graf je Hamiltonov ako sadrži Hamiltonov ciklus.

Bojenje vrhova

• Bojenje vrhova grafa G je funkcija f: V(G) -> C sa skupa vrhova grafa u skup boja C (C je skup boja). Bojenje je pravilno ako susjedni vrhovi nisu obojeni istom bojom.

Bojenje Bridova

• 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 incidentna istom vrhu nisu obojena istom bojom.

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.

Eulerova Formula

• χ(G) = v(G) - e(G) + f(G) = 2, gdje je:
  • χ(G) je Eulerova karakteristika,
  • v(G) je broj vrhova,
  • e(G) je broj bridova,
  • f(G) je broj strana grafa.