PRIMENE RAČUNARA - novembar 2002.

1. Zadato je n ≥ 2 prirodnih brojeva d_{1}, d_{2}, …, d_{n} takvih da im je zbir 2n − 2. Da li postoji stablo sa n čvorova čiji su stepeni brojevi d_{1}, d_{2}, …, d_{n}? Odgovor obrazložiti! Odgovor je postoji. Dokažimo to.

Stepen čvora je broj grana koje su mu susedne. U sumi stepena čvorova d_{1} + … + d_{n} svaka grana se broji tačno dva puta. Dokaz izvedimo indukcijom po n (broju čvorova) Baza: Ako n = 2 je d_{1} + d_{2} = 2 => d1 = d2 = 1 i postoji ovakvo stablo, jer dva čvora povezana granom jesu upravo stablo koje ima 2 čvora i to oba stepena 1 IH: Pretpostavimo da je tvrdenje tacno za n-1 brojeva i neka je dato n ≥ 3 prirodnih brojeva d_{1}, d_{2}, …, d_{n} čiji je zbir d_{1} + … + d_{n} = 2n − 2. Tada postoje bar jedno i (1 ≤ i ≤ n), bar jedno j (1 ≤ j ≤ n) tako da d_{i} = 1, d_{j} > 1. Zašto? SP: Za svako i ≤ n da su d_{i} ≠ 1. Tada ne može biti d_{1} + … + d_{n} = 2n − 2 (IH) Slično za d_{j} se pretpostavi suprotno: za svako j ≤ n je d_{j} ≤ 1 . Tada je d_{1} + … + d_{n} ≤ n, a opet za n ≥ 3 je n < 2n − 2. Izbacimo iz skupa d_{i} i umanjimo d_{j} za jedan i dobice se skup za koga po IH postoji stablo sa tim stepenima. Zatim na to stablo dodamo novi cvor, zapravo list stepena di=1 prikacenog za cvor stepena d_{j} − 1 ≥ 1 i dobija se stablo iz f-lacije zadtaka, tj. stablo sa n cvorova stepena d_{1}, d_{2}, … d_{n} . Rešenje problema u opštem slučaju nije jedinstveno.

2. Neka je G = (V, E) usmereni graf i neka T je DF S stablo grafa G. G sadrži usmereni ciklus ako i samo ako G sadrži povratnu granu (u odnosu na T). Dokazati. REŠENJE: Lema1: Grana (u, v) usmerenog grafa G je povratna ako i samo ako prema odlaznoj numeraciji (DFS) čvor u prethodi čvoru v, tj. u.P ost ≤ v.P ost

Ako je grana (u,v) povratna, onda ona zajedno sa granama stabla na putu od u do v zatvara ciklus. Takodje je tačno i suprotno tvrdjenje: ako u grafu postoji cklus, tada u njemu mora da postoji povratna grana. Zaista, pretpostavimo da u grafu postoji ciklus koji čine grane (v_{1}, v_{2}), (v_{v}2, v_{3}), … (v_{k}, v_{1}). Ako k = 1 (tj. ciklus je petlja), tada je grana (v, v) povratna. Ako je k veće od jedan, pretpostavimo da nijedna od grana (v_{1}, v_{2}), (v_{v}2, v_{3}), … (v_{k−1}, v_{k}) nije povratna. Po Lemi 1, onda važi da v_{1}.P ost > v_{2}.P ost > … v_{k}.P ost , odnosno v_{k}.P ost < v_{1}.P ost, pa je grana (v_{k}, v_{1}) povratna. Time je dokazano da u svakom ciklusu postoji povratna grana.

3. Dato je n tačaka u ravni i prava q. Konstruisati algoritam linearne složenosti za nalaženje prave paralelne sa q koja dati skup tačaka razbija na dva podskupa jednake veličine (ako tačka leži na toj pravoj, može se uračunati u bilo koji od podskupova). REŠENJE: Neka je prava q zadata jednačinom: y=kx + m Jednačina prave t paralelne sa q: y=kx + m’ Rastojanje tačke (x_{i},y_{i}) (gde i=1..n) od (x_{i},kx_{i} + m’) (ovo je projekcija (x_{i},y_{i}) u vertikalnom smeru na pravu t u pravcu y-ose) je: d_{i}=d{ (x_{i},y_{i}), (x_{i},kx_{i}+m’) }= y_{i}-kx_{i} -m’ (d_{i} je pozitivno/negativno ako je tačka (x_{i},y_{i}) iznad/ispod prave t). Da bi se zadovoljio zahtev iz formulacije onda se m’ bira tako da polovina brojeva d_{i} bude veća ili jednaka od nule. Zapravo to znači da će polovina brojeva y_{i}-kx_{i} biti veća ili jednaka od m’ . Dakle, za i=1..n se problem svodi na traženje medijane za y_{i}-kx_{i}, o čemu je bilo reči kod rangovskih statistika.

4. Pravilan graf je graf čiji svi čvorovi imaju isti isti stepen. Dokazati da je problem klika za neusmerene pravilne grafove NP -kompletan. REŠENJE: Svedimo opšti problem klika na problem klika za pravilne grafove. Neka je G = (V, E) proizvoljan graf i k proizvoljan broj. Kontruiše se pravilan graf R takav da graf G ima kliku veličine ≥ k ako i samo ako R ima kliku veličine ≥ k, pri čemu se ne bi mogle samo dodvati grane u grafu G, dok ne postane pravilan graf, jer bi se mogle pojaviti nove i veće klike. Problem klika pripada klasi NP, jer se za svaki predpostavljeni podskup od k čvorova može za polinomijalno vreme proveriti da li je klika.

Neka je n broj čvorova grafa G. Neka je d maksimalni stepen grafa G ako je taj broj paran, a maksimalni stepen grafa G plus jedan, inače (dakle, vrednost d je uvek parna). Za svaki čvor v grafa G stepena d(v) < d dodaje se d − d(v) novih čvorova i povezujemo ih sa v. Ukupan broj novih čvorova je

dn − ∑_{i=1}^{n} d(v_{i}) = dn − 2|E|

Ovaj broj je paran, jer je broj d paran. Treba povezati nove čvorove tako da svi imaju stepen d. Nove klike nisu napravljene (jer je savki novi čvor povezan samo s ajednim čvorom). Skup novih čvorova podelimo na dva dela sa jednakim brojem čvorova. Svaki čvor iz jedne grupe povežimo sa tačno d − 1 čvorova iz druge (pri čemu se vodi računa da stepeni novih čvorova iz druge grupe ne prevazidju broj d). Novi čvorovi indukuju bipartitivni graf (sa klikom ne većom od dva). Tako dobijen graf je pravilan i on ima kliku veličine ≥ k ako i samo ako graf G ima kliku veličine ≥ k. Time je klika problem sveden na klika problem za pravilne grafove. Kako je klika problem NP -kompletan problem, sledi da je i klika problem za pravilne grafove NP -kompletan.