Ninguno

Solo disponible en BuenasTareas
  • Páginas : 5 (1042 palabras )
  • Descarga(s) : 0
  • Publicado : 17 de agosto de 2010
Leer documento completo
Vista previa del texto
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...
tracking img