hola

Matemáticas Discretas
Tc1003
Teoría de Grafos

7.3 Árboles
•
•

Definición. Sea A un grafo. A recibe el nombre de árbol sí y sólo si:
A es conexo.
A no contiene circuitos.

Ejemplos:Definición. Sea A un árbol. Un vértice de grado 1 se llama una hoja. Un vértice de
grado mayor que 1 se llama rama.
De las definiciones anteriores se desprenden las siguientes propiedades:
• Existeuna trayectoria única entre dos vértices cualesquiera de un
árbol.
• El número de vértices es mayor en 1 al número de aristas.
• Un árbol con dos o más vértices tiene al menos dos hojas.
EjemploUn grupo de ajedrecistas que luchan por un campeonato. Cada
ajedrecista tiene una única oportunidad para enfrentar al campeón vigente, y que el
perdedor de cualquier encuentro será eliminado de lacontienda.
• Sea A = (V, E) un grafo no dirigido donde los vértices 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 campeón 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 quedetalla esta situación, es el siguiente:

Los vértices v2, v3, v4, v6, v7, v9 son hojas.
Los vértices v1, v5, v8 son ramas.

Ngj/v2008

7.3 Árboles

1

Matemáticas Discretas
Tc1003
Teoría deGrafos
Definición. 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.
Definición. Un árbol con raíz es unárbol dirigido que posee exactamente un
vértice cuyo grado de entrada es 0 y los grados de entrada de todos los demás
vértices es 1.
El vértice con grado de entrada 0 se llama raíz de árbol. Un vérticecuyo
grado de salida es 0 se llama hoja. Un vértice cuyo grado de salida es diferente de 0
se llama rama.
Definición. Sea vi una rama de un árbol con raíz. Se dice que Vk es un hijo de Vi si...