5.4 Redes

Es una red G, el flujo máximo. Generalmente existen varios flujos con el mismo valor máximo. Para encontrar el flujo máximo consideremos un flujo inicial en cada arista igual a cero, después se determina un camino específico de la fuente al sumidero y se incrementa el flujo el flujo.

Si una arista está dirigida hacia la fuente decimos que esta arista está dirigida en forma impropia, en caso contrario está dirigida en forma propia.

Si se determina un camino P de la fuente al sumidero en donde cada arista de P está orientada en forma propia y el flujo en cada arista es menor que la capacidad de la arista, es posible aumentar el valor de flujo.

Es  posible incrementar el flujo en ciertos caminos de la fuente al sumidero que tenga aristas orientadas en forma impropia y propia. Sea P un camino de “a” a “z” y sea “x” un vértice en P que no sea ni “a” ni “z”

·         Ambas aristas están orientadas en forma propia e impropia, en este caso, si incrementamos el flujo en “, el flujo en la entrada en x seguirá siendo igual al flujo de salida de x.

·         Si incrementamos el flujo en e2 en “, debemos disminuir el flujo en e1 en ‘’ de modo que el flujo de entrada en x  siga siendo igual al flujo de salida en x

·         Es análogo en el caso b

·         Disminuimos el flujo en ambas aristas en ‘’. En cada caso las asignaciones resultantes de las aristas dan como resultado un flujo.

Para realizar estas alteraciones debemos tener un flujo menor  que la capacidad en una arista orientada en forma propia y un flujo distinto de cero en una arista orientada en forma impropia.

Teorema 2:

   seaP un camino de “a” a  ”z” en una red G tal que:

·         Para arista (i, j) de P, orientada en forma propia.

Fij<Cij

·         Para cada arista (i, j) de P, orientada en forma propia.

0< Fij

Se define

F’ij= si no existieran  caminos que concuerden con el teorema 2, el flujo es máximo, entonces se considera el algoritmo:

·         Iniciar con un flujo

·         Buscar un camino que satisfaga con las condiciones del teorema 2

·         Si no existe el camino el flijo es máximo

·         Se incrementa el flujo en ‘’, y se regresa a línea 2

A dicho algoritmo se le llama algoritmo etiquetado.

  Teorema de Flujo Máximo

  Definición

Una red de transporte es una grafica dirigida, simple, con peso y que debe cumplir las siguientes:

·         Poseer una fuente o vértice fijo que no tiene aristas de entrada.

·         Poseer un sumidero o vértice fijo que no tiene arista de salida.

·         El peso Cij, es la arista dirigida de i a j llamado capacidad de “ij” es un número no negativo.

Una red de transporte, es una grafica dirigida, simple con peso que satisface:

·         Un vértice fijo, designado como el origen o fuente, no tiene aristas de entrada.

·         Un vértice, designado como destino o sumidero, no tiene aristas salientes.

·         El peso Cij de la arista dirigida (i, j) llamada capacidad de (i, j) es un número no negativo

  Redes de Petri

Ejemplo

En una grafica dirigida G= (V, E) donde V= PUT y P’’T=, cualquier arista en E es incidente en un miembro de P y un miembro de T, el conjunto P es el conjunto de lugares y el conjunto T es un conjunto de transiciones.

Un “marcado de red petri” asigna a cada lugar un entero no negativo, una red de petri con un marcado es una “red de petri marcada” (o simplemente una red petri).

Con un marcado se asigna al valor no negativo n al lugar P, decimos que existe n elementos en P, mediante los elementos a representar con los puntos.

Los lugares representan condiciones, las transiciones representan eventos, y la presencia de al menos un elemento en un lugar (condición) indica que tal condición se cumple.

Grafos Isomorfos

Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.

Grafos Platónicos

Son los Grafos formados por los vértices y aristas de los cinco  sólidos regulares      (Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro

Grafos conexos

Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: “un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une”.

Grafos dirigido (bigrafo)

  A un grafo dirigido se le puede definir como un grafo que contiene aristas dirigidas, como en el siguiente caso.