Teorema 18.1.

Un multigrafo conexo G = (V, E) contiene una cadena euleriana (ciclo euleriano) si y sólo si el número de vértices con grado impar es 2 (0).

Demostración

⇒ Si existe una cadena euleriana, los vértices con grado impar son los extremos. En el caso del ciclo, no hay vértices con grado impar. Es suficiente con ir sumando el grado al recorrer la cadena o el ciclo eulerianos. ⇐ La demostración de esta implicación se hace por inducción en el número de aristas. Se supone que hay 2 vértices con grado impar; el caso sin vértices con grado impar se incluye en el anterior sin más que considerar una arista y considerar sus extremos con grado impar al quitarla, posteriormente se cierra el ciclo al añadir dicha arista. • Si hay 1 arista, la cadena euleriana es la propia arista. • Se supone cierta la hipótesis para menos de m aristas • Si el grafo tiene m aristas: Sean a, b ∈ V los dos vértices con grado impar. Al ser dG(a) impar, al menos hay una arista incidente en a; esta arista sería la primera de la cadena euleriana. El otro extremo de la arista tiene dos posibilidades: o coincide con el vértice b o es distinto de b. Si es distinto, al tener grado par, existe otra arista distinta de la utilizada que sale, dicha arista es la siguiente en la cadena euleriana. Este esquema se repite hasta llegar al vértice b, puesto que el multigrafo es conexo. Cuando se llega al vértice b, se utiliza la hipótesis de inducción en cada una de las componentes conexas del grafo parcial que resulta al suprimir las aristas de la cadena µ[a, b] construida. Al tener menos de m aristas, todos los vértices del grafo parcial tienen grado par y existe un ciclo euleriano que recorre todas las aristas de cada componente conexa. Al ser el multigrafo conexo, se unen a la cadena µ[a, b] todos estos ciclos y se tiene así construida la cadena euleriana.

Teorema 17.1.

Dado un grafo simple G = (V, E) con n vértices, un emparejamiento K0 de máximo cardinal y un recubrimiento de mínimo cardinal F0 verifican |K0| + |F0| = n. Además, de un emparejamiento máximo se obtiene un recubrimiento de mínimo cardinal y viceversa

Demostración

A partir del emparejamiento K0 se obtiene el siguiente recubrimiento F1 = K0 ∪ {ey = {y, ∗} ∈ E / sat(y) = 0} añadiendo una arista incidente a cada uno de los vértices no saturados por K0. Por construcción, F1 es un recubrimiento y su cardinal verifica |F1| = |K0| + (n − 2|K0|) = n − |K0| porque se añade exactamente una arista por cada vértice no saturado; en caso contrario, no sería K0 el emparejamiento de máximo cardinal. En sentido contrario, a partir del recubrimiento de mínimo cardinal F0 se construye el emparejamiento K1 al quitar sucesivamente aquellas aristas que son adyacentes. En el recubrimiento F0 no puede haber cadenas de 3 o más aristas, puesto que en caso contrario se podría obtener un recubrimiento menor quitando la arista intermedia. De este modo, cada arista que se quita añade sólo un vértice no saturado para el emparejamiento que se está construyendo, se concluye así que el número de aristas quitadas de F0 para construir K1 es: |F0| − |K1| = n − 2|K1| ⇐⇒ |F0| = n − |K1| El subconjunto de aristas K1 verifica, al ser K0 un emparejamiento de máximo cardinal, la siguiente propiedad: |K1| ≤ |K0| de forma que|F1| = n − |K0| ≤ n − |K1| = |F0| y se demuestra así que F1 es un recubrimiento de mínimo cardinal también. Análogamente se demostraría que K1 es un emparejamiento de máximo cardinal, ya que |F1| ≥ |F0| lo que implica |K1| = n − |F0| ≥ n − |F1| = |K0| y K1 también es un emparejamiento máximo.

Proposición 11.1.

Dada una red de transporte (G = (V, U); {cu, u ∈ U}) y fijados los vértices s,t ∈ V, para cualquier (s,t)-flujo f se verifica que su valor de flujo f0 está acotado por la capacidad de cualquier (s,t)-corte. Es decir f0 ≤ ∑cu con u ∈ w +(A) ∀A ⊂ V s ∈ A, t₵ A.

Demostración

Sea A ⊂ V verificando s ∈ A y t₵ A y sea f un (s,t)-flujo. Considerando el arco de retorno (t, s) con índice 0, se verifica que el flujo en la red ampliada que entra en A coincide con el que sale: f0 + ∑ fu con u ∈ w −(A) u ≠0 = ∑ fu con u ∈ w +(A) . Al ser el flujo compatible, 0 ≤ fu ≤ cu ∀u ∈ U y, por consiguiente, f0 = ∑fu cn u ∈ w +(A) −∑ fu con u ∈ w −(A) u ≠ 0 ≤ ∑ cu con u ∈ w +(A) = c(w +(A))

Teorema 11.1.(Ford-Fulkerson)

Dada una red de transporte, fijados dos vértices s, t ∈ V, el (s,t)-flujo máximo coincide con la mínima capacidad de los (s,t)-cortes.

Demostración

Sea ft= (f0, f1, . . . , fm) el (s,t)-flujo máximo. Todos los arcos de la red ampliada se colorean con las siguientes reglas: col((t, s)) = N, col(u) = N, para todo u ∈ U tal que fu = 0, col(u) = V, para todo u ∈ U tal que fu = cu, col(u) = R, para todo u ∈ U tal que 0 0 por la regla de coloración elegida. Por consiguiente, esta opción no es compatible con la optimalidad del flujo f al ser posible incrementar f0 en la cantidad c(µ) > 0. Se da necesariamente, pues, la otra opción. (t, s) ∈θ(N −, V +) Este cociclo θ tiene sólo arcos negros y verdes, al estar todos los arcos coloreados. Sea θ = w(A) dicho cociclo, formado por arcos negros que entran en A, w −(A), y arcos verdes que salen de A, w +(A). Por la regla de etiquetado de vértices del lema de coloración y por el procedimiento de coloración de los arcos, se verifica que todos los arcos de w +(A) son verdes y todos los arcos de w −(A) son negros, de forma que el valor del flujo f0 verifica: f0 = ∑ fu con u ∈ w +(A) − ∑ fu con u ∈ w −(A) u ≠0 = ∑cu con u ∈ w +(A) − ∑ 0 con u ∈ w −(A) u ≠ 0 = ∑ cu con u ∈ w +(A) = c(w +(A)) De esta forma, se ha determinado el (s,t)-corte: w +(A) A = {v ∈ V / v etiquetado} cuya capacidad es mínima y coincide con el valor del (s,t)-flujo máximo.

Lema 10.1

Sea G = (V, U) un digrafo conexo cuyos arcos pueden estar (arbitrariamente) coloreados de negro N, verde V, rojo R o no estar coloreados 0. La única hipótesis es que uno de ellos, el arco de referencia u0, es negro. Se denota la clasificación de los arcos del digrafo por el vector col(): col : U −→ {N, V, R, 0} con la única restricción col(u0) = N. Entonces, se verifica una, y sólo una, de las dos aseveraciones siguientes: -Por el arco u0 pasa un ciclo elemental con los arcos coloreados de negro, verde o rojo. Los negros —el arco de referencia entre ellos— mantienen el sentido del ciclo, identificado por el sentido del arco de referencia; los verdes están orientados en sentido contrario; y, por último, los arcos rojos pueden estar orientados en cualquier sentido.- El arco u0 pertenece a un cociclo elemental formado por arcos negros, verdes o no coloreados. Los arcos negros mantienen el sentido del arco de referencia; los verdes están orientados en sentido contrario; y, por último, los arcos no coloreados pueden estar orientados en cualquier sentido.

Demostración

Sea u0 = (t, s) el arco de referencia. La demostración es constructiva y se basa en un proceso de etiquetado de vértices: 1. Etiquetar s: p(s) = s El resto de los vértices no está etiquetado p(j) = 0 ∀j ≠ s 2. Repetir este paso mientras se puedan etiquetar vértices: Dados un vértice i etiquetado (p(i) ≠0) y un vértice j no etiquetado (p(j) = 0) de forma que ambos son adyacentes en G: Etiquetar j, es decir p(j) = i si se verifica alguna de las condiciones siguientes: -u = (i, j) ∈ U y col(u) ∈ {N, R} . -u = (j, i) ∈ U y col(u) ∈ {V, R} Las cuatro posibilidades para etiquetar un vértice j a partir de otro adyacente i, ya etiquetado previamente, se ilustran en el DIBUJO COLORES.

Después del proceso de etiquetado, hay dos opciones exhaustivas y excluyentes: -p(t) ≠ 0 Se tiene construido el ciclo de arcos negros, rojos o verdes al unir el arco (t, s) con la cadena: t − p(t) − p(p(t)) − · · · − s. -p(t) = 0 El cociclo al que pertenece el arco u0 es w(A), siendo A = {i ∈ V / p(i) ≠0} Este cociclo, por construcción, verifica las hipótesis del lema.

Teorema 10.1.

Sea G = (V, U) un digrafo conexo con n vértices y m arcos. Dado H = (V, T), un árbol soporte de G, al añadir a T cualquier arco u ∈ U −T se forma un único ciclo elemental µ u en G, el sentido del ciclo es el del arco u, es decir, µ u u = 1. La base de flujos de G definida a partir de H es {µ u / u ∈ U − T}

Demostración

En primer lugar, el conjunto de ciclos elementales {µ u / u ∈ U − T} es independiente, puesto que cada uno de los ciclos µ u tiene un 1 en la componente asociada al arco u, mientras que el resto de ciclos µ u’ , con u’ ≠ u, tiene un 0 en la citada componente u-ésima. Para demostrar que este conjunto genera cualquier flujo, sea f un flujo. Se define un nuevo vector f’ = f − ∑ fuµ u con u∈U−T siendo fu la componente u-ésima del vector f. El vector f’ es un flujo, puesto que tiene tantas componentes como arcos el digrafo y verifica la ley de conservación de flujo por verificarla tanto el ciclo µ como cada uno de los ciclos µ u , con u ∈ U−T. Al considerar que las componentes de f’ se pueden clasificar en dos: u ∈ U − T Por construcción, el ciclo f’u = 0 u ∈ T El resto de las componentes, al ser H = (V, T) un árbol, por la proposición 10.1, deben ser nulas y f’u = 0.Por tanto, f’ = 0 y el flujo f se puede expresar como combinación lineal de la base de ciclos: f = ∑ fuµ u con u∈U−T

Teorema 3.2.

Dado un grafo G = (V, E) planar conexo con |V| = n vértices y |E| = m aristas, si r es el número de regiones determinadas por G, incluida la no acotada, se verifica la relación n + r = m + 2.

Demostración Se haría por inducción en m: m = 1 Hay dos opciones para un grafo planar conexo con 1 arista: • Una arista cuyos extremos coinciden e = {1, 1}. En este caso se verifica la relación al ser n = 1, m = 1 y r = 2 • Una arista con extremos distintos e = {1, 2}. En este caso se verifica también la relación al ser n = 2, m = 1 y r = 1 Cierto el teorema para m = k Un grafo con k aristas verifica n + r = k + 2. ¿m = k + 1? Sea G = (V, E) el grafo con n vértices, k + 1 aristas y r regiones. Hay dos posibilidades: • G tiene un vértice pendiente: a ∈ V tal que d(a) = 1. Sea Ga el subgrafo generado por V − {a}. Al ser a un vértice pendiente, Ga tiene n − 1 vértices, k aristas y mantiene el número de regiones r. Por la hipótesis de inducción, se verifica (n − 1) + r = k + 2 que es equivalente a n + r = (k + 1) + 2 que es lo que se quería demostrar. • G no tiene vértices pendientes: En este caso, y recordando que cualquier grafo no trivial sin vértices pendientes contiene al menos un ciclo µ ⊂ E, existe una arista {a, b} ∈ µ y que, por tanto, cierra una región finita cuyos bordes son las aristas del ciclo. Sea G a,b el grafo parcial obtenido al eliminar la arista {a, b}. Al disminuir en 1 el número de regiones de G a,b y tener k aristas, por la hipótesis de inducción, se verifica n + (r – 1) = k + 2 que es equivalente a n + r = (k + 1) + 2 que es lo que se quería demostrar.

Teorema 5.2.

 Las tres siguientes propiedades de un grafo G = (V, E), con |V | = n, son equivalentes: 1. G es un árbol 2. G tiene n − 1 aristas y no tiene ciclos. 3. G tiene n − 1 aristas y es conexo 

Demostración : 1 =⇒ 2 Se demuestra por inducción en n: • n = 1. Trivial, pues el grafo es el grafo formado por un único vértice. • n = k − 1. Se supone que un árbol de k − 1 vértices tiene k − 2 aristas. • n = k. Sea un grafo con k vértices. Por el teorema 5.1, al quitar una arista deja de ser conexo y se tienen dos componentes conexas, cada una de ellas con k1 y k2 vértices verificando 1 ≤ k1, k2 ≤ k −1 y k1 +k2 = k. Cada componente conexa es un árbol con menos de k − 1 vértices, por lo que al aplicar la hipótesis de inducción se tienen en cada una de ellas k1 − 1 y k2 − 1 aristas para totalizar k1 − k2 − 2 = k − 2 aristas, que al añadir la arista que se eliminó al principio, da un total de k − 1 aristas. 2 =⇒ 3 Se demuestra por inducción en n: • n = 1. Es trivial. • n = k − 1. Se supone que un grafo sin ciclos con k − 1 vértices y k − 2 aristas es conexo. • n = k. Sea un grafo con k vértices, k − 1 aristas y sin ciclos. Al no tener ciclos, existe un vértice x ∈ V pendiente. El subgrafo generado por V − {x} tiene k −1 vértices y no tiene ciclos; por lo que al aplicar la hipótesis de inducción es conexo y, por consiguiente, el grafo original G también lo es. 3 =⇒ 1 Hay que demostrar que un grafo conexo con n vértices y n − 1 aristas no contiene ciclos. Si contuviera un ciclo, el grafo parcial que resulta al quitar una arista del ciclo sería conexo y tendría n vértices y n − 2 aristas. La contradicción se ve en este grafo parcial, puesto que un grafo con n vértices y n − 2 aristas nunca puede ser conexo. •

Proposición 6.1. El algoritmo de Kruskal construye el árbol soporte de mínimo peso.

Demostración Sea T el subconjunto de aristas construido por el algoritmo. Sea S el subconjunto de aristas de un árbol de mínimo peso. En el caso en que T = S, ya está demostrada la proposición. En caso contrario, es decir, si T 6= S, por verificarse |T| = |S| = n − 1: Existe una arista e 1 verificando e 1 = {x 1 , y1 } ∈ T e1 6∈ S esta arista e 1 elegida es la primera de la lista ordenada por pesos verificando esta propiedad. Al ser S un árbol y e 1 6∈ S =⇒ ∃µ 1 S [x 1 , y1 ] ⊂ S . Esta cadena µ 1 S [x 1 , y1 ] formaría un único ciclo en S al añadir la arista e 1 . ∀e ∈ µ 1 S [x 1 , y1 ] se verifica d(e) ≤ d(e 1 ), puesto que en caso contrario, S no sería el árbol de peso mínimo. En µ 1 S [x 1 , y1 ] existe una arista e 2 = {x 2 , y2} que no pertenece a T, puesto que si todas las aristas de µ 1 S [x 1 , y1 ] ⊂ T habría un ciclo en T. Considerando que e 2 ∈ µ 1 S [x 1 , y1 ], d(e 2 ) ≤ d(e 1 ). La arista e 2 no puede estar delante de la arista e 1 en la lista ordenada asociada al algoritmo de Kruskal, puesto que en caso contrario: Si e 2 6∈ T es porque formaría un ciclo si se añadiera a T, existe por consiguiente una cadena µ 2 T [x 2 , y2 ] ⊂ T. Además, todas las aristas de µ 2 T están situadas en la lista del algoritmo antes que e 2 . Por definición de e 1 , al ser la primera arista de la lista incluida en T y no incluida en S, se deduce que µ 2 T [x 2 , y2 ] ⊂ S y la arista e 2 formaría un ciclo en S. Por consiguiente, la arista e 2 está después de la arista e 1 en la lista del algoritmo y d(e 2 ) ≥ d(e 1 ). Se concluye así que d(e 2 ) = d(e 1 ). Sea S 0 = S ∪ {e 1} − {e 2}. Este árbol es también de peso mínimo al verificar d(S 0 ) = d(S) y tiene una arista más en común con T que S. El proceso se repite S → S’→ S»→ · · · → S ^k hasta concluir que d(S) = d(S’) = · · · = d(S^k ) = d(T) y la proposición ha quedado demostrada. •

Teorema 5.3. Sea G = (V, E) un grafo conexo con n vértices y m aristas. Dado H = (V, T), un árbol soporte de G, al añadir a T cualquier arista e ∈ E − T se forma un único ciclo elemental µ e en G. La base de ciclos de G definida a partir de T es {µ e / e ∈ E − T} de forma que cualquier ciclo de G se puede expresar como combinación de los ciclos de esta base. La dimensión de la base de ciclos de un grafo G se denomina número ciclomático y se denota por ν(G). Se tiene, por consiguiente, que ν(G) = m − (n − 1) si el grafo es conexo. Habrá tantas bases de ciclos como ´arboles soporte se puedan definir en G.

Teorema 6.1. Dado el grafo conexo G = (V, E), H = (V, T) es el árbol soporte de mínimo peso si y sólo si ∀e ∈ T se verifica d(e) ≤ d(e’ ) ∀e’ ∈ θ e , siendo θ e el cociclo definido en el teorema 5.4 a partir de la base asociada a T.

Teorema 7.1. Dado un digrafo H = (V, T) con n > 1 vértices, las siguientes afirmaciones son equivalentes: 1. H es una arborescencia (digrafo sin ciclos con una raíz r) 2. ∃r ∈ V del que parte un único camino al resto de los vértices 3. H es casi-fuertemente-conexo y es mínimo —en el sentido de la inclusión— con esa propiedad. 4. H es conexo y ∃r ∈ V al que no llega ningún arco y al resto de los vértices llega exactamente uno 5. H no tiene ciclos y ∃r ∈ V al que no llega ningún arco y al resto de los vértices llega exactamente uno 6. H es casi-fuertemente-conexo y no tiene ciclos 7. H es casi-fuertemente-conexo y tiene n − 1 arcos

Proposición 8.7. Dado un vector de dimensión n, (u1, . . . , un), se verifica que u ∈ B ⇐⇒ u ∈ P 

Demostración  ⇒ Por definición de los uj , se verifica que uj ≤ uk + dkj ∀(k, j) ∈ U y, por consiguiente, el vector u es una solución del problema P. Para ver que es la que maximiza la función objetivo u2 + · · · + un, se demuestra que no puede haber otra solución u 0 de P mejor, puesto que en este caso existe al menos un j ∈ {2, . . . , n} tal que uj’ > uj , o, lo que es equivalente, uj’= uj + δj con δj > 0. Sea p(j) el predecesor de j en la arborescencia asociada a las ecuaciones de Bellman, por lo que verifica uj = up(j) + dp(j)j y se verifica uj’ − up(j)’ ≤ dp(j)j ⇐⇒ uj + δj − up(j) − δp(j) ≤ dp(j)j donde up(j)’ = up(j) + δp(j) Se concluye así que δj ≤ δp(j) y δp(j) > 0. El proceso se itera a p(p(j)) hasta llegar a la raíz 1 y concluir que δ1 > 0, que contradice que u1’ = u1 + δ1 = u1 = 0. ⇐ Por ser uj − uk ≤ dkj ∀(k, j) ∈ U y ser dkj = ∞ ∀(k, j) 6∈ U se verifica siempre que uj ≤ uk + dkj ∀k 6= j, ∀j 6= 1 Además, uj alcanza la cota superior ∀j 6= 1. En caso contrario, sea un j tal que uj

Proposición 8.8. Sea la red (G = (V, U); {du, u ∈ U}). Supongamos que du ≥ 0, ∀u ∈ U. Entonces, el algoritmo de Dijkstra construye los caminos de longitud mínima.

Demostración: Sea la iteración del algoritmo donde se incluye el vértice k como vértice permanente. En ese instante, u p k = uk es la longitud del camino mínimo que va desde 1 a k utilizando, exclusivamente, vértices permanentes: Si existiera otro camino de longitud estrictamente menor, iría por vértices de P hasta llegar al vértice h, que sería el primero de los vértices transitorios. La longitud de este camino a través de h no puede ser inferior a u P k , ya que u P k ≤ u P h y desde el vértice h hasta el vértice k hay que sumar una cantidad no negativa, puesto que du ≥ 0 ∀u ∈ U. Por tanto, u P k es la longitud del camino mínimo que va desde 1 a k. Como en ninguna iteración se modifican las cantidades u P j para los vértices permanentes, cuando T = ∅ se han conseguido todos los caminos mínimos.

Proposición 10.1. Un flujo definido sobre un árbol —digrafo conexo sin ciclos— es necesariamente nulo. 

Demostración El árbol tiene n vértices y n−1 arcos. Existe al menos un vértice pendiente, sea x1 tal vértice. El arco que incide en este vértice, tanto si entra en o sale de x1, tiene un flujo nulo, puesto que no sale o no entra ningún otro arco en el vértice. Se repite el esquema para el subgrafo generado por V − {x1} y se concluye así que todos los arcos tienen un flujo nulo. •

Proposición 10.2. La combinación lineal de flujos es otro flujo.

Demostración Sea G = (V, U) un digrafo con m arcos. Sea {f 1 ,f 2 , . . . ,f k} un conjunto de flujos sobre G. Si se define el vector f = ∑λj f^j  con j=1, k  λj ∈ R ∀j ∈ {1, . . . k} Al ser f j un flujo sobre G para todo j, el vector f ∈ IRm al ser IRm un espacio vectorial. Además, cada flujo f j verifica la ley de conservación de flujo; por consiguiente:  ∑ fu  con  u∈w+(i)  =   ∑ con  u∈w+(i) de   ∑ λjfu^j con  j=1, k = ∑ con  u∈w-(i) de   ∑ λjfu^j con  j=1, k = ∑fu con  u∈w−(i) ∀i ∈ {1, . . . , n} concluyendo así que f verifica también la ley de conservación de flujo. Es, por tanto, un flujo definido sobre G. •

Proposición 10.3. Cualquier ciclo de un digrafo es un flujo.

Demostración Sea µ el vector asociado al ciclo. Obviamente, µ ∈ IRm. Hay que demostrar la ley de conservación de flujo en cada vértice:  ∑ µu con u∈w+(i)  = ∑ µu con u∈w-(i) ∀i ∈ {1, . . . , n} Sea i ∈ V un vértice genérico de G. Si el vértice no es visitado por el ciclo, todos los arcos que inciden en él, exterior o interiormente, tienen asignado el valor 0 en el vector µ, por lo que se verifica trivialmente la ley de conservación de flujo en el vértice al ser µu = 0 ∀u ∈ w(i). Si el vértice i es visitado por el ciclo una vez, las tres posibilidades de conexión de los dos arcos u^1 y u^2 que inciden en el vértice i son: u^1 ∈ w +(i), u^2 ∈ w −(i) Dependiendo del sentido del ciclo, hay dos posibilidades: • µu1 = µu2 = 1 • µu1 = µu2 = −1 En ambos casos,  ∑µu = µu1 = 1(−1)  con u∈w+(i) y ∑µu = µu2 = 1(−1)  con u∈w-(i) y coinciden. Para u^1 , u^2 ∈ w +(i) En este caso, si uno de ellos, por ejemplo, µu1 = 1, el otro debe ser negativo µu2 = −1 y se verifica ∑µu = µu1 + µu2 = 1 − 1  con u∈w+(i) y   ∑µu = 0 con u∈w-(i). Para u1 , u2 ∈ w −(i) Este caso es análogo al anterior; verifica ∑µu = µu1 + µu2 = 1 − 1  con u∈w-(i) y   ∑µu = 0 con u∈w+(i). En el caso en que el ciclo no sea elemental y pueda visitar más de una vez un vértice, habrá que reiterar el proceso anterior tantas veces como sea visitado el vértice para concluir la ley de conservación para todos los vértices. •