Ingenieria

ISOMORFISMO DE ARBOLES
En esta sección se analizan los arboles isomorfos, los arboles con raíz isomorfos y los arboles binarios isomorfos. Hay dos graficas simples G1 y G2 si y solo si existe unafunción f uno a uno y sobre del conjunto de vértices de G2 que preserva la relación de adyacencia en el sentido de que los vértices vi y vj son adyacentes en G1 si y solo si los vértices f(vi) y f(vj)son adyacentes en G.
Hay tres arboles isomorfos con cinco vértices.
Cualquier árbol con cinco vértices es isomorfo. Suponga que T es un árbol con cinco vértices y el grado máximo de vértices es 3,sea v un vértice de grado 3. Entonces v incide en tres aristas como se observa en la figura 9.8.4. L a cuarta arista no puede ser incidente en v ya que entonces v tendría grao 4.

Para que dosárboles con raíz T1 y T2 sean isomorfos, debe existir una función f uno a uno y sobre de T1 a T2 que preserve la relación de adyacencia y que preserve la raíz. Esta última condición significa que f(raíz deT1)= raíz de T2.
Ejemplo.
Los arboles con raíz T1 y T2 de la figura 9.8.8 no son isomorfos ya que la raíz de T1 tiene grado 3, pero la raíz de T2 tiene grado 2. Estos árboles son isomorfos comoarboles libres.


Existen cuatro arboles de cuatro vértices con raíz no isomorfos. Estos cuatro arboles con raíz se muestran en la figura 9.8.9.
Primero se encuentran todos los arboles decuatro vértices con raíz en los que la raíz tiene grado 3; después se encuentran todos arboles con raíz no isomorfos con cuatro vértices en los que la raíz tiene grado 2; y así sucesivamente. Se observaque la raíz de un árbol de cuatro vértices con raíz no puede tener grado mayor que 3.


Los arboles binarios son un tipo especial de arboles con raíz; entonces un isomorfismo de arboles binariosdebe preservar la relación de adyacencia y debe preservar las raíces. Sin embargo, en los arboles binarios un hijo se designa como hijo izquierdo o hijo derecho.
Ejemplo.
Los arboles binarios T1 y...