Teoría de grafos: arborescencias, árboles generadores y grafos eulerianos

¿Qué es una arborescencia?

El concepto de arborescencia es análogo al concepto de árbol, pero asociado a grafos orientados. Diremos que un grafo dirigido"" es una arborescencia si satisface las siguientes condiciones:

1. Existe un vértice X₀, denominado raíz de la arborescencia, desde el que se puede alcanzar por un camino cualquier otro vértice del grafo.
2. El grafo dirigido"" no tiene ciclos, en el sentido del grafo no dirigido subyacente.

¿Qué condiciones debe admitir un grafo para que admita arborescencia generadora?

La condición necesaria y suficiente para que un grafo dirigido admita arborescencia generadora es que exista un vértice que sea antecedente de todos los demás.

Sea G un grafo no dirigido, conexo, con n vértices tal que todas sus aristas tienen asociado el mismo costo C. ¿Existe algún árbol generador? ¿Qué conclusiones podemos extraer sobre el árbol de coste mínimo?

Si existe un árbol generador, ya que la definición de árbol generador está asociada a los grafos no dirigidos y la condición necesaria y suficiente para que un grafo no dirigido admita algún árbol generador es que dicho grafo sea conexo.

¿Qué es un grafo euleriano?

Es aquel en que puede recorrerse todas sus aristas (arcos) de manera consecutiva y sin repetir ninguna.

¿Qué condiciones deben cumplir los vértices de un grafo para que sea euleriano?

Las condiciones de un grafo para que sea euleriano es que sus vértices tengan grado par (el recorrido empieza y acaba en el mismo vértice) y que todos los vértices tienen grado par menos 2 (el recorrido empieza en un vértice y acaba en otro vértice diferente).

Grafo orientado (dirigido)

Camino: sucesión de arcos consecutivos; longitud es el número de arcos que lo forman.

Circuito: camino cerrado.

Grafo no dirigido (no dirigido)

Cadena: sucesión de aristas consecutivas.

Ciclo: cadena cerrada.

Observación: todo camino es una cadena, pues asociado a un arco, siempre tenemos una arista (sin más que eliminar el sentido del arco).

Matriz booleana

1. B contiene unos en la diagonal ---> el grafo tiene bucles.
2. G es no orientado ---> B es simétrica.
3. Operaciones"algebraica" sobre B permiten determinar el número de caminos que unen 2 nodos.

Matriz latina

1.L contiene elementos no vacios en la diagonal --> el grafo tiene bucles

2.G es no orientado --> L es simétrica

3.Operaciones “algebraicas” sobre L permiten determinar el nº de caminos que unen 2 nodos