A piece of a document sent to students regarding graph isomorphisms.

practica_isomorfismo.tex

\section{Resumen de isomorfismos}

\begin{definition} Dados grafos $G = (V, E)$ y $G' = (V', E')$, se dice que $G$ y $G'$ son \emph{isomorfos} si existe una función $f: V \to V'$ biyectiva tal que $\forall \ u, v \in V, (u, v) \in E \iff (f(u), f(v)) \in E'$. Notamos $G \cong G'$, y decimos que $f$ es un \emph{isomorfismo de grafos}.
\end{definition}

\paragraph{} Intuitivamente, un isomorfismo de grafos preserva lo que es el grafo en sí. Sobre un grafo, generalmente, nos importan solo los ejes entre los nodos. No nos importan, por ejemplo, las etiquetas con las que nombremos a los nodos, ni la posición gráfica de los mismos, ni las curvas que usemos para dibujar los ejes, ni si llovía mientras lo dibujábamos. Un isomorfismo de grafos preserva la estructura que nos importa, la relación entre los nodos. Se deja como ejercicio ver que ``ser isomorfo'' es una relación de equivalencia.

\paragraph{} Como dijo Mariano, podemos pensar que cualquier propiedad que intentemos escribir usando sólo esta estructura del grafo, va a ser preservada por el isomorfismo, pues siempre vamos a poder hablar del eje entre los transformados de nuestros nodos (o sea, si hablamos de $(u, v)$, siempre podemos hablar de $(f(u), f(v))$). La mayoría de las propiedades que nos interesan, son expresables puramente como relaciones entre nodos y ejes. A estas propiedades se las conoce como \emph{invariantes de grafos}. Acá algunos de ejemplos, luego sus pruebas.

\begin{enumerate}
\item $|V| = |V'|$
\item $|E| = |E'|$
\item $G$ es conexo sí y sólo sí $G'$ es conexo.
\item $G$ y $G'$ tienen la misma secuencia gráfica, sin importar el orden. 
\item $G$ y $G'$ tienen el mismo número de clique.
\end{enumerate}

En la práctica hay un par más (ejercicio 5.19).

\begin{enumerate}
\item \begin{proof}
Tenemos una biyección entre $V$ y $V'$. Como son finitos, tienen la misma cantidad de elementos. \qed
\end{proof}
\item \begin{proof}
Lo que podemos ver acá es que $f$ \emph{induce} otra biyección $g: E \to E'$, de tal forma que definimos $g((u, v)) = (f(u), f(v))$. Como $f$ era biyección, $g$ es biyección. Luego, por el mismo argumento que antes, si hay una biyección entre $E$ y $E'$ y son finitos, entonces tienen la misma cantidad de elementos. \qed
\vskip 10pt
\paragraph{} Intuitivamente, sabemos que $f$ preserva ejes. Luego, si hubiera un eje no correspondido $(f(u), f(v))$ en $E'$, podríamos tomar $(f^{-1}(f(u)), f^{-1}(f(v)))$ y llegaríamos a que ese eje sí era correspondido, justamente por $(u, v) \in E$. Luego no puede haber un eje que no sea correspondido (la correspondencia acá se hace explícita con la función $g$).
\end{proof}
\item \begin{proof}
Como ``ser isomorfo'' es una relación de equivalencia, basta probar que si $G$ es conexo, entonces $G'$ lo es. Asumamos lo contrario: $\exists\ v'_i, v'_j \in V'$ tal que no hay un camino en $G'$ entre $v'_i$ y $v'_j$, pero $G$ es conexo. Formalmente, esto es equivalente a que no existe una secuencia de números naturales $C$ tal que $C_1 = i, C_{|C|} = j$, y $\forall\ 1 \le k \le |C|, (v'_{C_k}, v'_{C_{k+1}}) \in E'$, pero $G$ es conexo. Un poco menos formalmente, pero igual de correcto, es decir que no hay un \emph{camino} $v'_i \rightsquigarrow v'_j$ en $G'$.
\vskip 10pt
\paragraph{} Consideremos ahora los nodos $f^{-1}(v'_i)$ y $f^{-1}(v'_j)$. Como estos dos nodos están en $G$, y $G$ es conexo, entonces hay un camino $X$ entre ellos en $G$. Entonces, podemos aplicar $f$ a cada nodo en $X$. Para cualquier par de nodos $(u, v)$ adyacentes en $X$, $(f(u), f(v))$ también son adyacentes, porque $f$ es un isomorfismo entre $G$ y $G'$. Por lo tanto aplicar $f$ a cada nodo en el camino, me sigue dando un camino en $G'$. Pero entonces, tengo un camino en $G'$ entre $f(f^{-1}(v'_i)) = v'_i$ y $f(f^{-1}(v'_j)) = v'_j$. Dijimos que esto no podía pasar, absurdo. Luego, no puede ser que $G$ sea conexo, pero $G'$ no. \qed
\end{proof}
\item \begin{proof}
Para probar esto, basta probar que, para todo $v \in V$, $deg(v) = deg(f(v))$. Como $f$ preserva ejes, para cada eje $(v, v') \in E$, hay un eje $(f(v), f(v')) \in E'$, y viceversa. Vale lo mismo para ejes de la forma $(v', v) \in E$\footnote{En general, en un grafo $G = (V, E)$ sin direcciones en los ejes, se considera que $E$ no es un subconjunto de $V \times V$, sino que $E \subseteq \mathcal{P}(V) = \{C\mbox{ tal que } C \subseteq V\}$, con $|x| = 2\ \forall\ x \in E$. O sea, $E$ son los subconjuntos de 2 elementos de $V$. Esto es lo mismo que considerar las tuplas en $V \times V$, pero sin importar el orden.}. Luego, $deg(v) = |\{(u, u') \in E\mbox{ tal que } u = v \lor u' = v\}| = |\{(u, u') \in E' \mbox{ tal que } u = f(v) \lor u' = f(v)\}| = deg(f(v))$. \qed
\end{proof}
\item \begin{proof}
Basta probar que si $G$ tiene una clique de $k$ elementos, entonces $G'$ tiene una clique de $k$ elementos, para cualquier $k$. Si $G$ tiene una clique de $k$ elementos, significa que existen $X = \{v_1, \cdots, v_k\} \subseteq V$ tal que para todo $1 \le i, j \le k, i \ne j, (v_i, v_j) \in E$. Tomando $f$ de cada nodo, vemos que tenemos un conjunto $X' = \{f(v_1), \cdots, f(v_k)\} \subseteq V'$, y como $f$ preserva ejes, $(v_i, v_j) \in E \iff (f(v_i), f(v_j)) \in E'$. Luego, como para cualquier par de nodos distintos $v_i, v_j \in X$ existía $(v_i, v_j) \in E$, para cualquier par de nodos distintos $f(v_i), f(v_j) \in X'$, existe $(f(v_i), f(v_j)) \in E'$. Luego, $X'$ induce un subgrafo completo, de $|X| = k$ elementos. Esto es lo mismo que decir que $G'$ tiene una clique de $k$ elementos. \qed
\end{proof}
\end{enumerate}

Por último, hay cosas que no son invariantes de grafos, por ejemplo: 

\begin{enumerate}
\item Si representamos los nodos por números, $\displaystyle \sum_{i=1}^n v_i \cdot deg(v_i)$.
\item La posición en el plano donde dibujo los nodos, o las curvas particulares que uso para los ejes.
\item La matriz de adyacencia (aunque, como dije en clase, las matrices de adyacencia de dos grafos isomorfos son permutaciones una de la otra.)
\end{enumerate}