\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{listings}
\usepackage{multirow}
\usepackage{multicol}
\title{Algoritmica Grafurilor. Tema 2}
\author{Ruben-Andrei Simion 2B4, Robert-Stefan Milea 2B4}
\date{November 2019}

\begin{document}

\maketitle

\section{Problema 1}
\subsection{a) Adevarat}

Consideram un graf conex G = (V,E) care contine mai multe muchii de cost minim in graf. Aplicam algoritmul lui Kruskal pentru acest graf, un prim pas fiind sortarea muchiile dupa cost.
Ideea algoritmului lui Kruskal este sa genereze multimi disjuncte de noduri, unite prin muchii de cost minim, si unirea acestora pentru formarea unui arbore partial de cost minim.

Parcurgem muchiile sortate, dar luam in considerare doar muchiile de cost minim(continuarea algoritmului nu face parte din subiectul problemei). Pentru fiecare muchie (x,y) exista 2 cazuri:
\newline
1. x si y apartin unor multimi disjuncte diferite, acestea putand fi unite prin muchia (x,y), formand o singura multime disjuncta ce contine nodurile celor 2 multimi anterioare.
2. x si y apartin unei aceleasi multimi disjuncte, prin urmare introducerea muchiei (x,y) ar crea un ciclu. Insa, noi stiind ca aceasta muchie este de cost minim, o putem plasa ca fiind prima in vectorul muchii, astfel asigurandu-ne ca algoritmul va selecta aceasta muchie in vederea crearii unui arbore partial de cost minim(orice nod este initial o multime disjuncta) si va alege sa nu selecteze o alta muchie din acelasi ciclu.

Altfel spus, muchia noastra fiind de cost minim, plasarea ei pe prima pozitie intre cele de cost minim in vectorul de muchii va garanta faptul ca aceasta este selectata de algorimul lui Kruskal $\Rightarrow$ $\forall$ v $\in$ E(G), c(v) este minim $\rightarrow$ $\exists$ T* astfel incat v $\in$ T*(T* este un arbore partial de cost minim pentru graful G)

\subsection{b) Fals}
In desenul de mai jos, nicio muchie din ciclul 1-2-3-4-1 nu apartine arborelui partial de cost minim al grafului G.
\subsection{c) Adevarat}

Consideram din nou algoritmul lui Kruskal pe algoritmul G = (V,E). Aplicam algoritmul pana in punctul in care decidem daca muchia v = (x,y) $\in$ V(G). Daca muchia este selectata, putem deduce faptul ca G' = (E(G) + \{y\},V(T)) nu este conex, nodul y nefiind conectat cu restul nodurilor din G'(notam cu T arborele partial pentru nodurile din G'). Astfel, daca consideram taietura ca fiind toate muchiile din vectorul sortat de muchii, incepand cu muchia v inclusiv, v este muchia de cost minim in acea taietura si graful rezultat nu este conex, nodul y nefiind conectat cu restul nodurilor $\Rightarrow$ $\forall$ v = (x,y) astfel incat v $\in$ T* $\rightarrow$ $\exists$ o taietura astfel incat v este muchie de cost minim in acea taietura(notam cu T* un arbore partial de cost minim pentru graful G).

\section{Problema 2}
\subsection{a)}
Consideram ca T* a fost generat cu algoritmul lui Kruskal si H un subgraf conex c-extensibil al lui G.\newline
T*H = (V(H), E(H) $\cap$ E(T*)) arbore partial in H\newline
Presupunem ca T*H nu este arbore partial de cost minim pentru H.\newline T*H fiind arbore si T*H provine din arborele partial de cost minim al grafului $\rightarrow$ $\exists$ un singur nod x astfel incat (x, y) $\in$ T*, y $\in$ G-H. Daca T*H nu este arbore partial de cost minim $\rightarrow$ $\exists$ T'H astfel incat Cost(T'H) $<$ Cost(T*H) $\rightarrow$ $\exists$ T' astfel incat Cost(T') $<$ Cost(T*) (cei 2 arbori sunt identici in rest, diferenta fiind in multimea elementelor lui H) $\rightarrow$ T* nu este arbore partial de cost minim(contradictie) $\Rightarrow$ T*H este arbore partial de cost minim in H.

\subsection{b)}

Consideram graful GH.
Graful GH va fi format din toate nodurile care nu sunt din H, toate muchiile (x, y), x, y $\in$ G-H, nodul xH ce reprezinta componenta conexa H, si muchiile (x, xH), x $\in$ G-H, $\exists$ y astfel incat (x, y), y $\in$ H, si Cost(x, xH) = Cost(x, y). Imaginea urmatoare poate reprezenta transformarea.
\newline

\newline
Astfel, daca consideram transformarea ca fiind un pas din algoritmul lui Prim(H este arborele ce se creaza in orice pas al algoritmului lui Prim), putem considera nodul xH ca fiind o componenta conexa rezultata in urma a n pasi de algoritm. Astfel, se va crea un arbore partial de cost minim intre toate nodurile din G-H si nodul xH. Pentru a reconstrui arborele, trebuie sa gasim muchia cu prop ca (xH, y) $\in$ T*, x $\in$ H, Cost(xH, y) = Cost(x, y). Astfel, pentru a reconstrui Arborele Partial de Cost Minim trebuie sa unim arborele partial de cost minim H, arborele partial de cost minim din GH, si muchia mentionata mai sus.

Astfel, considerand ca H este rezultatul algoritmului lui Prim la pasul k, unde k $=$ $\|E(H)\|-1$, constructia arborelui partial de cost minim este T(G-H+xH), iar unirea lor se face prin T*H $\cup$ T*GH $\cup$ (x, y), x$\in$G-H, y $\in$ H, Cost(x, y) = Cost(xH, y).

\section{Problema 3}
\subsection{a) (i) $\rightarrow$ (ii)}

Consideram G astfel incat G este nenul si G-\{x, y\} are un cuplaj perfect, $\forall$ x $\in$ S, $\forall$ y $\in$ T $\Rightarrow$ (restrangem aceasta afirmatie la nodurile cu muchii intre ele) $\Rightarrow$ G-\{x, y\} are un cuplaj perfect, $\forall$ x $\in$ S, $\forall$ y $\in$ T, (x, y) $\in$ V(G)(notam acest cuplaj cu C) $\Rightarrow$ C + (x, y) este un cuplaj perfect pentru graful G $\Rightarrow$ $\forall$ (x, y) $\in$ V(G), (x, y) apartine unui cuplaj perfect. (*)
\newline
Presupunem ca G nu este conex $\rightarrow$ G este format din minim 2 componente conexe. Consideram o din aceste componenta conexa, X $\cup$ Y, X $\in$ S si Y $\in$ T, existand muchii intre ele. Fiindca exista un cuplaj perfect intre ele $\rightarrow$ $\|X\|$ = $\|Y\|$. Alegand un element din x din X si un element y din T-Y, ar trebui sa se pastreze cuplajul perfect. Insa $\|X-\{x\}\|$ != $\|Y\|$ $\rightarrow$ nu se poate forma un cuplaj perfect $\rightarrow$ contradictie. $\Rightarrow$ G este conex. (**)

\newline

Din (*) si (**) $\Rightarrow$ (i) $\rightarrow$ (ii).

\subsection{b) (ii) $\rightarrow$ (iii)}

G este conex si orice muchie apartine unui cuplaj perfect $\rightarrow$ G are un cuplaj perfect(maximal) si $\|S\|$ = $\|T\|$ $\rightarrow$ Prin terorema lui Hall $\rightarrow$ $\|NG(A)\|$ $>=$ $\|A\|$, $\forall$ $\emptyset$ $\ne$ A $\subset$ S. \newline
Presupunem $\|NG(A)\|$ $=$ $\|A\|$ si notam NG(A) cu Y. Stiind ca graful este conex si NG(A) = Y $\rightarrow$ $\exists$ y $\in$ Y astfel incat (y, x) $\in$ V(G), x $\in$ S-A. Alegem muchia (x, y) si stim ca aceasta trebuie sa apartina unui cuplaj perfect din (ii) $\rightarrow$ A trebuie sa formeze un cuplaj perfect cu Y-\{y\}, dar $\|Y-\{y\}\|$ $!=$ $\|A\|$ $\rightarrow$ contradictie $\rightarrow$ $\|NG(A)\|$ $!=$ $\|A\|$ $\Rightarrow$ $\|NG(A)\|$ $>$ $\|A\|$. (*)
\newline
Fiind conex, graful nu este nul. (**)

\newline

Din (*) si (**) $\Rightarrow$ (ii) $\rightarrow$ (iii).
\subsection{c) (iii) $\rightarrow$ (i)}

Consideram A = S - \{x\}, $\forall$ x $\in$ S. $\|NG(A)\|$ $>$ $\|A\|$ $\rightarrow$ NG(A) = T. Consideram y $\in$ T si G' = (S - \{x\}, T-\{y\},E')$\rightarrow$ NG'(A) = T - \{y\} $\rightarrow$ $\|NG'(A)\|$ $>=$ $\|A\|$ $\Rightarrow$ Prin teorema lui Hall $\Rightarrow$ G' are un cuplaj maximal(deci perfect). Dar G' = G - \{x, y\}, $\forall$ x $\in$ S, $\forall$ y $\in$ T $\Rightarrow$ G - \{x, y\} are un cuplaj perfect, $\forall$ x $\in$ S, $\forall$ y $\in$ T(*).
\newline
Deoarece $\|NG(A)\|$ $>$ $\|A\|$ $\rightarrow$ G are macar 3 noduri, deci G nu este nul. (**)
Din (*) si (**) $\Rightarrow$ (iii) $\rightarrow$ (i)


\section{Problema 4}

\subsection{a)}
Consideram urmatoarele notatii $\:$\newline
K = $\|C\|$ ;
X = $\|M1\|$;
Y = $\|M2\|$; \newline
Consideream suma initiala OldSum  = $\Sigma a(muchie)^2 , muchie \in E^+ $ \newline
Fie: InitM1$=\Sigma a(muchie) ^ 2, muchie \in M1 $ ,
InitM2$=\Sigma a(muchie) ^ 2, muchie \in M2 $ ,
InitRest $=\Sigma a(muchie) ^ 2, muchie \in \{E^+ -C\}$\newline
OldSum=InitM1+InitM2+InitRest\newline
Fie NouM1 $=\Sigma ( a(muchie)+1) ^ 2 = InitM1 + \Sigma2*a(muchie) + X, muchie \in M1 $ \newline
NouM2 $=\Sigma (a(muchie)-1) ^ 2 = InitM2 - \Sigma2*a(muchie) + Y, muchie \in M2 $\newline
InitRest $=\Sigma a(muchie) ^ 2, muchie\in \{E^+ -C\} .\newline

  NewSum $=InitRest+NouM1+NouM2 = OldSum + 2*(a(M1)-a(M2) +K$\newline
  Din Algorimt stim ca  $a(M1)\geq a(M2)$ $\Rightarrow$ $NewSum \geq OldSum+K$
  \subsection{b)}
  Notatii:
$sumaB(v) = \Sigma a(muchie)$,muchie incidenta cu v si muchie $\in E^+$\newline

  Initial G-graf p-regulat $\Rightarrow$ $\forall v \in V $ sumaB(v) = p .
  Presupunem ca dupa K pasi proprietea este adevarata. sumB(v) = p\newline
  Cazul I:
$v \in C \Rightarrow \exists $ m1,m2 incidente in v unde $m1 \in M1$ si $ m2 \in M2$. $a(m1)'=a(m1)+1 , a(m2)'=a(m2)-1$\newline
  sumaB(v)= $\Sigma a(n) + a(m2)' +a(m1)'$ = $\Sigma a(n) + a(m2)+1 +a(m1)-1 =p, n \notin C$,=  si n incident cu v $\Rightarrow$ suma nu se schimba de la pasul K la pasul K+1 \newline
  Cazul II: $v \notin C \Rightarrow$ sumB nu sufera modificari \newline
  Din I, II $\Rightarrow$ pentru $\forall v \in V$ sumB(v)=p

\subsection{c)}
Prin contradictie :presupun $v \in V$ si m muchie incidenta in v si $a(m) > p$ $\Rightarrow$ $sumB(v) > p$ $\Rightarrow$ contrazice punctul b deci a(m)$\leq$ p.\newline
Fiind graf bipartit $\|C\|$ este multiplu de 2. d(V) $>$ 2 $\Rightarrow$ V $\exists v \in C$
Algoritmul se opreste cand nu mai gaseste cicluri $\Rightarrow$
toate nodurile au gradul 1. Prin eliminari multiple ramane o singura muchie m , a(m) = p si v nu mai apare in nici un ciclu.
Fie v $\in V \exists w $ astfel incat $vw \in E^+$  atunci w este unic . ( prin reducere la absurd daca am avea alt nod si o alta muchie m' $\Rightarrow$ sumaB(v) = p + a[m'] $\neq$ p) in final $\Rightarrow$ pentru orice v aprtine lui V $\exists$ v' $\in$ V , vv' $\in$ $E^+ \Rightarrow E^+$ contine un cuplaj.
\subsection{d)}
Fie x $\in M2$ astfel incat $\forall$ x' $\in M2$ a[x] $<$a[x'].
\subsection{e)}

\subsection{f)}

\end{document}