Diskretna matematika i teorija grafova - veoma teški zadaci sa rešenjima

Rešenje:
Posmatrajmo graf čiji su čvorovi gradovi, a grane direktne linije. Svaki čvor ima stepen najviše [tex]3[/tex], a svaka dva čvora su na rastojanju najviše [tex]2[/tex] (najviše jedno presedanje znači najviše dva leta).
Gornja granica. Fiksirajmo grad [tex]v[/tex]. Svaki drugi grad je ili sused grada [tex]v[/tex] ili sused nekog suseda grada [tex]v[/tex]. Grad [tex]v[/tex] ima najviše [tex]3[/tex] suseda, a svaki od njih ima najviše [tex]2[/tex] suseda različita od [tex]v[/tex]. Dakle, broj gradova je najviše
[tex]1+3+3\cdot 2=10[/tex]
Primer sa [tex]10[/tex] gradova (Petersenov graf): gradovi su [tex]\binom{5}{2}=10[/tex] dvočlanih podskupova skupa [tex]\{1,2,3,4,5\}[/tex], a dva grada su povezana ako su odgovarajući podskupovi disjunktni. Podskup [tex]\{a,b\}[/tex] disjunktan je sa tačno [tex]\binom{3}{2}=3[/tex] podskupa, pa je svaki stepen jednak [tex]3[/tex].
Dva različita podskupa koji nisu disjunktni imaju tačno jedan zajednički element, na primer [tex]\{a,b\}[/tex] i [tex]\{a,c\}[/tex]; preostala dva elementa [tex]d,e[/tex] čine podskup [tex]\{d,e\}[/tex], koji je disjunktan sa oba, pa su ta dva grada povezana sa jednim presedanjem. Dakle, [tex]10[/tex] gradova je moguće i odgovor je [tex]10[/tex].

Rešenje:
Činjenica [tex]1[/tex]: grana [tex]e=xy[/tex] je most ako i samo ako ne leži ni na jednom ciklusu. Ako [tex]e[/tex] leži na ciklusu [tex]C[/tex], svaka šetnja kroz [tex]e[/tex] može se preusmeriti duž puta [tex]C-e[/tex], pa uklanjanje grane [tex]e[/tex] ništa ne razdvaja. Obrnuto, ako [tex]e[/tex] nije most, onda su [tex]x[/tex] i [tex]y[/tex] povezani putem u [tex]G-e[/tex], i taj put zajedno sa [tex]e[/tex] čini ciklus.
Činjenica [tex]2[/tex]: uklanjanje mosta [tex]e=xy[/tex] povećava broj komponenti tačno za [tex]1[/tex]. Zaista, menja se samo komponenta koja sadrži [tex]e[/tex], a svaki njen čvor [tex]w[/tex] povezan je sa [tex]x[/tex] u [tex]G[/tex] nekim putem; ako taj put prekinemo pri prvom prolasku kroz [tex]e[/tex] (ako ga ima), dobijamo put u [tex]G-e[/tex] od [tex]w[/tex] do [tex]x[/tex] ili do [tex]y[/tex]. Dakle, ta komponenta se raspada na najviše dva dela, i to tačno na dva, jer je [tex]e[/tex] most.
Neka je sada [tex]B[/tex] skup mostova grafa [tex]G[/tex] i [tex]H=G-B[/tex] (isti čvorovi, bez mostova).
Korak [tex]1[/tex]: [tex]c(H)=c(G)+|B|[/tex]. Uklanjajmo mostove jedan po jedan. Uklanjanje grana ne stvara nove cikluse, pa je prema činjenici [tex]1[/tex] svaka preostala grana iz [tex]B[/tex] i dalje most trenutnog grafa, a prema činjenici [tex]2[/tex] svako uklanjanje povećava broj komponenti tačno za [tex]1[/tex].
Korak [tex]2[/tex]: komponente grafa [tex]H[/tex] su tačno komponente dvopovezanosti po granama grafa [tex]G[/tex].
Svaka komponenta [tex]K[/tex] grafa [tex]H[/tex] je dvopovezana po granama. Neka je [tex]e[/tex] grana iz [tex]K[/tex]. Ona nije most, pa prema činjenici [tex]1[/tex] leži na nekom ciklusu [tex]C[/tex] grafa [tex]G[/tex]. Nijedna grana ciklusa [tex]C[/tex] nije most (svaka leži na [tex]C[/tex]), pa je [tex]C\subseteq H[/tex], a kako je [tex]C[/tex] povezan i sadrži [tex]e[/tex], važi [tex]C\subseteq K[/tex]. Zamenom grane [tex]e[/tex] putem [tex]C-e[/tex] u svakoj šetnji u [tex]K[/tex] vidimo da je [tex]K-e[/tex] povezan.
Svaki podgraf [tex]S[/tex] grafa [tex]G[/tex] dvopovezan po granama sadržan je u jednoj komponenti grafa [tex]H[/tex]. Kada bi [tex]S[/tex] sadržao most [tex]e=xy[/tex], onda bi [tex]S-e[/tex] bio povezan, tj. [tex]x[/tex] i [tex]y[/tex] bi bili povezani u [tex]G-e[/tex] i grana [tex]e[/tex] bi ležala na ciklusu, što je u suprotnosti sa činjenicom [tex]1[/tex]. Dakle, [tex]S\subseteq H[/tex], a pošto je povezan, [tex]S[/tex] je sadržan u jednoj komponenti grafa [tex]H[/tex].
Iz ova dva tvrđenja sledi da je svaka komponenta grafa [tex]H[/tex] maksimalan podgraf grafa [tex]G[/tex] dvopovezan po granama, a svaki takav maksimalan podgraf sadržan je u nekoj komponenti grafa [tex]H[/tex], pa se s njom poklapa (izolovani čvorovi grafa [tex]H[/tex] su komponente sa jednim čvorom). Zato je
[tex]c_2(G)=c(H)=c(G)+|B|\ \Rightarrow\ |\mathrm{br}(G)|=c_2(G)-c(G)[/tex]

Rešenje:
Neka je [tex]n=10[/tex], [tex]m=26[/tex], [tex]t[/tex] broj trouglova, [tex]d(v)[/tex] stepen čvora [tex]v[/tex], a [tex]N(v)[/tex] skup njegovih suseda. Trouglovi koji sadrže granu [tex]xy[/tex] su [tex]xyz[/tex] sa [tex]z\in N(x)\cap N(y)[/tex], a svaki trougao ima [tex]3[/tex] grane, pa je
[tex]3t=\sum_{xy\in E}|N(x)\cap N(y)|[/tex]
Kako je [tex]N(x)\cup N(y)\subseteq V[/tex], prema principu uključenja-isključenja
[tex]|N(x)\cap N(y)|=d(x)+d(y)-|N(x)\cup N(y)|\ge d(x)+d(y)-n[/tex]
Sabiranjem po svim granama dobijamo [tex]3t\ge\sum_{xy\in E}\left(d(x)+d(y)\right)-mn[/tex]. U ovom zbiru svaki čvor [tex]v[/tex] učestvuje u [tex]d(v)[/tex] grana i svaki put doprinosi [tex]d(v)[/tex], pa je zbir jednak [tex]\sum_{v\in V}d(v)^2[/tex]. Prema Koši-Švarcovoj nejednakosti i lemi o rukovanju
[tex]\sum_{v\in V}d(v)^2\ge\frac{1}{n}\left(\sum_{v\in V}d(v)\right)^2=\frac{(2m)^2}{n}[/tex]
Prema tome,
[tex]3t\ge\frac{4m^2}{n}-mn=\frac{4\cdot 676}{10}-260=270{,}4-260=10{,}4[/tex]
odakle je [tex]t\ge\frac{10{,}4}{3}\gt 3[/tex]. Pošto je [tex]t[/tex] ceo broj, [tex]t\ge 4[/tex].

Rešenje:
Posmatrajmo graf čiji su čvorovi ljudi, a grane prijateljstva: svaka dva različita čvora imaju tačno jednog zajedničkog suseda. Neka je [tex]n[/tex] broj čvorova; za [tex]n=1[/tex] tvrđenje važi, pa neka je [tex]n\ge 2[/tex].
Korak [tex]1[/tex]: svaki stepen je paran. Neka je [tex]v[/tex] čvor i [tex]u\in N(v)[/tex], gde je [tex]N(v)[/tex] skup suseda čvora [tex]v[/tex]. Par [tex]u,v[/tex] ima tačno jednog zajedničkog suseda [tex]u'[/tex]; on pripada skupu [tex]N(v)[/tex] i [tex]u'\ne u[/tex]. Zajednički sused čvorova [tex]u'[/tex] i [tex]v[/tex] je [tex]u[/tex], pa je preslikavanje [tex]u\mapsto u'[/tex] involucija skupa [tex]N(v)[/tex] bez fiksnih tačaka. Ono deli [tex]N(v)[/tex] na parove [tex]\{u,u'\}[/tex], pa je stepen [tex]d(v)=|N(v)|[/tex] paran.
Korak [tex]2[/tex]: fiksirajmo čvor [tex]v[/tex] i neka je [tex]W=V\setminus\left(N(v)\cup\{v\}\right)[/tex], tj. [tex]|W|=n-1-d(v)[/tex]. Čvor [tex]u\in N(v)[/tex] susedan je sa [tex]v[/tex], sa [tex]u'[/tex] i ni sa jednim drugim čvorom iz [tex]N(v)[/tex] (takav čvor bi bio drugi zajednički sused čvorova [tex]u[/tex] i [tex]v[/tex]), pa [tex]u[/tex] ima tačno [tex]d(u)-2[/tex] suseda u [tex]W[/tex]. Svaki čvor [tex]w\in W[/tex] ima tačno jednog zajedničkog suseda sa [tex]v[/tex], tj. tačno jednog suseda u [tex]N(v)[/tex]. Prebrojavanjem grana između [tex]N(v)[/tex] i [tex]W[/tex] na dva načina dobijamo
[tex]n-1-d(v)=|W|=\sum_{u\in N(v)}\left(d(u)-2\right)[/tex]
Prema koraku [tex]1[/tex] desna strana je parna i [tex]d(v)[/tex] je parno, pa je [tex]n-1[/tex] parno, tj. [tex]n[/tex] je neparno. (Primer: [tex]k[/tex] trouglova sa zajedničkim čvorom daju takvu grupu od [tex]2k+1[/tex] osoba.)

Rešenje:
Neka je [tex]H[/tex] graf „nepoznatih“: dve osobe su susedne u [tex]H[/tex] ako se ne poznaju. Kako svi imaju isti broj [tex]d[/tex] poznanika, [tex]H[/tex] je regularan stepena [tex]s=n-1-d[/tex], pri čemu je [tex]s\ge 1[/tex], jer postoje dve osobe koje se ne poznaju. Osobe koje ostaju čine skup [tex]S[/tex] bez grana grafa [tex]H[/tex] unutar njega (nezavisan skup u [tex]H[/tex]).
Prebrojimo grane grafa [tex]H[/tex] između [tex]S[/tex] i [tex]V\setminus S[/tex]. Svaki čvor iz [tex]S[/tex] ima svih svojih [tex]s[/tex] suseda van [tex]S[/tex], što daje tačno [tex]s|S|[/tex] grana; svaki čvor van [tex]S[/tex] ima najviše [tex]s[/tex] suseda u [tex]S[/tex], što daje najviše [tex]s(n-|S|)[/tex] grana. Dakle, pošto je [tex]n[/tex] neparno,
[tex]s|S|\le s(n-|S|)\ \Rightarrow\ |S|\le\frac{n}{2}\ \Rightarrow\ |S|\le\frac{n-1}{2}[/tex]
Dakle, iz svakog takvog društva mora da ode bar [tex]n-\frac{n-1}{2}=\frac{n+1}{2}[/tex] osoba.
Primer u kome je to dovoljno: [tex]n[/tex] osoba sedi za okruglim stolom i svaka poznaje sve osim svoja dva suseda za stolom. Svako ima [tex]n-3[/tex] poznanika i postoje osobe koje se ne poznaju. Osobe na mestima [tex]1,3,5,\ldots,n-2[/tex] (to je [tex]\frac{n-1}{2}[/tex] osoba, od kojih nikoje dve nisu susedi) međusobno se poznaju, pa je dovoljno da ode ostalih [tex]\frac{n+1}{2}[/tex] osoba. Dakle,
[tex]k=\frac{n+1}{2}[/tex]