Instituto Tecnológico de Querétaro
Matemáticas Discretas
6.5 Redes
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
Teorema del Flujo Máximo
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.
Redes de Petri
Una red de petri, es un grafo dirigido bipartito, con un estado inicial, llamado “marcación inicial”. Los dos componentes principales de la red de petri son los sitios (también conocidos como estados) y las transiciones. Gráficamente, los sitios son dibujados con círculos y las transiciones como barras o rectángulos. Las aristas del grafo son conocidas como arcos. Estos tienen un peso específico, el cual es iniciado por un numero entero positivo, y van de sitio a transición y viceversa. Por simplicidad, el peso de los arcos no se indica cuando este es igual a 1.
Un arco que este etiquetado con K puede ser interpretado como K arcos paralelos.
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.
