Correspondencia entre soluciones básicas factibles y árboles de expansión factibles (I)

El concepto más importante que apoya el método símplex de redes es su representación como red de soluciones básicas factibles. Recuérdese que en la sección 10.6 se estableción que con n nodos, toda solución básica factible tiene (n-1)variables básicas, donde cada variable básica xij representa el flujo a través del arco i→ j. Se hace referencia a estos (n-1) como arcos básicos (De igual manera, los arcos corresponderan a variables no básicas, xij =0 o yij = 0, se llaman arcos no básicos.)

Una propiedad de los arcos básicos es que nunca forman ciclos no dirigidos. (Esta propiedad evita que la solución que se obtiene sea un promedio ponderado de otro par de soluciones factibles, lo que violaría una de las propiedades generales de las soluciones básicas factibles). Sin embargo, cualquier conjunto de (n-1) arcos que no contiene ciclos no dirigidos forma un árbol de expansión. Por lo tanto, cualquier conjunto de arcos básicos forma un árbol de expansión.