Propiedades

Antes de hablar sobre las propiedades es importante conocer el número cíclico.

Si G es un grafo conexo, se llama número cíclico al número natural:

Siendo |A| el número de aristas de G; y |V| el número de vértices de G.

Si el grafo G tiene k componentes conexas resulta:

Propiedades:

• Si φ(G) = 0 entonces el grafo no tiene ciclo.
• Si φ(G) = 1 entonces el grafo tiene un ciclo.
• Si φ(G) > 1 entonces el grafo tiene más de un ciclo.

Si el grafo es un árbol, entonces el número cíclico siempre es cero, porque un árbol no tiene ciclos.

Ejemplos

Teorema:

El número de aristas que hay que suprimir en un grafo conexo para obtener un árbol maximal es el número cíclico (indica cuántas aristas se pueden suprimir pero no cuáles).

Se deben suprimir tres aristas para obtener un árbol maximal.

Subgrafo maximal

Subgrafos no maximales

Ejemplo de un árbol:

Este árbol tiene:

• Padre o raíz en 2.
• Raíz 2 tiene de hijos al 7 y 5. Por lo tanto 7 y 5 hermanos.
• 2, 5, 11 y 4 son hojas.
• El nodo en nivel uno es el 2.
• Los nodos de nivel dos son el 7 y 5.
• Altura o niveles 4.

Índice:

1. ¿Qué es un árbol?
• Estructura
• Árboles libres y orientados
2. Propiedades
3. Tipos de recorridos de un árbol
4. Bibliografía