Ngj/v2008 7.3 rboles

1

Matemticas Discretas Tc1003

Teora de Grafos

7.3 rboles Definicin. Sea A un grafo. A recibe el nombre de rbol s y slo si:

A es conexo. A no contiene circuitos.

Ejemplos:

Definicin. Sea A un rbol. Un vrtice de grado 1 se llama una hoja. Un vrtice de grado mayor que 1 se llama rama. De las definiciones anteriores se desprenden las siguientes propiedades:

Existe una trayectoria nica entre dos vrtices cualesquiera de un rbol.

El nmero de vrtices es mayor en 1 al nmero de aristas. Un rbol con dos o ms vrtices tiene al menos dos hojas.

Ejemplo Un grupo de ajedrecistas que luchan por un campeonato. Cada ajedrecista tiene una nica oportunidad para enfrentar al campen vigente, y que el perdedor de cualquier encuentro ser eliminado de la contienda.

Sea A = (V, E) un grafo no dirigido donde los vrtices de V representan los ajedrecistas y las aristas de E representan los encuentros.

Sea V = { v1, v2, v3, v4, v5, v6, v7, v8, v9 } Al inicio, v1 es el campen vigente y que se dan los siguientes encuentros: - v1 venci a v2, v3 y v4 y pierde con v5. - v5 venci a v6 y v7 y pierde con v8. - v8 pierde con v9. El rbol que detalla esta situacin, es el siguiente:

Los vrtices v2, v3, v4, v6, v7, v9 son hojas.

Los vrtices v1, v5, v8 son ramas.

Ngj/v2008 7.3 rboles

2

Matemticas Discretas Tc1003

Teora de Grafos

Definicin. Sea G un grafo dirigido. Se dice que G es un rbol dirigido si se convierte en un rbol cuando se ignoran las direcciones de sus aristas. Definicin. Un rbol con raz es un rbol dirigido que posee exactamente un vrtice cuyo grado de entrada es 0 y los grados de entrada de todos los dems vrtices es 1. El vrtice con grado de entrada 0 se llama raz de rbol. Un vrtice cuyo grado de salida es 0 se llama hoja. Un vrtice cuyo grado de salida es diferente de 0 se llama rama. Definicin. Sea vi una rama de un rbol con raz. Se dice que kV es un hijo de iV si existe una arista dirigida de iV a kV , adems se dice que vi es padre de kV . En un rbol con raz se dice que los vrtices son hermanos si son hijos del mismo vrtice. Ejemplo Un hombre que tiene dos hijos, de los cuales uno no tiene hijos y el otro tiene tres hijos. Solucin

Ngj/v2008 7.3 rboles

3

Matemticas Discretas Tc1003

Teora de Grafos

Definicin. Sea A un rbol con raz. Se dice que A es un rbol binario si cada rama tiene exactamente dos hijos. Ejemplo

El rbol anterior muestra el nmero de encuentros en un torneo de eliminacin simple con 8 competidores.

Se juegan un total 7 encuentros a saber: Cuatro encuentros en la primera ronda. Dos encuentros en la segunda ronda. El encuentro final. En total son 7 encuentros.

En este rbol binario, las hojas representan a los competidores en el torneo y las ramas a los ganadores de los encuentros o, equivalentemente los encuentros jugados en el torneo. Si se llama r el nmero de ramas y h el nmero de hojas en un rbol binario, se puede demostrar que: r = h 1.

Ngj/v2008 7.3 rboles

4

Matemticas Discretas Tc1003

Teora de Grafos

Si un grafo tiene un vrtice oU que solo contiene una diferente de 1UUo (a s mismo) entonces es un rbol rbol no es rbol este vrtice tiene dos trayectorias En general

Altura = 3 (el nivel mas grande) raz = que no tiene padre (inicial) padre = que tiene hijo(s) hoja = no tiene hijo(s), tiene padre Conjunto de rboles = Bosque. rbol ordenado: tiene nivel, los hijos de izquierda a derecha. n-rbol: cuando cada padre tiene a lo ms n hijos rbol binario: cada padre tiene a lo ms 2 hijos.

Ngj/v2008 7.3 rboles

5

Matemticas Discretas Tc1003

Teora de Grafos

Para: sub - rboles

Cuntos subrboles? 6 Altura = ? 5

10 VV 20 VV 30 VV 1V 2V 3V

4V 6V 8V 13V

Ngj/v2008 7.3 rboles

6

Matemticas Discretas Tc1003

Teora de Grafos

Notacin polaca La evaluacin se realiza de derecha a izquierda y de abajo hacia arriba Ejemplo: ( ) ( )( )( )[ ] ( )[ ]xyyx +++ 727413 Primero: parntesis interiores rbol etiquetado

EJEMPLO:

( )( ) ( ) ( )( )xxx ++ 3223 ( )( ) ( ) ( )( )xxx ++ 3232

5 2 6 1 7 3 9 4 8

8 = ? 5, 6, 7, 9, 8 4 = ? 5, 2, 3, 4

Ngj/v2008 7.3 rboles

7

Matemticas Discretas Tc1003

Teora de Grafos

rboles de expansin Un rbol T es un rbol de expansin de un grafo G si T es un subgrafo de G que contiene todos los vrtices de G. [Johnsonbaugh, 392] Ejemplos: Grafo: rbol de expansin:

rboles enraizados En ciencias computacionales los rboles tienen muchas veces vrtices principales que pueden utilizarse para dar a los rboles estructuras dirigidas. En general, se puede transformar cualquier grafo no dirigido en un grafo dirigido ponindole flechas. Si el grafo es un rbol lo que se obtiene es un rbol dirigido. Si todas las flechas parten de un solo vrtice se llama rbol enraizado. [Ross, 451]

2008-06-27T09:54:47-0500Nazira Guerrero-Jezzini