Terminología de redes (V)

Considérese un conjunto de n nodos (por ejemplo, n=5 nodos en la figura 10.2) sin arcos. Se puede entonces "hacer crecer" un "árbol" agregando un arco (o rama) a la vez de cierta manera. El primer arco puede ir a donde sea para conectar algún par de nodos. De ahí en adelante, cada arco nuevo debe agregarse entre un nodo que haya sido conectado a otros nodos y a un nuevo nodo no conectado. Si se agregan arcos de esta manera, se evita que se forme un ciclo y además se asegura que el número de nodos conexos es uno más que el número de arcos. Cada nuevo arco crea un árbol más grande, que es una red conexa (para algún subconjunto de n nodos) que no contiene ciclos no dirigidos. Una vez que se ha agregado el (n-1)-ésimo arco, el proceso se detiene porque el árbol resultante se expande (conecta) a todos los n nodos.

Este árbol se llama árbol de expansión, y es una red conexa para los n nodos que no contiene ciclo no dirigidos. Todo árbol de expansión tiene exactamente (n-1) arcos, ya que este es el mínimo número de arcos necesarios para tener una red conexa y el máximo número posible para que no hay ciclos no dirigidos.

La figura 10.3 muestra los cinco nodos y algunos de los arcos de la figura 10.2 para ilustrar este proceso de hacer crecer un árbol poniendo un arco (rama) a la vez, hasta que se obtiene un árbol de expansión. En cada etapa se tienen varias alternativas para el nuevo arco,por lo que la figura 10.3 muestra sólo una de las muchas formas de construir un árbol de expansión en este caso. Ahora bien, obsérvese cómo cada nuevo arco que se agrega satisface las condiciones especificadas en el párrafo anterior. Los árboles de expansión se estudiarán más a fondo en la sección 10.4.

Los árboles de expansión juegan un papel clave en el análisis de muchas redes. Por ejemplo, forman la base del problema del árbol de mínima expansión que se presenta en la sección 10.4. Otro ejemplo es que los árboles de expansión (factibles) corresponden a las soluciones básicas factibles en el método símplex de redes que se analiza en la sección 10.6.

Por último, será necesario introducir la terminología adicional sobre los flujos en redes. La cantidad máxima de flujo (quizá infinito) que puede circular en un arco dirigido se conoce como capacidad del arco. Entre los nodos, se pueden distinguir aquellos que son generadores de flujo, absorbedores netos o ninguno de los dos. Un nodo fuente (o nodo de origen) tiene la propiedad de que el flujo sale del nodo excede el flujo que entra a él. El caso inverso es un nodo demanda (o nodo destino), en el que el flujo que llega excede al que sale del nodo. Un nodo de trasbordo (o nodo intermedio)satisface la conservación del flujo, así el flujo que entra es igual al que sale.