\documentclass[a4paper]{article}
\usepackage[margin=1in]{geometry}
\usepackage[utf8]{inputenc}

\usepackage{tikz}
\usepackage{tikz-qtree}
\usepackage{amsmath}
\usepackage{color}

\title{Algoritmica Grafurilor - Tema 1}
\author{Ciocoiu Razvan$^{[1]}$, Olariu Leonard$^{[2]}$ - grupa A5}
\date{\today}

\begin{document}

\maketitle

\section{}

\section{}

\section{Problema III}
\subsection{(a)}
In demonstratia noastra ne vom baza pe urmatoarea proprietate: $abs(|M_T - C_v|) = abs(|M_{T'} - C_v|)$, unde T' este un izomorfism al arborelui T, iar $C_v$ este coloana corespunzatoare nodului pe care dorim sa-l eliminam. Aceasta egalitate este garantata prin maniera de obtinere a lui T', anume redenumiri de noduri si muchii, care la nivelul matricii de incidenta muchie-nod s-ar traduce prin combinatii liniare de linii si coloane. \\

Astfel, pentru a demonstra ca $M_T$ nesingulara, este suficient sa aratam ca $M_{T'}$ nesingulara. Pentru a obtine o forma convenabila a matricii $M_{T'}$, vom seta nodul a carei coloana dorim sa o eliminam drept radacina si vom desfasura arborele T' in functie de acesta, urmand ca printr-o parcurgere BFS sa redenumim nodurile si muchiile dupa modelul: \\

\begin{minipage}{.3\textwidth}
\begin{tikzpicture}[every node/.style = {circle, draw = black}]

\node{1}
    child {node{2} edge from parent node[midway, left, draw = none] {1}}
    child {node{3} edge from parent node[near end, left, draw = none] {2}}
    child {node{4}
        child {node[red]{5}
            child {node{7} edge from parent node[midway, left, draw = none] {6}}
            child {node{8} edge from parent node[midway, right, draw = none] {7}}
        edge from parent node[midway, left, draw = none] {4}}
        child {node{6} edge from parent node[midway, right, draw = none] {5}}
    edge from parent node[midway, right, draw = none] {3}};

\end{tikzpicture}
\end{minipage}
\begin{minipage}{.3\textwidth}
\begin{tikzpicture}[every node/.style = {circle, draw = black}]

\node[red, dotted]{5}
    child {node{4}
        child {node{1}
            child {node{2} edge from parent node[midway, left, draw = none] {1}}
            child {node{3} edge from parent node[midway, right, draw = none] {2}}
        edge from parent node[midway, left, draw = none] {3}}
        child {node{6} edge from parent node[midway, right, draw = none] {5}}
    edge from parent node[midway, left, draw = none] {4}}
    child {node{7} edge from parent node[near end, left, draw = none] {6}}
    child {node{8} edge from parent node[midway, right, draw = none] {7}};

\end{tikzpicture}
\end{minipage}
\begin{minipage}{.3\textwidth}
\begin{tikzpicture}[every node/.style = {circle, draw = black}]

\node[red, dotted]{1}
    child {node{2}
        child {node{5}
            child {node{7} edge from parent node[midway, left, draw = none] {6}}
            child {node{8} edge from parent node[midway, right, draw = none] {7}}
        edge from parent node[midway, left, draw = none] {4}}
        child {node{6} edge from parent node[midway, right, draw = none] {5}}
    edge from parent node[midway, left, draw = none] {1}}
    child {node{3} edge from parent node[near end, left, draw = none] {2}}
    child {node{4} edge from parent node[midway, right, draw = none] {3}};

\end{tikzpicture}
\end{minipage}
\bigskip

Procedand astfel, garantam existenta unei singure muchii de forma $(tata(v), v)$, $\forall v \in V \setminus \{radacina\}$. Eliminand coloana 1 (coloana radacinii in $M_{T'}$, corespunzatoare nodului v in T) obtinem o matrice patratica, binara, superior triunghiulara de forma: \\

\begin{center}
\begin{bmatrix}
1 & 0 & \hdots & 0 \\
0/1 & 1 & \ddots & \vdots \\
\vdots & \ddots & \ddots & 0 \\
0/1 & \hdots & 0/1 & 1
\end{bmatrix}
\end{center}\bigskip

Determinantul unei astfel de matrici este $\prod\limits_{i=1}^{|V|-1} a_{ii}$, 1 in cazul nostru. Conform proprietatii enuntate la inceputul demonstratiei, putem concluziona ca $|M_T - C_v| = \pm 1$, deci $M_T - C_v$ este matrice patratica nesingulara. \\

\subsection{(b)}
Conform definitiei din cursul suport, prin "circuit" vom intelege "ciclu simplu" (drum inchis in care nodurile si muchiile sunt distincte, cu exceptia extremitatilor care coincid). Vom respinge alte definitii acceptate in literatura, precum "drum inchis ce permite repetari de noduri, dar nu de muchii", deoarece matricea muchie-nod asociata unui astfel de circuit nu este neaparat patratica, deci nu am putea calcula determinantul acesteia si implicit discuta singularitatea/ nesingularitatea.

\subsubsection{$\Longleftarrow$}
Fie C - ciclu simplu, $|C|$ impar si $M_C$ - matricea ($|C| X |C|$) muchie-nod asociata \\

Prin permutari de linii si coloane, operatii care nu afecteaza valoarea absoluta a determinantului, putem aduce $M_C$ la forma:

\begin{center}
$\begin{bmatrix}
\color{red}1 & 1 &  &  &  \\
 & 1 & 1 &  &  \\
 &  & \ddots & \ddots &  \\
 &  &  & 1 & 1  \\
\color{red}1 &  &  &  & 1
\end{bmatrix}$
\end{center}\bigskip

Dezvoltand dupa prima coloana, det($M'_C$) =
$(-1)^0 *
\begin{vmatrix}
 1 & 1 &  &  \\
 & \ddots & \ddots &  \\
 &  & 1 & 1  \\
 &  &  & 1
\end{vmatrix}
+ (-1)^{|C|-1} *
\begin{vmatrix}
 1 &  &  & \\
 1 & 1 &  & \\
 & \ddots & \ddots & \\
 &  & 1 & 1
\end{vmatrix}$
\bigskip

Cum $|C|$ impar, iar cele 2 matrici pentru care calculam determinantul sunt iferior, respectiv superior triunghiulare, obtinem det($M_C$) = $(-1)^{nrPerm} * 2 \neq 0$, deci putem afirma ca $M_C$ nesingulara.

\subsubsection{$\Longrightarrow$}
Fie C - ciclu simplu si $M_C$ - matricea nesingulara ($|C| X |C|$) muchie-nod asociata \\

Cum det($M_C$) $\neq 0$, iar formula de calcul al acestuia corespunde celei de la implicatia reciproca, concluzionam ca $|C|$ par ar conduce la o contradictie. Astfel, ipoteza este respectata doar pentru $|C|$ impar.

\section{}

\end{document}