6320_HW1.tex

\documentclass[12pt, a4paper]{report}

\title{Homework 1}
\author{Chang Wang}
\begin{document}

\maketitle

\section{Consider the (Vertex list-edge list) and the (Adjacency Matrix) representations of the graph isomorphism problem.}
\subsection{Derive the length functions for these two representations.}
Here Assuming $G_{1} = (V_{1}, E_{1})$ denotes Vertex list-edge list, and $G_{2} = (V_{2}, E_{2})$ denotes Adjacency Matrix. \\
The encoding scheme for $G_{1}$: use [x] to represent the name of vertex, and x is a decimal; if there is a connection between vertices x and y, use ([x], [y]) to present. Under this encoding scheme, the graph $G_{1}$ could be presented like, ([1] [2]) ([1] [3]) ([2] [4]). Here we just consider the upper bound. So the length function could be: \\
\begin{center}
$f_{1}(V, E) = 4V + 10E + (V+2E) \log_{10} V$
\end{center}
And the maximum case is a complete graph, we have $E = \frac {V(V-1)} {2}$. Then \\
\begin{center}
$f_{1}(V, E) = 5V^{2} - V + V^{2} \log_{10} V$
\end{center}
The encoding scheme for $G_{2}$: if there is a connection between vertices x and y, set 1, otherwise set 0. So this adjacency matrix is a $V \times V$ matrix, meanwhile there are $V - 1$ separators after each row in order to tell the length function this is an end of a row. So the length function should be: \\
\begin{center}
$f_{2}(V, E) = V^{2} + (V - 1)$
\end{center}
\subsection{Prove that these two functions are polynomial related.}
In order to prove $f_{1}$ and $f_{2}$ are polynomial related, we need to find two polynomials $P_{1}(x)$ and $P_{2}(x)$, and $\forall n$ $f_{1}(n) \leq P_{1}(f_{2}(n))$ and $f_{2}(n) \leq P_{2}(f_{1}(n))$. \\
Here suppose 
\begin{center}
$P_{1}(n) = n^{2} \log_{10} n + 5n$
\end{center}
use $f_{2}$ to replace n, we can get \\
\begin{center}
$P_{1}(f_{2}) = [V^{2} + (V-1)]^{2} \log_{10} [V^{2} + (V-1)] + 5 [V^{2} + (V-1)]$
\end{center}
Then
\begin{center}
$P_{1}(f_{2}) - f_{1} = [V^{2} + (V-1)]^{2} \log_{10} [V^{2} + (V-1)] + 5 [V^{2} + (V-1)] - 5V^{2} + V - V^{2} \log_{10} V$ \\
$= [V^{2} + (V-1)]^{2} \log_{10} [V^{2} + (V-1)] - V^{2} \log_{10} V + 6V - 5$ \\
\end{center}
Obviously, $[V^{2} + (V-1)]^{2} > V^{2}$ and $6V > 5$, so we can say $P_{1}(f_{2}) > f_{1}$. \\
And suppose 
\begin{center}
$P_{2}(n) = n$
\end{center}
use $f_{1}$ to replace n, we can get \\
\begin{center}
$P_{2}(f_{1}) = 5V^{2} - V + V^{2} \log_{10} V$
\end{center}
Then
\begin{center}
$P_{2}(f_{1}) - f_{2} = 4V^{2} - 2V + V^{2} \log_{10} V + 1$
\end{center}
It's easy to prove this expression is larger than 0, so $P_{2}(f_{1}) > f_{2}$. \\
Apparently, $P_{1}$ and $P_{2}$ are polynomials, then we proved $f_{1}$ and $f_{2}$ are polynomial related.
\end{document}