1.1 --- a/damecco.tex	Wed Nov 23 20:59:40 2016 +0100
     1.2 +++ b/damecco.tex	Wed Nov 23 21:15:26 2016 +0100
     1.3 @@ -730,25 +730,6 @@
     1.4  view of the matching procedure, this means, that always the same node
     1.5  of $G_{small}$ will be covered on the d-th level.
     1.6  \end{claim}
     1.7 -\begin{proof}
     1.8 -In order to make the search space a tree, the pairs in $\{(u,v)\in
     1.9 -P(s) : \exists \hat{u} : \hat{u}\prec u\}$ are excluded from $P(s)$.
    1.10 -\newline
    1.11 -Let $\tilde{P}(s):=P(s)\backslash \{(u,v)\in P(s) : \exists \hat{u} :
    1.12 -\hat{u}\prec u\}$
    1.13 -\newline
    1.14 -The relation $\prec$ is a total ordering, so $\exists!\ \tilde{u} :
    1.15 -\forall\ (u,v)\in \tilde{P}(s): u=\tilde u$. Since a pair form
    1.16 -$\tilde{P}(s)$ is chosen for including into $M(s)$, it is obvious,
    1.17 -that only $\tilde{u}$ can be covered in $V_{small}$. Actually,
    1.18 -$\tilde{u}$ is the smallest element in $T_{small}(s)$ (or in
    1.19 -$V_{small}\backslash M_{small}(s)$, if $T_{small}(s)$ were empty), and
    1.20 -$T_{small}(s)$ depends only on the covered nodes of $G_{small}$.
    1.21 -\newline
    1.22 -Simple induction on $d$ shows that the set of covered nodes of
    1.23 -$G_{small}$ is unique, if $d$ is given, so $\tilde{u}$ is unique if
    1.24 -$d$ is given.
    1.25 -\end{proof}
    1.26  
    1.27  \begin{definition}
    1.28  An order $(u_{\sigma(1)},u_{\sigma(2)},..,u_{\sigma(|V_{small}|)})$ of
    1.29 @@ -772,29 +753,6 @@
    1.30  (u_{\sigma{(k)}},u_{\sigma{(i)}})\in E'_{small}$, where $i,j,k,l\in
    1.31  \{1,..,|V_{small}|\}$\newline
    1.32  \end{claim}
    1.33 -\begin{proof}
    1.34 -Suppose a matching order is given. It has to be shown that the node
    1.35 -sequence has a structure described above.\\ Let
    1.36 -$G'_{small}=(V'_{small},E'_{small})$ be an arbitrary component and $i$
    1.37 -an arbitrary index.
    1.38 -\newline
    1.39 -$(\exists j : j<i\wedge u_{\sigma(j)},u_{\sigma(i)}\in
    1.40 -V'_{small})\Rightarrow u_{\sigma(i)}$ is not the first covered node in
    1.41 -$G_{small}\ \Rightarrow u_{\sigma(i)}$ is connected to a covered node
    1.42 -$u_{\sigma(k)}$ where $k<i$, since $u_{\sigma(i)}\in T_{small}(s)$ for
    1.43 -some $s$ and $T_{small}(s)\subseteq{V'_{small}}$ contains only nodes
    1.44 -connected to at least one covered node. It's easy to see, that
    1.45 -$\forall l: k\leq l\leq i \Rightarrow u_{l}\in V'_{small}$, since
    1.46 -$T_{small}(s)$ contains only nodes connected to some covered ones,
    1.47 -while it is not empty, but if it were empty, then $u_{\sigma(k)}$ and
    1.48 -$u_{\sigma(i)}$ were not in the same component.
    1.49 -
    1.50 -Now, let us show that if a node sequence has the special structure
    1.51 -described above, it has to be matching
    1.52 -order.\\ $(u_{\sigma(1)},u_{\sigma(2)},..,u_{\sigma(|V_{small}|)})$ is
    1.53 -a total ordering, which determines the matching order
    1.54 -$(u_{\sigma(1)},u_{\sigma(2)},..,u_{\sigma(|V_{small}|)})$.
    1.55 -\end{proof}
    1.56  
    1.57  To summing up, a total ordering always uniquely determines a matching
    1.58  order, and every matching order can be determined by a total ordering,
    1.59 @@ -964,32 +922,6 @@
    1.60  \begin{claim}
    1.61  \[LabCut_{IND}((u,v),M(s))\!:=\!\!\!\!\!\bigvee_{l\ is\ label}\!\!\!\!\!\!\!|\Gamma_{large}^{l} (v) \cap T_{large}(s)|\!<\!|\Gamma_{small}^{l}(u)\cap T_{small}(s)|\ \vee\]\[\bigvee_{l\ is\ label} \newline |\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)| < |\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)|\] is a cutting function by IND.
    1.62  \end{claim}
    1.63 -\begin{proof}
    1.64 -It has to be shown, that $LabCut_{IND}((u,v),M(s))=true\Rightarrow$
    1.65 -the mapping can not be extended to a whole
    1.66 -mapping.\\ $LabCut_{IND}((u,v),M(s))=true,$ iff the following
    1.67 -holds. $\\\exists l: |\Gamma_{large}^{l} (v)\ \cap\ T_{large}(s)| <
    1.68 -|\Gamma_{small}^{l} (u)\ \cap\ T_{small}(s)| \vee
    1.69 -|\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)| <
    1.70 -|\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)|$.
    1.71 -
    1.72 -Suppose that $|\Gamma_{large}^{l} (v)\ \cap\ T_{large}(s)| <
    1.73 -|\Gamma_{small}^{l} (u)\ \cap\ T_{small}(s)|$. Each node of
    1.74 -$\Gamma_{small}^{l} (u)\ \cap\ T_{small}(s)$ has to be matched to a
    1.75 -node in $\Gamma_{large}^{l} (v)\ \cap\ T_{large}(s)$, so
    1.76 -$\Gamma_{large}^{l} (v)\ \cap\ T_{large}(s)$ can not be smaller than
    1.77 -$\Gamma_{small}^{l} (u)\ \cap\ T_{small}(s)$. That is why $M(s)$ can
    1.78 -not be extended to a whole mapping.
    1.79 -
    1.80 -Otherwise $|\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)| <
    1.81 -|\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)|$ has to be
    1.82 -true. Similarly, each node of $\Gamma_{large}^{l}(v)\cap
    1.83 -\tilde{T}_{large}(s)$ has to be matched to a node in
    1.84 -$\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)$,
    1.85 -i.e. $\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)$ can not be
    1.86 -smaller than $\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)$, if
    1.87 -$M(s)$ is extendible.
    1.88 -\end{proof}
    1.89  The following claims can be proven similarly.
    1.90  \subsubsection{Graph isomorphism}
    1.91  \begin{claim}
    1.92 @@ -1338,7 +1270,7 @@
    1.93  
    1.94  
    1.95  
    1.96 -\begin{figure}[H]
    1.97 +\begin{figure}
    1.98  \vspace*{-1.5cm}
    1.99  \hspace*{-1.5cm}
   1.100  \begin{subfigure}[b]{0.55\textwidth}
   1.101 @@ -1472,7 +1404,7 @@
   1.102  
   1.103  
   1.104  
   1.105 -\begin{figure}[H]
   1.106 +\begin{figure}
   1.107  \vspace*{-1.5cm}
   1.108  \hspace*{-1.5cm}
   1.109  \begin{subfigure}[b]{0.55\textwidth}