Diskretna matematika i teorija grafova - zadaci sa rešenjima

Rešenje:
U prostom grafu (bez petlji i višestrukih grana) svaki čvor može biti susedan samo ostalim [tex]n-1[/tex] čvorovima, pa stepen svakog čvora pripada skupu [tex]\{0; 1; \ldots; n-1\}[/tex], koji ima [tex]n[/tex] elemenata.
Vrednosti [tex]0[/tex] i [tex]n-1[/tex] ne mogu se pojaviti istovremeno: čvor stepena [tex]n-1[/tex] susedan je svim ostalim čvorovima, pa tada nema čvora stepena [tex]0[/tex]. Prema tome, [tex]n[/tex] stepeni uzimaju najviše [tex]n-1[/tex] različitih vrednosti — iz jednog od skupova
[tex]\{0; 1; \ldots; n-2\}\text{ ili }\{1; 2; \ldots; n-1\}[/tex]
Prema Dirihleovom principu, dva od [tex]n[/tex] čvorova imaju jednake stepene.

Rešenje:
Koristimo da je [tex]\overline{u}=u\oplus 1[/tex] i [tex]1\oplus 1=0[/tex]. Najpre zamenjujemo promenljive njihovim negacijama:
[tex]f(\overline{x},\overline{y})=(x\oplus 1)\oplus(y\oplus 1)\oplus 1=x\oplus y\oplus 1[/tex]
Zatim negiramo rezultat:
[tex]f^*(x,y)=\overline{x\oplus y\oplus 1}=x\oplus y\oplus 1\oplus 1=x\oplus y[/tex]
Provera tablicom istinitosti: za [tex](x; y)[/tex] jednako [tex](0; 0)[/tex], [tex](0; 1)[/tex], [tex](1; 0)[/tex], [tex](1; 1)[/tex] funkcija [tex]f[/tex] uzima vrednosti [tex]1; 0; 0; 1[/tex], a [tex]f^*[/tex] vrednosti [tex]0; 1; 1; 0[/tex], tj. [tex]f^*=\overline{f}[/tex].
Česta greška je da se izračuna samo [tex]f(\overline{x},\overline{y})[/tex] i zaboravi spoljašnja negacija; tako se dobija sama funkcija [tex]f[/tex], tj. pogrešan odgovor [tex]x\oplus y\oplus 1[/tex].

Rešenje:
Neka je [tex]A[/tex] matrica susedstva grafa [tex]G[/tex]. Element [tex](A^k)_{ij}[/tex] jednak je broju šetnji dužine [tex]k[/tex] od [tex]v_i[/tex] do [tex]v_j[/tex] (indukcijom po [tex]k[/tex]: šetnja dužine [tex]k+1[/tex] je šetnja dužine [tex]k[/tex] za kojom sledi još jedna grana). Posebno, [tex](A^2)_{ij}[/tex] je broj zajedničkih suseda čvorova [tex]v_i[/tex] i [tex]v_j[/tex] (stepen čvora [tex]v_i[/tex] za [tex]i=j[/tex]). Skupovi suseda čvorova su:
[tex]N(v_1)=\{v_3,v_4,v_5\}; \quad N(v_2)=\{v_4,v_5\}; \quad N(v_3)=\{v_1,v_5\}[/tex]
[tex]N(v_4)=\{v_1,v_2,v_5\}; \quad N(v_5)=\{v_1,v_2,v_3,v_4\}[/tex]
Druga vrsta matrice [tex]A^2[/tex] (zajednički susedi čvora [tex]v_2[/tex] sa [tex]v_1,\ldots,v_5[/tex]) je [tex](2; 2; 1; 1; 1)[/tex], a peta kolona (zajednički susedi čvora [tex]v_5[/tex] sa [tex]v_1,\ldots,v_5[/tex]) je [tex](2; 1; 1; 2; 4)[/tex]. Pošto je [tex]A^4=A^2A^2[/tex], dobijamo
[tex](A^4)_{25}=\sum_{k=1}^{5}(A^2)_{2k}(A^2)_{k5}=2\cdot 2+2\cdot 1+1\cdot 1+1\cdot 2+1\cdot 4=13[/tex]

Rešenje:
Ovo je linearna nehomogena rekurentna relacija sa konstantnim koeficijentima. Karakteristična jednačina [tex]r^2-3r+2=0[/tex] ima korene [tex]r_1=1[/tex] i [tex]r_2=2[/tex], pa je opšte rešenje homogene relacije [tex]C_1+C_2\cdot 2^n[/tex].
Desna strana je konstanta [tex]1=1\cdot 1^n[/tex], a [tex]1[/tex] je prost koren karakteristične jednačine, pa partikularno rešenje tražimo u obliku [tex]p_n=Cn[/tex] (konstanta bi bila sadržana u rešenju homogene relacije):
[tex]Cn=3C(n-1)-2C(n-2)+1=Cn+C+1\Rightarrow C=-1[/tex]
Dakle, [tex]a_n=C_1+C_2\cdot 2^n-n[/tex]. Iz početnih uslova:
[tex]\begin{cases}C_1+2C_2-1=1\\ C_1+4C_2-2=2\end{cases}\Rightarrow C_2=1; \ C_1=0[/tex]
Prema tome, [tex]a_n=2^n-n[/tex]. Provera:
[tex]a_3=3\cdot 2-2\cdot 1+1=5=2^3-3; \qquad a_4=3\cdot 5-2\cdot 2+1=12=2^4-4[/tex]

Rešenje:
Pretpostavimo da [tex]G[/tex] nema ciklus. Neka je [tex]u[/tex] jedini čvor stepena [tex]1[/tex], a [tex]K[/tex] komponenta povezanosti grafa [tex]G[/tex] koja sadrži [tex]u[/tex]; ona sadrži bar granu koja spaja [tex]u[/tex] s njegovim susedom. Pošto je [tex]K[/tex] konačna, u njoj postoji najduži put
[tex]P=w_0w_1\ldots w_k,\quad k\ge 1[/tex]
Neka je [tex]x[/tex] sused čvora [tex]w_0[/tex] različit od [tex]w_1[/tex]. Ako [tex]x[/tex] leži na [tex]P[/tex], tj. [tex]x=w_j[/tex] za [tex]j\ge 2[/tex], onda je [tex]w_0w_1\ldots w_jw_0[/tex] ciklus. Ako [tex]x[/tex] ne leži na [tex]P[/tex], onda je [tex]xw_0w_1\ldots w_k[/tex] duži put. Oba slučaja su nemoguća, pa [tex]w_0[/tex] nema drugih suseda osim [tex]w_1[/tex] i njegov stepen je [tex]d(w_0)=1[/tex]. Analogno je [tex]d(w_k)=1[/tex].
Pošto je [tex]k\ge 1[/tex], čvorovi [tex]w_0[/tex] i [tex]w_k[/tex] su različiti, pa [tex]G[/tex] ima bar dva čvora stepena [tex]1[/tex], što je u suprotnosti sa pretpostavkom. Prema tome, [tex]G[/tex] sadrži ciklus.