\title{Tema 2}
\author{
	Boca Ioan-Bogdan -- A7 \\
	Danila Marius Cristian -- A7 \\
}

\documentclass[12pt]{article}
\usepackage{cancel}
\usepackage{tikz}
\usetikzlibrary{arrows}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage[linesnumbered,ruled]{algorithm}
\usepackage{algpseudocode}


\begin{document}
\maketitle


\paragraph{Prolema 1}

Fie $D = (V, E)$ si $a : E \rightarrow R$. D nu are circuit de cost total negativ $=> \exists$ o functie $ \pi : V \rightarrow R$ astfel incat $a(uv) + \pi (v ) \geq 0 \forall u, v \in E$

"$<=$"

Fie $v_1, v_2, ... v_k, v_1$ un circuit oarecare din $G$. Presupunem ca $\exists \pi : V \rightarrow R$ astfel incat $a(uv) + \pi (v ) \geq 0 \forall u, v \in E$.

Vom demonstra ca costul total al circuitului este pozitiv

$$ a(v_1 v_2) +  \pi(v_1) \pi(v_2) \geq 0$$
$$ a(v_1 v_2) \geq \cancel{\pi(v_1)} - \cancel{\pi(v_2)} $$
$$ a(v_2 v_3) \geq \cancel{\pi(v_3)} - \cancel{\pi(v_2)} $$
$$ \vdots \vdots \vdots  $$
$$ a(v_{k-1} v_{k}) \geq \cancel{\pi(v_k)} - \cancel{\pi(v_{k - 1})} $$
$$ a(v_k, v_1) \geq \cancel{\pi(v_1)} - \cancel{\pi(v_k)} $$

{
\center
\noindent\rule{8cm}{0.4pt} $(+)$

$$\underbrace{a(...) + a(...) + ... \geq 0}$$

costul total al nodurilor

}


"$=>$" Presupunem ca orice circuit are cost pozitiv. Aratam ca exista o functie $\pi$. Fixam $p_0 \in G$ si definim functia $\pi$

$$ \pi(p_0) = 0$$
$$ \pi(p_i) = min_{j \neq i} (\pi(p_j) + a(p_i p_j)) $$


\paragraph{Problema 2}

Fie $G\ =\ (V,\ E)$ un graf conex si $v_0 \in V$ un punct de articulatie al sau.


Presupunem ca $G$ admite cuplaj perfect $\Rightarrow $ $|V|$ este numar par. $(|V| = 2n)$
Fie $H$ graful obtinut prin scoaterea lui $v_0$ din $G$. $\Rightarrow$ numarul de noduri ale lui $H$ este impar. Prin scoaterea lui $v_0$ din $G$ graful devine neconex $\Rightarrow$ $H$ este format din
$C_1$, $C_2$, ... $C_m$ componente conexe. $\Rightarrow |C_1|\ +\ |C_2|\ +\ ... \ +\ |C_m|\ =\ 2n\ -\ 1$.


Presupunem ca avem cel putin $2$ componente conexe ce au numar impar de noduri. Fie $C_i,\ C_j\ cu\ i \neq j\ 2$ componente cu numar impar de noduri.
Datorita faptului ca $C_i$ are numar impar de noduri, prin formarea cuplajului perfect va ramane un nod $v_i$ fara pereche $\Rightarrow$ $v_iv_0$ formeaza o muchie.

In $C_j$ situatia este similara. Va ramane un nod $v_j$ fara pereche $\Rightarrow\ v_iv_0$ formeaza o muchie.

Fie $L$ cuplajul perfect al grafului. $L\ =\ \{.....(v_i,\ v_0),\ (v_j,\ v_0)\ .....\}$. $v_0$ apare de 2 ori in multimea $L\ \Rightarrow L$ nu este cuplaj perfect. Contradictie. $\Rightarrow$ nu avem $2$ componente conexe ce au numar impar de noduri.

Acceasi justificare este valabila si in cazul unei singure componente conexe cu numar impar de noduri.

Daca avem o singura componenta conexa cu numar impar de noduri, atunci prin eliminarea lui $v_0$ obtinem tot un graf conex. $(Contradictie\ cu\ ipoteza)$.
$\Rightarrow$ vom avea o componenta conexa cu numar par de noduri.
$G$ conex $\Rightarrow \ \exists$ cel putin o muchie de la $v_0$ la una dintre componentele conexe cu numar impar de noduri.

Fie $c_i$ un nod apartinand unei componente conexe cu numar par de noduri. Fie $e_0\ =\ (v_0,\ c_i)$ o muchie. Cum $v_0$ apare in lista cuplajului perfect $\Rightarrow$ $c_i$ nu va aparea in lista cuplajului perfect.

Am demonstrat ca $\exists$ o muchie $e_0$ $\in\ G$ incidenta cu $v_0$ cu proprietatea ca $e_0$ nu apartine la un cuplaj perfect al lui $G$.


\paragraph{Problema 3}

a)

Multimea $T: $ fiecare nod este unit cu cel mai apropiat vecin al sau.

$$ A(v_1) \rightarrow P_1 $$
$$ A(v_2) \rightarrow P_2 $$
$$ \vdots $$
$$ A(v_n) \rightarrow P_n $$

Multimea returnata de functie este multimea nodurilor de forma $(v_i, p_i)$ cu $p_i$, $A(v_i)$ catul muchiilor $v_i p_i$ este costul minim al unei muchii dintre $v_i$ si un nod din lista de adiacenta $A(v_i)$

Fie $C_1, C_2, ..., C_p$ cele $p$ componene conexe ale grafului $G=(V, T)$

$$ |C_1| + |C_1| + ... + |C_p| = m$$

Cum fiecare varf $v \in V$ este unit cu siguranta de un vecin al sau $w$, gradul fiecarui nod din graful $G'$ este $\geq 1$

Fie $C$ comp conexa are cel putin 2 noduri
$$ |C_i| \geq 2 => |C_1| + |C_2| + ... + |C_p| = m \geq$$
$$ \underbrace{2 + 2 + ... + 2}  \leq m$$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  de\ p\ ori$

$=>$ Avem cel mult $\frac{n}{2}$ componente conexe.

Presupunem ca avem un circuit $v_1, ..., v_k$. Notam cu $w$ costul muchiilor $v_i v_{i+1}$. Presupunem ca $v_2$ este cel mai apropiat vecin de $v_1$, $v_3$ cel mai apropiat vecin de $v_2$.... $v_1$ cel mai apropiat vecin de $v_k$. Pentru a avea aceasta configuratie avem nevoie ca $a_k < a_{k-1} < ... < a_1$. Daca nu se repeta $a_i < a_{i-1}$ atunci $v_1$ nu ar mai fi cel mai apropiat vecin de $v_{i-1}$

Ajungand inapoi in varful $v_1$ trebuie sa avem $a_1 < a_k$. Altfel cel mai apropiat vecin de $v_1$ ar fi fost $v_k$ si nu $v_2$. Avem

$$ a_k < a_{k-1} < ... < a_p $$

Inegalitate, deoarce functia de cost $c$ este strict injectiva.

b)

\begin{algorithm}
\caption{Algoritm exercitiul 3}\label{euclid}
\begin{algorithmic}[1]

\For {i = 1; i < p; i++}
\For {j = i + 1; $j \in p$; ++j}
\For {each $v \in C_i$}
\State {x = $A(v) \cap C_j$}
\State {E(H) = E(H) $\cup$ \{multimea muchiilor $vx$ cu $x\in X$\}}
\If {$c(x_i)$ < min}
\State {min = $c(v_i)$}
\EndIf
\EndFor
\EndFor
\EndFor
\end{algorithmic}
\end{algorithm}


Parcurgem toate listele de adiacenta $\rightarrow$ parcurgerea tuturor nodurilot din graf $\rightarrow$ parcurgerea fiecarei liste de adiacenta $\rightarrow O(m + n)$

Este pentru aflarea muchiei de cost minim intre oricare 2 componente $\rightarrow$ parcurgem listele de adiacenta (Costul unei muchii se afla in  O(1)) $\rightarrow$ O(n)

c)

$e_\overline{ij}$ = \{ costul minim al unei muchii intre $c_i$ si $c_j$\}

$A'$ - arbore partial de cost minim in $H$

$T \cup \overline{A'}$ - arbore partial de cost minim in G

Presupunem ca pentru un graf cu functie de cost injectiva ar exista 2 arbori partiali de cost minim.
Fie $T$ si $T'$ cei 2 arbori.

$L1={c(e_1) < c(e_2) < .... < c(e_k)}$ - lista sortata a costurilor muchiilor din arborele $T$

$L2={c(e'_1 < c(e'_2) < .... < c(e'_k)}$ - lista sortata a costurilor muchiilor din arborele $T'$

Fie $t$ prima pozitie in care $L1$ si $L2$ sunt diferite. $(c(e_t) \neq c(e'_t) )$

Presupunem ca $c(e_t) < c(e'_t)$

Fie $R=T'\cup\{e_t\}$ . $T'$ este arbore, iar daca mai adaugam o muchie se va forma un circuit. Notam cu $C$ circuitul respectiv.

Fie $S = C - E(T)$. Costul muchiilor din $S$ este mai mare decat $c(e_t)$. Deci eliminand una din muchiile din $S$ in $H$ obtinem un arbore partial de cost minim mai mic decat $T'$. Contradictie cu ipoteza.

Presupunem ca arborele sugerat la punctul $c)$ nu ar fi arbore partial de cost minim in $G$.

Fie $A'$ arborele partial de cost minim in $H$ si $A''$ arborele partial de cost minim in $G$.

Presupunem ca $A' \neq A''$.

- cost$(A')<$cost$(A'')$ $\Rightarrow$ avem in G un arbore partial de cost minim ce are un cost mai mare decat costul unui arbore partial de cost minim dintr-un subgraf de-al sau. $(Fals)$

- cost$(A'')<$cost$(A')$ $(Fals)$ deoarece la fiecare pas din constructia grafului $H$ am ales muchii de cost minim intre un varf si vecinii sai.

Deci costurile celor 2 arbori nu pot fi decat egale, iar prin faptul ca arborele partial de cost minim din $G$ este unic $\Rightarrow$ cerinta).



d)

\begin{algorithm}
\caption{Algoritm exercitiul 3. d)}\label{euclid}
\begin{algorithmic}[1]

$T=B(V,C)$;

$G'=(V,T)$;

getConnexComponentsOf$(G')$;

$H$=b)function;

Prim'sAlgorithm$(H)$


\end{algorithmic}
\end{algorithm}


Complexitatea algoritmului este $O(n^2)$ - datorata apelului la algoritmul lui Prim.

\paragraph{Problema 4}

Fie $G\ =\ (S,\ T;\ E)$ un graf bipartit fara varfuri izolate.
Aratam ca daca pentru fiecare muchie $e\ \in\ E,\ e\ =\ st\ (s\ \in S,t\ \in T)$ are loc inegalitatea
$d_G(s)\ \geq\ d_G(t)$ avem ca $|N_G(X)|\ \geq |x|
\ \forall X \subseteq S$.

Notam cu $n$ numarul de muchii ale subgrafului indus de $X$ in $G$.
Observam ca $n\ =\ \sum_{S\ \in X} d_G(S)$ $=$ $\sum_{t\ \in N_G(X)} d_G(t)$.
$\Rightarrow |N_G(X)|\ \geq \ |X|\ \forall X \subseteq S\ (*)$

Demonstram ca orice graf bipartit care satisface relatia $(*)$ are un cuplaj ce satureaza toate varfurile lui $S$.

Vrem sa aratam ca $\Gamma(_G)$(numarul maxim de muchii independente) $\ =\ |S|$.

Numarul minim de puncte necesare pentru a reprezenta toate muchiile din $G\ \leq |S|$ deoarece orice muchie are o extremitate in multimea $S$. $\Rightarrow\ |\Gamma(G)|$(numarul minim de puncte pentru a reprezenta muchiile lui $G$) $\leq\ |S|$.

Este suficient sa aratam ca orice multime $A$ ce acopera toate muchiile din $G$ are cel putin $|S|$ elemente.

Din Teorema lui Hall $\Rightarrow$ $\gamma(G)\ =\ \Gamma(G)$

$|\Gamma(G)| \leq |S|$

$\ \ \ \ \ \ \ \ \ \geq |S|$ $\Rightarrow$ $|\Gamma(G)| = |S|$ $(**)$


Vom arata ca relatia $N_G(S - A) \leq A \cap T$.

Fie $x$ un nod oarecare, $x\ \in\ S-A$, care are corespondent pe $y$, $y \in T$. Pentru ca muchia $xy$ sa fie acoperita de multimea $A$ trebuie sa avem ca $y\in A$ $\Rightarrow \ y \in A \cap T$.

$|A|=|A\cap S|+|A \cap T| \geq |A\cap S|+|N_G(S-A)|$

$|N_G(S-A)| \geq |S-A| \geq |A\cap S|+|S-A| = |S|$ $\Rightarrow$ orice multime care acopera toate elementele lui $G$ are $|S|$ elemente.

Pentru a avea un cuplaj ce satureaza toate elementele din $|S|$ trebui sa avem ca $\Gamma(G)=|S|$
$\Rightarrow$ am aratat relatia $(**)$.


\end{document}