Ninguno

3.1. Árboles. Árboles enraizados. Definición 3.1.1. Un árbol es un grafo conexo que no tiene ciclos. Ejemplo 3.1.2

Los grafos G1 y G2 son árboles, mientras que los grafos G3 y G4 no lo son. Definición 3.1.3. Un bosque es un grafo donde cada componente conexa es un árbol. Definición equivalente: Un bosque es un grafo acíclico. El grafo G4 del ejemplo anterior es un bosque. Caracterizaciones delos árboles Proposición 3.1.4. El grafo T =(V, E) es un árbol si y solo si todo par de vértices de T están conectados por un único camino simple. Demostración. => T es un árbol =>T conexo => Dados u, v ∈ V existe al menos un camino simple que los une. Supongamos que entre los vértices u y v existen dos caminos simples. Denotemos por x el vértice donde estos caminos divergen por primera vez y porw el vértice donde estos caminos convergen nuevamente. Por tanto los dos caminos diferentes entre los vértices x y w forman un ciclo, lo cual contradice la definición de árbol.

T es un árbol. =>Sean u, v ∈ V y agreguemos una arista que los une. Caso 1. Si u y v son adyacentes, al agregar la arista se producen dos aristas paralelas produciendo un ciclo de longitud dos. Caso 2. Si u y v no sonadyacentes existe un camino único que los une. Con la nueva arista este camino se cierra formando un ciclo.

 Supongamos que T no es conexo. => existe al menos dos vértices  u, v que no son mutuamente alcanzables. Al agregar la arista (u, v) aparece un ciclo, lo cual implica la existencia de un camino entre u y v. Contradicción. T es conexo por tanto es un árbol.
Proposición 3.1.6. El grafo T=(V, E) es un árbol si y solo si T es conexo y toda arista es un puente. Demostración.

=> T es un árbol. => Sea a una arista que es no es puente. => a forma parte de un ciclo. => Contradicción. No existen ciclos. => T es un árbol.
Proposición 3.1.7. Todo árbol tiene al menos dos vértices con grado 1 (hojas). Demostración.

Sea v1, v2, ..., vs un camino de longitud máxima en el árbol T.Supongamos que d(v1)>1 . Pueden ocurrir dos casos: a) v1 es adyacente a otro vértice de T que no pertenece al camino. El camino puede extenderse. Contradicción con camino de longitud máxima. b) v1 es adyacente a otro vértice del camino diferente de v2. Aparece un ciclo. Contradicción con definición de árbol. Por tanto d(v1)=1. Lo mismo ocurre para d(vs)
Proposición 3.1.7. Sea T =(V, E) un grafo con nvértices. Las siguientes afirmaciones son equivalentes:

1. 2. 3.

T es un árbol. T es acíclico y tiene exactamente m=n-1 aristas. T es conexo y tiene exactamente m=n-1 aristas.

Proposición 3.1.8. Sea T =(V, E) un grafo con n vértices y k componentes. G es un bosque si y solo si tiene m=n-k aristas. Proposición 3.1.9. (Fórmula de Cayley) El número de árboles etiquetados de n vértices es nn − 2 . Código de Prüfer de un árbol T de orden n, etiquetado con {1,2,...,n}. Este código es una sucesión de n-2 números de {1,2,...,n}.

1. Se busca la hoja u de T de menor etiqueta y se añade al código C, inicialmente vacío, la etiqueta de su vecino. 2. Se borra de T el vértice u, T=T-{u}.

3. Si T tiene más de dos vértices se vuelve al paso 1. En caso contrario el algoritmo termina.Descodificación. Se parte ahora del código C, que es una sucesión de longitud n-2, de la lista L ={1,2,...,n} y del bosque trivial T de n vértices etiquetados con {1,2,...,n}

1. Repetir lo siguiente n-2 veces lo siguiente. Sea j el primer elemento de C y sea k el menor número de L que no está en C. Añadir a T la arista (j, k). Borrar j de C y k de la lista L. 2. Cuando sólo quedan dos elementos enL y ninguno en C, añadir a T la arista que une dichos elementos. Fin del algoritmo
Ejemplo 3.1.10. Construir el código Prüfer del siguiente árbol:

Ejemplo 3.1.11. Construir el árbol correspondiente al código [2,3,1,1,1,2,2,5]. Definición 3.1.12. Un árbol con raíz o árbol enraizado es un árbol en el cual un vértice en particular se designa como raíz.

Los árboles con raíz se representan de...