Conceptos Esenciales de Grafos y Algoritmos: Flujo, Emparejamiento y Caminos Óptimos

Conceptos de Flujo en Redes de Transporte

Flujo

El flujo es el número que determina el valor de algo que pasa por una red de transporte.

Valor de Flujo

El valor de flujo es la suma total de los flujos de las aristas que tienen como vértice inicial la fuente y como final el sumidero.

Corte de una Red

Un corte de una red es una partición del conjunto de vértices de una red de transporte (S, T).

Teorema del Flujo Máximo y Corte Mínimo

El valor de cualquier flujo es menor o igual que la capacidad de cualquier corte. Dado que el número de cortes es finito, esto implica que existe un flujo cuyo valor es máximo y un corte cuya capacidad es mínima.

Matemáticamente, se expresa como:

Valor Flujo Máximo ≤ Capacidad del Corte Mínimo

Emparejamiento en Grafos Bipartitos

Emparejamiento de un Grafo Bipartito

Un emparejamiento de un grafo bipartito es un subconjunto M del conjunto de aristas E con la propiedad de que dos aristas nunca tienen un vértice en común.

• Un emparejamiento se dice que es máximo si y solo si ningún otro emparejamiento tiene un número de aristas mayor.
• Un emparejamiento se dice que es completo cuando todos los vértices de V1 están conectados con los vértices de V2.

Condición de Hall

Un grafo bipartito admite un emparejamiento completo si, y solo si, se cumple la Condición de Hall:

|T(A)| ≥ |A| para todo A ⊆ V1

Donde |T(A)| = {v ∈ V2 | {u, v} ∈ E para algún u ∈ V1}.

Algoritmos de Caminos y Búsqueda en Grafos

Algoritmo de Dijkstra

El Algoritmo de Dijkstra es un algoritmo que permite hallar un camino de longitud mínima entre dos vértices en un grafo ponderado.

Sean a el vértice de partida y z el vértice final. El peso de una arista cualquiera (u, v) se denotará por w(u, v). Durante su ejecución, se lleva a cabo un proceso de etiquetado de los vértices, donde cada etiqueta representa la longitud del camino mínimo desde a hasta el vértice en cuestión.

Búsqueda en Profundidad (DFS)

Sea G el grafo de partida. El algoritmo de Búsqueda en Profundidad (DFS) construye un árbol con raíz, en un proceso en el que se exploran los caminos desde la raíz hasta cada una de las hojas. Una vez alcanzada una hoja, se retrocede en el camino hasta encontrar un nodo que tenga algún hijo no visitado.

En cada paso, se debe tener en cuenta el subárbol construido hasta ese momento, que llamaremos árbol parcial, y el último vértice añadido, conocido como vértice activo.

Búsqueda en Anchura (BFS)

Sea G el grafo de partida. El algoritmo de Búsqueda en Anchura (BFS) encuentra un árbol con raíz, en un proceso en el que se van construyendo los niveles del árbol.

Desde el vértice activo, se visitan todos los vértices adyacentes. Se considera el conjunto de vértices del árbol parcial no visitados, que está formado por aquellos vértices del árbol parcial para los cuales aún no se han explorado sus hijos.

Árboles Generadores Mínimos

Definición de Árbol Generador Mínimo

Un árbol generador mínimo de un grafo ponderado es un árbol generador tal que la suma de los pesos de sus aristas es la mínima posible.

Teorema de Existencia del Árbol Generador Mínimo

En todo grafo ponderado, existe al menos un árbol generador mínimo.

Demostración

Dado G un grafo finito, el número de sus subgrafos es un conjunto finito. En particular, el número de árboles generadores es finito. Por tanto, al ser un conjunto finito de valores, existe un valor mínimo para la suma de los pesos de las aristas.