8
Teorema del Flujo Máximo/ Minimo
DEFINICIÓN
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”
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
Teorema del flujo mínimo. En lo que respecta a las redes, un corte es un conjunto de corte en el cual quedando partes disjuntas del conjunto de vértices, V1 y V2 que, situados en la red, dejan la fuente en una de ellas y al sumidero en la otra. Se llama capacidad de un corte a la suma: Capacidad (v,w) ; vV1, w?V2 V1es la parte que contiene a la fuente V2 es la parte que contiene al sumidero Sea F un flujo en G y sea (P, P) un corte en G. Entonces la capacidad de (p, p) es mayor o igual que el valor de F.
Las Redes de Petri son grafos bipartidos que consisten de tres tipos de objetos:
Lugares.
Transiciones.
Arcos orientados
Un lugar se puede unir mediante un arco con una transición, y una transición se puede unir con un lugar también mediante un arco, pero nunca se podrán unir mediante un arco dos lugares o dos transiciones.
Regla de evolución. Un lugar P es un lugar de entrada de una transición T si existe un arco orientado que conecta este lugar a la transición. Un lugar P es un lugar de salida de una transición T si existe un arco orientado que conecta esta transición al lugar.
Cada lugar puede tener una marca (token) que indica cuando la condición asociada con este lugar es falsa o verdadera. En cualquier instante de tiempo, la distribución de lugares, llamado marcado de Petri define el estado del modelo. El marcado de una red de Petri es denotado por un vector M(p) de mx1 que representa el número de marcas en los lugares correspondientes. En el ejemplo M=[1,0,0,0,0]´
Matching (PAREO)
Definición
Dado un grafo, un pareo es un subconjunto de aristas los cuales no tiene vértices en común.
Pareo maximal
Un pareo maximal es un pareo que contiene el máximo número de aristas posibles, minimizando así el número de vértices sin unir. En el mejor de los casos, el pareo maximal contendrá a lo sumo V/2 aristas.
En el ej. anterior, el pareo maximal podría ser: AB DF EG HI LM JK
Grafo bipartido
Se dice que G = {V, E} es un grafo bipartido si se cumple que:
pareo maximal: A J2 B J5 C J3
Problema de pareja estable (Grafo Bipartido Pesado)
Asumimos que existen 2 grupos de N hombres y N mujeres cada uno. Cada hombre debe hacer una lista de preferencias sobre las mujeres y viceversa.
El problema seria encontrar N parejas respetando sus preferencias lo mas posible.
Llamaremos pareja no estable, cuando dos personas que no están en pareja se pretenden a la pareja que se les asigno.
REFERENCIAS:
https://www.trabajoinvestigacion.com/materias/redes-matematicas-discretas/0
https://matesdiscretasisc.blogspot.com/2014/12/65-redes.html
http://www.dspace.espol.edu.ec/retrieve/2769/DMD7_Redes_y_redes_petri.pdf
https://mate-discretasj2.blogspot.com/p/blog-page.html