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

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

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

\begin{document}

\maketitle

\section{}

\section{}

\section{}
\boldsymbol{(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.

\section{}

\end{document}