1. \documentclass{article}
2. \usepackage[utf8]{inputenc}
3. \usepackage{algorithm}
4. \usepackage{amsmath}
5. \usepackage{algorithmic}
6. \usepackage{algpseudocode}
7. \usepackage{graphicx}
8. \title{\[Tema_{1}\]}
9. \author{Burcă Rafael, Petrariu Florin-Iustinian, IIB3 }
10. \date{30 Octombrie 2020}
11.  
12.  
13. \begin{document}
14.  
15. \maketitle
16. \section{Problema 1.}
17.  
18. \begin{algorithm}
19. \caption{Verifica posibilitatea partitionarii lui G in k partitii disjuncte}
20.  \Function{main}{$ $}
21.     \State INPUT: N,K,M // numărul de noduri, numărul k și numărul de muchii
22.         \State ${componente} = 0$
23.         \For{$nod \gets 1$ to $V-1$, $nod++$ }
24.           \State viz[i]=0;
25.          \EndFor
26. \For{$nod \gets 1$ to $V-1$, $nod++$ }  
27.   \If{$viz[i]=0$}
28.   \State componente++
29.    \State DFS(i)) // aplicam algorimul DFS prezentat la curs
30.    \EndIf  // si vom marca în viz nodurile vizitate, similar în curs cu label(i)
31. \EndFor
32.  \If{$componente <= k <= |V|$}
33.    \State return "DA"
34.    \Else
35.       \State return "NU"
36.  
37.     \EndFunction
38. \end{algorithm}
39.  
40.     În cadrul acestui exercițiu vom implementa un algoritm DFS(Depth First Search) care se bazează pe următorul raționament: parcurgerea DFS va determina numărul de componente conexe ale grafului G din instanța problemei, iar asupra acestui număr și în funcție de ordinul grafului, $ |V(G)|$ vom decide dacă există o partiție de cardinal k, $V_{1},V_{2},...V_{k}$ astfel încât fiecare partiție să inducă un subgraf conex .Așadar am considerat un vector de vizitare \emph{viz[]} pentru a putea vedea nodurile vizitate. De asemenea pentru a ne asigura că vom parcurge fiecare nod cu DFS vom itera prin toate nodurile, iar atunci cand vom găsi un nod nevizitat vom crește variabila de componente conexe. Din noțiunile predate la curs cunoaștem complexitatea algoritmului DFS(s), unde s este nodul de start, ca fiind $\mathcal{O}(n_{s} + m_{s})$ unde $n_{s}= |S| <= |V| = n$ și $m_{s}= |E([S]_{G})| <= |E|$, iar S reprezintă mulțimea de noduri accesibile din nodul s. Cum vom aplica acest algoritm pentru fiecare nod al grafului G, complexitatea va rămâne $\mathcal{O}(|V|+|E|)$, întrucat dacă avem mai multe componente conexe, fie acest numar p,  va trebui să adunăm $DFS(s_{1})+DFS(s_{2})+...DFS(s_{p}) =\mathcal{O}(n_{s1}+m_{s1})+...+O(n_{sp},m_{sp})$  pentru care putem considera ca este in $p*O(max(n_{s1},n_{s2}\dots n_{sp}), max(m_{s1},m_{s2} \dots m_{sp})) $ care aparține $\mathcal{O}(|V|+|E|)$
41.     Codul descris în pseudo-cod calculează numărul de componente conexe. Dacă numarul de componente conexe este mai mic decât numărul k în care dorim sa partiționăm G si daca numărul k este mai mic sau egal cu numărul de noduri ale grafului atunci stim ca exista o partiție de cardinal k al grafului G, în caz contrar, nu există.
42.  
43. \section{Problema 2.}
44.     \subsection{a)}
45.      Diametrul unui graf G reprezintă cea mai mare distanță dintre minimele distanțelor oricăror 2 noduri din graful G. \[   d(G)=max_{u,v \in V} d_{G}(u,v)   \]
46.      Două noduri formează o pereche diametrală dacă distanța dintre ele este cât diametrul.
47.      
48.      
49.     Conform enunțului, știm că oricare doi utilizatori au o cunoștință comună. Asta înseamnă că dacă vom considera  $\forall u,v \in V(G) $ , va exista un nod \emph{w} astfel incat  $ uw, vw \in E(G) $. Așadar, obținem că între oricare două noduri vom avea un nod de legatură și în acest fel distanța minimă între oricare două noduri va fi cel mult 2, întrucât $d_{G}(u,v)=d_{G}(u,w)+d_{G}(w,u)=1+1=2 $ sau $d_{G}(u,v) =1 $ dacă cele două noduri sunt adiacente. În acest fel, diametrul în graful G va fi maximul acestor distanțe, dintre oricare două noduri, a cărui lungime nu va fi mai mare decât 2.
50.    
51.    
52.     Presupunem prin reducere la absurd că diametrul în G este mai mare decât 2. Astfel, rezultă ca ar exista doua noduri, \emph{u} si \emph{v} $\in V(G)$ astfel încat $d_{G}(u,v) > 2 $. Însa în acest fel contrazicem faptul că u si v ar avea un prieten comun. Pentru că daca ar avea un prieten în comun, fie \emph{w} acel prieten, atunci distanța dintre cele două noduri va trebuie sa fie 1, daca cele doua sunt adiacente și 2 in caz contrar întrucât mergem prin vecinul comun și obținem distanța maximă 2.
53.      
54.      Graful rezultat care respectă condițiile din enunț nu poate avea circuite de lungime 4, singurele circuite sunt cele de lungime 3. Dacă presupunem, prin reducere la absurd, că ar exista în G un circuit de lungime 4, fie acesta (c1,c2,c3,c4), cu $c1,c2,c3,c4 \in V(G) $ atunci nodurile c1,c3 si c2,c4 (aflate la disanța 2 unele de celelalte) nu respectă proprietatea de a avea o singură cunoștintă comuna. Astfel, nodurile vor avea două cunoștinte comune, pentru c1 si c3 avem nodurile c2 si c4 ca si cunoștințe comune, iar pentru c2 si c4 avem nodurile c1 si c3 ca și cunoștine comune, ceea ce contrazice cu restricția problemei de a avea între oricare două noduri o singură cunoștință (un singur vecin comun). Așadar am ajuns la o contradicție, iar graful nu poate avea circuite de lungime 4 ( sau orice circuit mai mare de lungimea 3).
55.    
56.  \subsection{b)}
57.      O submulțime de \emph{k} noduri a unui graf G care induce un graf complet este numită o k-clică.
58.    Conform demonstrațiilor de la subpunctul a), graful obținut nu poate avea circuite de lungime 4, așadar circuitul de cardinal maxim care se poate forma si care păstrează proprietatea grafului este alcătuit din 3 noduri, care reprezintă o 3-clica, acesta fiind si graful minimal pe care îl putem desena cu 3 noduri și care respectă condițiile din enunț. Pentru a adăuga mai multe noduri grafului vom proceda în felul următor: Pentru a păstra proprietatea de a avea diametrul 2 este nevoie ca toate nodurile să fie conectate printr-un singur nod comun tuturor celorlalte noduri. Însa, pentru a exista un nod comun pentru toate celelalte n-1 noduri este necesar să mai adăugăm muchii între acest nod la toate cele  n-1 noduri, iar acum nodul comun  are deja un numar maxim de muchii(n-1). Pentru a păstra toate proprietătile grafului, observăm ca între un nod oarecare si nodul comun pentru toate nodurile nu exista un vecin comun. Astfel, trebuie să mai adaugam  muchii între celelalte n-1 noduri astfel încat să nu formam circuite de lungime 4 ( conform subpunctului a) ). În acest fel, vom adăuga muchii pentru cele n-1 noduri din două în două noduri pentru a evita formarea unui circuit de lungime 4, obținând în acest fel circuite de lungime 3 care formează, impreuna cu nodul comun tuturor celorlalte noduri o 3-clică. Așadar, obținem n-1 muchii de la nodul comun la care se adaugă muchiile din două în două noduri din cele n-1 noduri și obținem (n-1)/2 muchii pe care trebuie sa le adaugam. În final, avem $(n-1)+(n-1)/2 = 3*(n-1)/2 $ muchii in graful rezultat. Astfel numărul de muchii ale subrafului [ $ v \cup N_{G}(v)]_{G}$ este $3*D_{G}(v)/2 = 3*(n-1)/2$ atunci cand v este chiar nodul comun pentru toate nodurile. Când \emph{v} nu este nodul comun, \emph{v} face parte dintr-o 3-clică si obținem că numărul de muchii ale subrafului [ $ v \cup N_{G}(v)]_{G}$ este $3*D_{G}(v)/2 = 3*2/2 = 3$ care este exact 3-clica.
59.    
60.  
61. \subsection{c)}
62.   Conform subpunctului b), fiecare nod împreună cu vecinul său formează o 3-clică. Așadar, pentru a considera oricare două noduri ne-adiacente, va trebui să facem abstracție de nodul comun care este adiacent cu toate nodurile din graf. Astfel, oricare două noduri le vom considera, care să nu fie adiacente, vor aparține unei 3-clici și astfel vor avea acelasi număr de vecini.
63.  
64.  
65.  
66. \end{document}