Teorija Grafova

Question 1

Kada se za niz nenegativnih celih brojeva D=(d1, d2, …, dn) kaže da je grafovski (grafički)? Kada je valjan? Kako se ispituje da li je niz grafovski?
(Oktobar 2019) (Septembar 2020)

Answer 1

Niz nenegativnih celih brojeva D=(d1, d2, …, dn) naziva se grafičkim (grafovskim) ako postoji graf G=(V,E), V={1,2,…,n} tako da je za svako i, di=di, i=1,2,…,n.

Niz nenegativnih brojeva D=(d1, d2,…,dn) je pravilan (valjan) ako važe nejednakosti
n-1≥d1≥d2≥…≥dn≥0

Provera grafičkog niza
Neka je dat niz D=(d1, d2,…,dn).

Korak 1: Proverava se da li je dati niz pravilan. Ako nije, prelazimo na korak 4. Ako jeste, prelazimo na korak 2.

Korak 2: Formira se niz
D1=(d2-1,d3-1,…, dd1+1-1, dd1+2,…,dn).
Proverava se da li je niz D1 pravilan. Ako nije, prelazi se na korak 4. Ako jeste, prelazi se na korak 3.

Korak 3: Proverava se da li je niz D1 nula niz. Ako jeste, prelazi se na korak 5. Ako nije, obavi se supstitucija D≔D1 i prelazi na korak 1.

Korak 4: Dati niz D nije grafički.

Korak 5: Dati niz D je grafički.

Question 2

Dokazati da u grafu G sa n čvorova postoje bar dva čvora sa istim stepenima. (Jun 2018 usmeni)

Answer 2

Neka je dat graf G=(V,E), V={x1,x2,…, xn}, E=m. Tada u grafu G postoje bar dva čvora istog stepena.
Dokaz: Polazimo od toga da uvek važi:
n-1≥dxn≥…≥d(x1)≥0

Sada pretpostavimo suprotno – da u grafu G ne postoje dva čvora istog stepena.

To znaci da su svi cvorovi u grafu razlicitog stepena, tj.
da je
0 ≤ d(x1) < d(x2) < · · · < d(xn) ≤ n − 1.
To znaci da u grafu G postoji cvor x1 tako da je d(x1) = 0, da nije susedan ni
sa jednim, i cvor xn tako da je d(xn) = n − 1, tj. da je susedni sa svima.
To je
nemoguce.

Question 3

Šta je most, viseći most i artikulacioni čvor? (Jun 2019)

Answer 3

Most je grana grafa čijim se udaljavanjem iz grafa, bez incidentnih čvorova, povećava broj komponenti povezanosti grafa.
Viseći most je most koji je incidentan sa čvorom stepena 1.
Artikulacioni čvor je onaj čvor u grafu čijim se udaljavanjem iz datog grafa, zajedno sa incidentnim granama, povećava broj komponenti povezanosti.

Question 4

Ojlerovi grafovi. (Januar 2017) (Septembar 2016)

Answer 4

Multigraf (graf) je polu-Ojlerov ako u njemu postoji prost put, koji se naziva Ojlerov, koji sadrži sve njegove grane.
Multigraf (graf) je Ojlerov ako u njemu postoji ciklus, koji se naziva Ojlerov, koji sadrži sve njegove grane.

Question 5

Navesti i dokazati Ojlerovu teoremu za planarne grafove. (Decembar 2016) (Oktobar 2016)

Answer 5

Povezan planarni graf G = (V, E), definisan skupovima V = {x1,x2, . . . , xn} i E = {l1, l2, . . . , lm}, deli ravan u kojoj je predstavljen na f = m − n + 2 oblasti. (5.47)

Dokaz cemo izvesti pomocu matematicke indukcije, po broju grana datog
grafa. Kako je dati graf povezan, minimalan broj grana u njemu je m = n − 1.
U ovom slucaju planarni graf je tipa stabla, a znamo da stablo ne sadrzi ni jednu konturu, tj. ne ogranicava ni jedan deo ravni. Za stablo je f = 1. Zamenom m = n − 1 u (5.47) dobijamo takodje da je f = 1, tj. da Ojlerova teorema vazi za m = n − 1.
Neka je m fiksiran broj, m > n − 1. Tada odgovarajuci graf G ima bar jednu konturu. Pretpostavimo da (5.47) vazi za m − 1 granu. Kako graf G ima bar jednu konturu, uocimo neku njegovu granu sa konture. Ta grana je granicna za dve oblasti. Ako je udaljimo dobijamo novi graf G1, koji ima m − 1
granu i deli ravan na f − 1 oblast. Na osnovu induktivne pretpostavke imamo da
je f − 1 = (m − 1) − n + 2, odakle sleduje da za graf sa m grana vazi jednakost
(5.47).

Question 6

Poluhamiltonovi i Hamiltonovi grafovi. (Decembar 2016) (Oktobar 2016)

Answer 6

Multigraf (graf ) je polu–Hamiltonov ako postoji elementarni put, koji se naziva Hamiltonov, koji sadrži sve njegove čvorove.
Multigraf (graf ) je Hamiltonov ako postoji prost ciklus, koji se naziva Hamiltonov, koji sadrži sve njegove čvorove.

Question 7

Brojevima od 1 do 9 označiti Hamiltonov put u grafu G=(V, E) sa slike

Answer 7

// Moramo proći kroz sve čvorove, tako da se ni čvorovi ne ponavljaju. Ne moramo proći kroz sve grane. Moramo krenuti od čvora parnog stepena.

Question 8

Neka je G planarni povezani graf sa n čvorova, m grana i r-regularan. Dokazati da je tada n=2(ƒ-2)/(r-2), ako je r≠2 ili m=n i ƒ=2 ako je r=2. (Septembar 2018)

Answer 8

Neka r-regularan povezan planaran graf ima n čvorova, m grana i deli ravan na f oblasti. Tada na osnovu jednakosti
m=r⋅n/2   i   m-n=f-2
dobijamo da je 
n=2(f-2)/r-2   za   r≠2
i
m=n   i   f=2   za   r=2

Question 9

Koliko čvorova ima povezan planarni graf, ako postoji, ako je
3-regularan i deli ravan na 4 oblasti
5-regularan i deli ravan na 11 oblasti
(Jun 2019) (Jun 2018 usmeni)

Answer 9

Neka r-regularan povezan planaran graf ima n čvorova, m grana i deli ravan na f oblasti. Tada na osnovu jednakosti
m=r⋅n/2   i   m-n=f-2
dobijamo da je 
n=2(f-2)/r-2   za   r≠2
i
m=n   i   f=2   za   r=2

a) Za r=3 i f=4 dobijamo da je n=2(f-2)/(r-2)=2*(4-2)/3-2=4/1=4. Planaran graf sa ovim karakteristikama postoji i to je graf K4.
b) Za r=5 i f=11 dobijamo da je n=2(f-2)/r-2=2(11-2 )/(5-2)=2∙9/3=6. To je graf K6. On nije planaran, jer je Kn planaran samo za 1≤n≤4.

Question 10

Neka povezani planarni graf G koji ima n čvorova i m grana, deli ravan na ƒ oblasti. Dokazati da važi nejednakost
m≤3(n-2)
Dokazati da u planarnom grafu postoji bar jedan čvor čiji je stepen manji od 6.
Kada nastupa jednakost? Ako je graf pri tome i bipartitni, dokazati da važe nejednakosti
2ƒ≤m≤2(n-2)

Answer 10

Pretpostavimo da je graf G=(V,E) acikličan. Tada važi nejednakost m≤n. Kako je n≥3 važi i nejednakost 2n≥6. Na osnovu ove dve nejednakosti važi tražena nejednakost.
	Neka je dati graf G=(V,E) cikličan. Minimalan broj grana koje grade jedan ciklus je 3, pri čemu svaka grana učestvuje dva puta u razgraničavanju svake oblasti, te važi nejednakost 3f≤2m. Na osnovu jednakosti Ojlera: 2=n-m+f važi 
6=3n-3m+3f
3f=6-3n+3m
6-3n+3m≤2m
m≤3n-6
m≤3(n-2) 
što je traženi rezultat.

Pretpostavimo da je dat planaran graf G = (V, E), definisan skupovima V = {x1, x2, . . . , xn} i E = {l1, l2, . . . , lm}, pri cemu je d(xi) ≥ 6, za svako i = 1, 2, . . . , n. Tada na osnovu nejednakosti 2m = ∑(n i=1) d(xi) ≥ 6n, dobijamo da je n ≤ 1/3 m (5.48).
Svaka ogranicena oblast u ravni koju ogranicava planarni graf, je ogranicena sa najmanje tri njegove grane, pri cemu se svaka grana pojavljuje dva puta kao granica iste oblasti ako je most i razlicite ako nije. Zbog toga vazi nejednakost 3f ≤ 2m, tj. f ≤ 2/3 m. (5.49) Zamenom (5.48) i (5.49) u f=m-n+2 dobijamo da vazi nejednakost 2 = f − m + n ≤ 2/3 m + 1/3 m − m = 0, sto je nemoguce. To znaci da je nasa pretpostavka da je d(xi) ≥ 6, za svako i = 1, 2, . . . , n, bila pogresna. Znaci da postoji bar jedan cvor ciji je stepen manji od 6.

Nek je dat proizvoljan povezan planaran bipartitan graf sa bar 2 grane. Ukoliko je ovaj graf stablo, onda se dobija trivijalni podslučaj kada važi f=1 i m=n-1≥2. Očigledno važi m≥2f, kao i m≤2(n-2), tako da je dokaz gotov.
Pretpostavimo da je dat graf koji nije stablo. U ovom slučaju svakoj oblasti odgovara ciklus čija je dužina bar 4 i parna, pošto bipartitni grafovi nemaju cikluse neparne dužine. Dakle, svaki ciklus generiše bar 4 nove grane, pri čemu se ovakvim principom generisanja grana svaka od njih javlja dva puta. Direktno sledi 4f≤2m, odnosno 2f≤m. Ako ovu nejednakost ubacimo u Ojlerovu jednakost m-n=f-2, sledi:
m-n≤m/2-2
m/2≤n-2
m≤2(n-2)
čime je dokaz gotov.

Question 11

Komplement grafa.

Answer 11

Graf G ̅=(V,E ̅) je komplement grafa G pri čemu su dva čvora u i v, iz V, susedna u grafu G ̅, {u,v}∈E ̅, ako i samo ako nisu susedna u grafu G, {u,v}∉E.

primer KVADAR X

Question 12

Definisati samokomplementirajući graf. Ako je graf G=(V,E), |V|=n ≥1, samokomplementirajući dokazati da je:
n≡0 mod 4 ili n≡1 mod 4.
(Septembar 2018) (April 2020) (Septembar 2020)
Kako glasi obrnuto tvrđenje? Šta se može reći ako je n≡2mod5 ili n≡3mod4?

Answer 12

Graf G je samokomplementirajući ako i samo ako je izomorfan svom komplementu G ̅.
Dokaz: Fizičkim preklapanjem grafova G=(V,E), |V|=n, i njegovog komplementa G ̅=(V,E ̅), po čvorovima koji su isto označeni, dobija se graf G ̂=(V,G ̂). Ovaj graf ima |E ̂ |=((n nad 2)) grana. Kako je graf G=(V,E) samokomplementirajući, važi jednakost |E|=|E ̅ |=1/2|E ̂|, tj. |E|=(n(n-1))/4. To znači da n mora biti oblika
n=4k ili n=4k+1
za svako k∈N, što je i trebalo dokazati.

Moguce je dokazati rezultat Teoreme 5.22 u obrnutom smeru.

b)Ma samo napises ako nije kongruentno sa 0 ili 1 po modulu 4, sigurno nije samokomplementirajuci, Moze se reci nije samokomplementirajuci

Question 13

Neka je G prost povezan graf sa n čvorova i m grana. Dokazati da tada važe nejednakosti
n-1≤m≤(n(n-1))/2
Kada u ovim nejednakostima nastupaju jednakosti?
(Jun 2019)

Answer 13

a) E sad stablo ti je minimalno povezan graf, u smislu ako otklonis jednu granu ode sve, postaje nepovezan, i ima smisla da to bude donja granica, a gornja se odnosi na situaciju gde je bas svaki stepena n-1, a to je maksimalni stepen koji cvor moze da ima, u tom slucaju imas gotovu formulu tu da je 2m=n*(n-1), pa odatle ova gornja granica
b) LEVA KAD JE STABLO, DESNA KAD JE KOMPLETAN GRAF

Question 14

Neka je G=(V,E) dati graf. Definisati graf grana L(G), pridružen grafu G. Ako je graf G sa n čvorova regularan, stepena regularnosti r, koliko čvorova i koliko grana ima graf L(G)? Da li je i L(G) regularan? Ako je graf L(G) regularan, šta se može reći za graf G?
(Januar 2017) (Septembar 2016)

Answer 14

Graf grana L(G)=(V_1,E_1), V_1=E, pri čemu su dva čvora susedna u L(G) ako i samo ako su odgovarajuće grane susedne u grafu G.
SLIKA
TABELA
Vidimo da graf L(G) ima (n⋅r)/2 čvorova i (n⋅r(r-1))/2 grana. Graf L(G) je reda regularnosti 2(r-1).

Question 15

BINARNE OPERACIJE

Answer 15

TABELA

Question 16

15. Definisati dekartovu sumu i proizvod dva grafa. (Jun 2020)

Answer 16

Neka su dati grafovi G_1=(V_1,E_1 ) i G_2=(V_2,E_2 ), V_1={x_1,x_2,…,x_n }, V_2={y_1,y_2,…,y_m }.
Dekartova suma grafova G_1 i G_2 je graf G=G_1⊕G_2=(V,E), pri čemu je V=V_1×V_2. Dva čvora (x_(i_1 ),y_(j_1 )) i (x_(i_2 ),y_(j_2 )) su susedna u grafu G ako i samo ako je x_(i_1 )=x_(i_2 ) i čvorovi y_(j_1 ) i y_(j_2 ) su susedni u grafu G_2, ili je y_(j_1 )=y_(j_2 ) i čvorovi x_(i_1 ) i x_(i_2 ) su susedni u grafu G_1.

Neka su dati grafovi G_1=(V_1,E_1 ) i G_2=(V_2,E_2 ), V_1={x_1,x_2,…,x_n }, V_2={y_1,y_2,…,y_m }.
Dekartov proizvod grafova G_1 i G_2 je graf G=G_1⊗G_2=(V,E), pri čemu je V=V_1×V_2. Dva čvora (x_(i_1 ),y_(j_1 )) i (x_(i_2 ),y_(j_2 )) su susedna u grafu G ako i samo ako su čvorovi x_(i_1 ) i x_(j_2 ) susedni u grafu G_1 i čvorovi y_(i_2 ) i y_(j_2 ) su susedni u grafu G_2.

Question 17

16. Koristeći pojmove povezanost, ciklus i elementarni put, navesti 6 definicija stabla. (Jun 2018 usmeni)

Answer 17

Stablo je graf koji je povezan i acikličan

Stablo je graf koji je povezan i ima (n-1) granu

Stablo je graf koji je acikličan i ima (n-1) granu

Stablo je graf koji ako ima (n-1) granu i povezan je, gubi tu osobinu ako mu se oduzme jedna grana

Stablo je graf koji je acikličan i ima (n-1) granu, ali dodavanjem grane između bilo koja dva nesusedna čvora on postaje cikličan

Stablo je graf u kome su svaka dva čvora u grafu povezana elementarnim putem

Question 18

Dokazati da svako stablo sadrži bar dva čvora stepena 1

Answer 18

Neka je G=(V,E), V={x_1,x_2,…,x_n}, |E|=n-1, dato stablo.
Pretpostavimo da stablo G ne sadrži nijedan čvor stepena 1, već da je d(x_i)≥2, za svako i=1,2,…,n. Tada na osnovu jednakosti:
2m=∑(i=1)^n〖d(x_i)〗
važi
2m=2(n-1)=∑(i=1)^n〖d(x_i)〗≥ ∑_(i=1)^n 2=2n
što je nemoguće.

Pretpostavimo da stablo sadrži jedan čvor stepena 1, na primer, neka je d(x_1 )=1. Tada bi važilo
2m=2(n-1)=∑(i=1)^n〖d(x_i)〗=d(x_1 )+∑(i=2)^n〖d(x_i 〗)≥1+∑_(i=2)^n2=1+2(n-1)
što je nemoguće.
Zaključujemo da graf sadrži bar dva čvora stepena 1.

Question 19

Navesti primere stabla koji sadrži tačno 2 čvora i stabla koji ima tačno n-1 čvorova stepena 1

Answer 19

Čvor u stablu koji ima stepen 1 naziva se list.
Čvor u stablu čiji je stepen veći ili jednak 3 naziva se račvište (čvor u kome se stablo račva).
Put dužine n, u oznaci P_n, je jedino stablo koje sadrži dva, i samo dva čvora stepena 1, a ostali su stepena 2.

PRAVA LINIJA ----* P5

Zvezda od n čvorova, u oznaci K_(1,n-1) je jedino stablo koje sadrži jedan čvor stepena n-1, a ostali su stepena 1.

Question 20

Neka je G povezan graf sa n čvorova i m grana. Izvesti ciklomatski broj za ovaj graf. Šta je ciklomatski broj povezanog grafa? (Jun 2018) (Januar 2017) (Septembar 2016)

Answer 20

Neka graf ima n čvorova, m grana i p komponenti povezanosti. Tada važe jednakosti:
r(G)=n-p i γ(G)=m-n+p
Dokaz: Pretpostavimo da svaka komponenta povezanosti datog grafa (multigrafa) sadrži n_i, i=1,2,…,p, čvorova, n=n_1+n_2+⋯+n_p. Da bi svaka komponenta povezanosti bila stablo ona mora da ima n_i-1 grana. To znači da je ukupan broj grana u odgovarajućoj sprežnoj šumi
r(G)=∑_(i=1)^p▒〖(n_i-1)〗=n-p
Kako dati graf ima m grana, prilikom formiranja sprežne šume (stabla) odstranjeno je
γ(G)=m-r(G)=m-n+p,
grana, što je ciklomatski broj, tj. broj nezavisnih ciklusa u grafu.
Kako je broj komponenti povezanosti u povezanom grafu p=1, tada sledi:
γ(G)=m-n+1
Ciklomatski broj predstavlja broj nezavisnih prostih ciklusa u datom grafu (multigrafu) G, u oznaci γ(G). Ciklomatski broj grafa G jednak je broju grana koje treba odstraniti iz grafa da bi se formirala šuma (stabla).

Question 21

Neka je G povezan graf sa n čvorova i m grana. Izvesti ciklomatski broj, γ, i broj oblasti, ƒ, koje graf ograničava u ravni. Naći vezu između ova dva broja. (Jun 2020)

Answer 21

Pretpostavimo da svaka komponenta povezanosti datog grafa (multigrafa) sadrži n_i, i=1,2,…,p, čvorova, n=n_1+n_2+⋯+n_p. Da bi svaka komponenta povezanosti bila stablo ona mora da ima n_i-1 grana. To znači da je ukupan broj grana u odgovarajućoj sprežnoj šumi
r(G)=∑_(i=1)^p▒〖(n_i-1)〗=n-p
Kako dati graf ima m grana, prilikom formiranja sprežne šume (stabla) odstranjeno je
γ(G)=m-r(G)=m-n+p,
grana, što je ciklomatski broj, tj. broj nezavisnih ciklusa u grafu.
Kako je broj komponenti povezanosti u povezanom grafu p=1, tada sledi:
γ(G)=m-n+1
Neka je G dati povezani planarni graf sa n čvorova i m grana. Tada on deli ravan na
f=m-n+2
oblasti.
Dokaz: Uočimo izraz
g=f+n-m
Pretpostavimo da smo iz povezanog planarnog grafa udaljili jednu granu, koja nije most ili viseći most. Tada je broj čvorova ostao isti, broj unutrašnjih oblasti se smanjio za jedan. Tada za izraz g važi
g=(f-1)+n-(m-1)=f+n-m
tj. ostao je nepromenjen.
Nastavimo ovaj postupak dok na osnovu datog povezanog planarnog grafa ne dobijemo stablo. Tada se broj čvorova nije promenio, broj grana se smanjio za m-n+1, a broj oblasti se takođe smanjio za ovaj broj. To znači da je izraz g ostao nepromenjen. S druge strane, stablo je planarni graf koji ima n čvorova, m=n-1 grana, i odvaja f=1 oblast u ravni. Tako je
g=f+n-m=1+n-n+1=2
čime je dokaz završen.
γ(G)=m-n+1
f=m-n+2
→f=γ(G)+1

Question 22

Neka je G povezani planarni graf sa n čvorova i m grana koji deli ravan na ƒ oblasti. Naći vezu između veličine ƒ i ciklomatskog broja grafa. (Jun 2018 usmeni)

Answer 22

γ(G)=m-n+1
f=m-n+2
→f=γ(G)+1

Question 23

Neka su T i T’ dva različita sprežna stabla datog povezanog grafa G. Opisati postupak i proceduru transformacije stabla T u stablo T^’. (Oktobar II 2016)

Answer 23

Proizvoljna dva sprežna stabla formirana na osnovu grafa G=(V,E), |V|=n≥2, mogu se transformisati jedan u drugi sukcesivnim formiranjem takozvanog monotonog niza sprežnih stabala.

Neka su T i T’ dva sprežna stabla, formirana na osnovu datog povezanog grafa G. želja nam je da sprežno stablo T transformišemo u sprežno stablo T’. U tom cilju formira se niz sprežnih stabala
T=T_1,T_2,… ,T_p=T^’, 1≤p≤n-1
na osnovu sledećih kriterijuma:
Stabla T_k i T_(k+1), k=1,2,… ,n-1, međusobno se razlikuju samo po jednoj grani.
Stablo T_(k+1), za svako k=1,2,…,n-1, ima jednu više zajedničku granu sa stablom T’, u odnosu na stablo T_k.

Ovako formirani niz sprežnih stabala, za dati povezani graf G, na osnovu koga se sprežno stablo T transformiše u sprežno stablo T’ naziva se monotonim nizom.

Sama transformacija sprežnog stabla T u T' može se opisati sledećom procedurom:

Neka je e^' proizvoljna grana stabla T^' koja ne pripada stablu T. Tada u stablu T postoji jedinstveni elementarni put koji povezuje čvorove incidentne sa granom e'. Ovaj put sadrži bar jednu granu e koja ne pripada stablu T', jer bi u protivnom u stablu T' postojao ciklus, što je nemoguće. Sada u stablu T=T_1 udaljimo granu e i pridodamo granu e'. Time smo formirali novo sprežno stablo T_2.
Ako je T_2=T' postupak transformacije je završen i procedura se prekida. Ako to nije slučaj, ponavlja se korak 1.Kako svako stablo grafa G sadrži |E|=n-1 grana, procedura se završava za najviše n-1 koraka.

Question 24

Opisati dekadno kodiranje i dekodiranje stabla. Ako je dekadni kod stabla D=62280, šta se može reći za stablo? Skicirati odgovarajuće stablo. (Jun 2020) (Oktobar 2020)

Answer 24

Dekadno kodiranje zasnovano je na sledećim pravilima:
Svakom čvoru dodeliti jedinstveni labelu (oznaku), tako da one budu međusobno uporedive. Najjednostavnije je da svakom čvoru dodelimo broj.
Kodiranje počinje i završava se u korenu stabla
Prelazak svake grane od korena kodira se jednom jedinicom.
U svakom račvištu krećemo ka čvoru sa manjom oznakom (brojem), ako ga nismo obišli.
Kada dođemo do lista, vraćamo se nazad, i svaku pređenu granu kodiramo nulom.
Pri kretanju nazad u svakom račvištu biramo kretanje ka čvoru, koga nismo obišli, sa manjom oznakom (brojem)
Kada se završi obilazak stabla, dobijeni broj prevodi se iz binarnog u dekadni i on predstavlja kod.
Dekadno dekodiranje:
Dekadni kod ne nosi informaciju o korenu. Zbog toga se za koren bira proizvoljni čvor, koga, uobičajeno, označimo sa 1. Kod se iz dekadnog prevodi u binarni brojni sistem. Dobijeni binarni niz se analizira s leva u desno. Svaka jedinica označava kretanje od korena i novi čvor. Svaka nula označava kretanje ka korenu za jedno mesto, po starim čvorovima. Dekodiranje se završava u novom korenu, tj. čvoru 1.
D=62280
Dekadni broj D u binarnom sistemu glasi
D=(1111001101001000)_2
Na osnovu koda, dobijamo sledeći graf (valjda):

ZAKLJUČAK: Na osnovu koda Prufera znamo kompletnu strukturu stabla. Na osnovu Dekadnog koda ne znamo apsolutno ništa.

Question 25

Pruferov kod. Kodiranje i dekodiranje. Šta se može na osnovu koda Prufera zaključiti o stablu, a šta na osnovu dekadnog koda? Neka je P=[1,2,2,2,3,3,3] Pruferov kod nekog stabla. Bez skiciranja, navesti karakteristike ovog stabla. (Jun 2018) i malo iz (Decembar 2016) (Oktobar 2016

Answer 25

Kodiranje se obavlja po sledećem algoritmu:
U početku je kod prazan
U stablu se pronalazi list (čvor stepena 1) sa najmanjom oznakom. Oznaka (broj) njegovog suseda se upisuje u kod (tj. radi se konkatenacija – nadovezivanje), a sam list se odstranjuje iz stabla
Proverava se da li novodobijeno stablo ima samo dva čvora. Ako je tako, kodiranje je završeno. Ako nije, prelazi se na korak 2
ZAKLJUČAK: Na osnovu koda Prufera znamo kompletnu strukturu stabla. Na osnovu Dekadnog koda ne znamo apsolutno ništa.
Dekodiranje koda Prufera:
Za proizvoljni vektor N=[a_1,a_2,…,a_n], označimo sa N^=[a_2,a_3,…,a_n] njegovo skraćivanje za prvi element.
Ako je P=[V_1,V_2,…,V_(n-2)] dati kod Prufera, odgovarajućeg stabla, njegovo dekodiranje se obavlja pomoću sledećih koraka:
Neka je P=[V_1,V_2,…,V_(n-2)] dati kod i N=[1,2,…,n] skup (vektor) čvorova odgovarajućeg stabla.
U vektoru (skupu) N pronalazi se najmanji broj V koji nije prisutan u vektoru P.
Čvorove označene sa V_1 i V spajamo granom.
Iz vektora N odstranjujemo broj V, N∶=N-V, a iz koda P prvi elemenat V_1, P^ ∶=P.
Ako je [N]=2, spajamo dva preostala čvora sa ovim oznakama i procedura je završena. U protivnom prelazi se na korak 2.
Stablo koje je kodirano kodom Prufera je, u principu slobodno, bez korena, mada se može uvesti i koren.
Na osnovu P=[1,2,2,2,3,3,3] znamo da stablo ima:
9 čvorova (ako stablo ima n čvorova, kod Prufera je dužine n-2)
8 grana
čvorovi 2 i 3 su stepena 4 (ako je neki čvor u stablu stepena p, njegova oznaka se u kodu pojavljuje p-1 puta), a čvor 1 je stepena 2.

Question 26

DODATAK1 Ako je G= (V,E), V={v1,v2, . . . ,vn}, E={e1,e2, . . . ,em}, dokazati da vazi jednakost
∑(n i=1)d(vi) =2m. (5.5)

Answer 26

Dokaz. Kako posmatramo grafove bez petlji, svaka grana datog grafa G = (V, E), ucestvuje u odredjivanju stepena tacno dva cvora, koji su njene krajnje tacke. Zbog toga se ona javlja tacno dva puta u ukupnom zbiru stepena svih cvorova datog grafa. Kako to vazi za svaku granu datog grafa, kojih ima m, sledi da vazi jednakost (5.5)
Posledica 5.1 Broj cvorova neparnog stepena datog grafa je paran broj

Question 27

Koliko kompletan bitrigraf ima preseka grana? (Decembar 2016) (Oktobar 2016)

Answer 27

Kompletan bitrigraf, K_3,3 izgleda ovako:

Dati graf možemo nacrtati i ovako:

Sa slike vidimo da ima 1 presek grana.