Matemticas Discretas TC1003

rboles: Deniciones y Resultados Bsicos

Departamento de Matemticas / Centro de Sistema Inteligentes

ITESM

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 1/14

rboles: Denicin
Un grafo G se dice que es un rbol si es un grafo conexo y no existe ningn circuito en l.
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 2/14

rboles: Denicin
Un grafo G se dice que es un rbol si es un grafo conexo y no existe ningn circuito en l. Un rbol trivial es un grafo que consiste de un solo vrtice.
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 2/14

rboles: Denicin
Un grafo G se dice que es un rbol si es un grafo conexo y no existe ningn circuito en l. Un rbol trivial es un grafo que consiste de un solo vrtice. Un grafo sin circuitos se dice bosque.
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 2/14

Ejemplos de grafos que son rboles

Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

G1

G2

G3

G4

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 3/14

Ejemplos de grafos que no son rboles

Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

G1

G2

G3

G4
rboles: Deniciones y Resultados Bsicos Matemticas Discretas - p. 4/14

Uso de rboles: rbol de Decisin

Se desean eligir los puestos de Director y Auxiliar de Director entre Luca, Mara, Toms y Juan. Se tiene que ni Luca ni Mara sern eligidas para director. Tambin se sabe que habiendo elegido a Toms como director Luca no debera ser auxiliar suyo. Construir el rbol de decisin.
Solucion
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

Elegir Director Juan Inicio Mara Luca Toms

Elegir Auxiliar Toms Luca Mara Juan Luca Mara

Seleccin

Director: Juan, Auxiliar: Toms Director: Juan, Auxiliar: Mara Director: Juan, Auxiliar: Mara Director: Toms, Auxiliar: Juan Director: Toms, Auxiliar: Mara

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 5/14

Vrtices Internos y Vrtices Terminales

Sea T un rbol:
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 6/14

Vrtices Internos y Vrtices Terminales

Sea T un rbol: s Si T tiene slo uno o dos vrtices, a cada uno de ellos se les llamar vrtices terminales.
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 6/14

Vrtices Internos y Vrtices Terminales

Sea T un rbol: s Si T tiene slo uno o dos vrtices, a cada uno de ellos se les llamar vrtices terminales.
s
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

Si T tiene tres vrtices o ms entonces

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 6/14

Vrtices Internos y Vrtices Terminales

Sea T un rbol: s Si T tiene slo uno o dos vrtices, a cada uno de ellos se les llamar vrtices terminales.
s
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

Si T tiene tres vrtices o ms entonces

x

a cada vrtice de grado 1 se le llamar vrtice hoja o vrtice terminal.

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 6/14

Vrtices Internos y Vrtices Terminales

Sea T un rbol: s Si T tiene slo uno o dos vrtices, a cada uno de ellos se les llamar vrtices terminales.
s
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

Si T tiene tres vrtices o ms entonces

x

a cada vrtice de grado 1 se le llamar vrtice hoja o vrtice terminal. a cada vrtice de grado mayor o igual que 2 se le llamar vrtice rama o vertice interno.

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 6/14

rboles: Resultados Principales

Sea G un grafo conexo:
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 7/14

rboles: Resultados Principales

Sea G un grafo conexo:
s
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

G es un rbol si y slo si entre cualquier dos vrtices de G existe solamente un camino que los une.

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 7/14

rboles: Resultados Principales

Sea G un grafo conexo:
s
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

G es un rbol si y slo si entre cualquier dos vrtices de G existe solamente un camino que los une. Si teniendo G n vrtices: G es un rbol si y slo si G tiene exactamente n 1 lados.

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 7/14

rboles: Resultados Principales

Sea G un grafo conexo:
s
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

G es un rbol si y slo si entre cualquier dos vrtices de G existe solamente un camino que los une. Si teniendo G n vrtices: G es un rbol si y slo si G tiene exactamente n 1 lados. G es un rbol si y slo si cualquier vrtice de grado mayor o igual que dos es un vrtice puente.

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 7/14

rbol Enraizado: Denicin

Un rbol enraizado es un rbol donde existe un vrtice distinguido o especial llamado raz.
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 8/14

rbol Enraizado: Denicin

Un rbol enraizado es un rbol donde existe un vrtice distinguido o especial llamado raz.
s
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

El nivel de un vrtice v es la longitud del camino del nodo raz a vrtice v.

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 8/14

rbol Enraizado: Denicin

Un rbol enraizado es un rbol donde existe un vrtice distinguido o especial llamado raz.
s
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

El nivel de un vrtice v es la longitud del camino del nodo raz a vrtice v. La altura del rbol enraizado es el mayor nivel que tienen los nodos.

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 8/14

rbol Enraizado: Denicin

Un rbol enraizado es un rbol donde existe un vrtice distinguido o especial llamado raz.
s
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

El nivel de un vrtice v es la longitud del camino del nodo raz a vrtice v. La altura del rbol enraizado es el mayor nivel que tienen los nodos. Los hijos de un nodo son los vrtices adyacentes al nodo y que estn en un nivel mayor que el nodo.

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 8/14

rbol Enraizado: Denicin

Un rbol enraizado es un rbol donde existe un vrtice distinguido o especial llamado raz.
s
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

El nivel de un vrtice v es la longitud del camino del nodo raz a vrtice v. La altura del rbol enraizado es el mayor nivel que tienen los nodos. Los hijos de un nodo son los vrtices adyacentes al nodo y que estn en un nivel mayor que el nodo. Si v es un hijo de w, w se dice padre de v.

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 8/14

rbol Enraizado: Denicin

Un rbol enraizado es un rbol donde existe un vrtice distinguido o especial llamado raz.
s
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

s s

El nivel de un vrtice v es la longitud del camino del nodo raz a vrtice v. La altura del rbol enraizado es el mayor nivel que tienen los nodos. Los hijos de un nodo son los vrtices adyacentes al nodo y que estn en un nivel mayor que el nodo. Si v es un hijo de w, w se dice padre de v. Si v y w son hijos de un mismo padre se llaman hermanos.

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 8/14

rbol Enraizado: Denicin

Un rbol enraizado es un rbol donde existe un vrtice distinguido o especial llamado raz.
s
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

s s

El nivel de un vrtice v es la longitud del camino del nodo raz a vrtice v. La altura del rbol enraizado es el mayor nivel que tienen los nodos. Los hijos de un nodo son los vrtices adyacentes al nodo y que estn en un nivel mayor que el nodo. Si v es un hijo de w, w se dice padre de v. Si v y w son hijos de un mismo padre se llaman hermanos. Si v est en el camino de la raz a w se dice que v es un ancestro de w o que w es un descendiente de v.

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 8/14

Ejemplo de rbol enraizado

Considere el rbol con raz v0 v0 v1 v4 v7 v8 v9 v2 v5 v10 v3 v6
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

a. Nivel de v5 : c. Altura del rbol: e. Padre de v2 : g. Descendientes de v3 :

rboles: Deniciones y Resultados Bsicos

b. Nivel de v0 : d. Hijos de v3 : f. Hermanos de v8 : h. Ancestros de v5 :

Matemticas Discretas - p. 9/14

Ejemplo de rbol enraizado

Considere el rbol con raz v0 v0 v1 v4 v7 v8 v9 v2 v5 v10 v3 v6
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

a. Nivel de v5 : 2 c. Altura del rbol: 3 e. Padre de v2 : v0 g. Descendientes de v3 : v5 , v6 y v10

rboles: Deniciones y Resultados Bsicos

b. Nivel de v0 : 0 d. Hijos de v3 : v5 y v6 f. Hermanos de v8 : v7 y v9 h. Ancestros de v5 : v0 y v3

Matemticas Discretas - p. 9/14

rbol Binario: Denicin

Un rbol binario es un rbol enraizado donde cada nodo tiene a lo ms dos hijos.
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 10/14

rbol Binario: Denicin

Un rbol binario es un rbol enraizado donde cada nodo tiene a lo ms dos hijos. s Cada hijo se designa se designa por el calicativo hijo derecho o hijo izquierdo.
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 10/14

rbol Binario: Denicin

Un rbol binario es un rbol enraizado donde cada nodo tiene a lo ms dos hijos. s Cada hijo se designa se designa por el calicativo hijo derecho o hijo izquierdo.
s
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

El rbol binario se dice rbol binario completo si todo padre tiene exactamente dos hijos.

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 10/14

rbol Binario: Denicin

Un rbol binario es un rbol enraizado donde cada nodo tiene a lo ms dos hijos. s Cada hijo se designa se designa por el calicativo hijo derecho o hijo izquierdo.
s
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

El rbol binario se dice rbol binario completo si todo padre tiene exactamente dos hijos. Para cada padre v el subrbol izquierdo es el subgrafo de G que es el rbol enraizado con raz el hijo izquierdo de v;

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 10/14

rbol Binario: Denicin

Un rbol binario es un rbol enraizado donde cada nodo tiene a lo ms dos hijos. s Cada hijo se designa se designa por el calicativo hijo derecho o hijo izquierdo.
s
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

El rbol binario se dice rbol binario completo si todo padre tiene exactamente dos hijos. Para cada padre v el subrbol izquierdo es el subgrafo de G que es el rbol enraizado con raz el hijo izquierdo de v; el subrbol derecho es el subgrafo de G que es el rbol enraizado con raz el hijo derecho de v;

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 10/14

rboles Binarios: Resultados principales

s

Si T es un rbol binario que tiene n nodos terminales y que tiene altura h entonces n 2h

Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 11/14

rboles Binarios: Resultados principales

s

Si T es un rbol binario que tiene n nodos terminales y que tiene altura h entonces n 2h

Sea T un rbol binario completo con k vrtices internos. Entonces T tiene un total de 2 k + 1 vrtices k + 1 de los cuales son terminales.

Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 11/14

Ejemplos de conteo en rboles binarios

Pregunta:
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

Un rbol binario T tiene 44 nodos terminales entonces tiene una altura mayor o igual que ...

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 12/14

Ejemplos de conteo en rboles binarios

Pregunta:
Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

Un rbol binario T tiene 44 nodos terminales entonces tiene una altura mayor o igual que ...
Solucion

Por el resultado principal para rboles binarios, si h es la altura: 40 = no. nodos terminales 2h Entoces tomando logaritmo en base 2 obtenemos: 5.321 h Como h debe ser entero, entonces la altura del rbol es mayor o igual que 6.
rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 12/14

Pregunta:

Un rbol binario completo T tiene 79 vrtices totales, entonces el nmero de vrtices internos es:

Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 13/14

Pregunta:

Un rbol binario completo T tiene 79 vrtices totales, entonces el nmero de vrtices internos es:
Solucion

Por el resultado principal en rboles binarios completos: Si k es el nmero total de vrtices internos en un rbol binario completo, entoces el nmero total de vrtices es 2 k + 1, por tanto: 2 k + 1 = 79 Despejando k, tenemos que k = 39.

Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 13/14

Pregunta:

Un rbol binario completo T tiene 83 vrtices totales, entonces el nmero de vrtices terminales es:

Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

rboles: Deniciones y Resultados Bsicos

Matemticas Discretas - p. 14/14

Pregunta:

Un rbol binario completo T tiene 83 vrtices totales, entonces el nmero de vrtices terminales es:
Solucion

Por el resultado principal en rboles binarios completos: Si k es el nmero total de vrtices internos en un rbol binario completo, entoces el nmero total de vrtices es 2 k + 1, por tanto: 2 k + 1 = 83 Despejando k, tenemos que k = 41, es decir el nmero total de vrtices internos es 41. Por tanto, el total de vrtices terminales es: n k = 83 41 = 42
rboles: Deniciones y Resultados Bsicos

Arbol Ejemplo 1 Ejemplo 2 Ejemplo 3 Vertices Resultados 1 Arbol enraizado Ejemplo 4 Arbol binario Resultados 2 Ejemplos

Matemticas Discretas - p. 14/14