Posgrado
  1. Introducción al análisis real  1.1. Teoría de conjuntos y lógica en el análisis real  1.1.1. Conjuntos y operaciones en teoría de conjuntos y lógica en análisis real  1.1.2. Relaciones y funciones  1.1.3. Lógica y cuantificadores  1.1.4. Cardinalidad de conjuntos  1.2. Espacio métrico  1.2.1. Introducción a conjuntos abiertos y cerrados en espacios métricos  1.2.2. Convergencia de secuencias en un espacio métrico  1.2.3. Función continua en un espacio métrico  1.2.4. Compacidad y completitud en espacios métricos en análisis real  1.3. Secuencias y series  1.3.1. Convergencia de secuencias  1.3.2. Series infinitas  1.3.3. Convergencia uniforme  1.3.4. Serie de potencias  1.4. Discriminación  1.4.1. Teorema del valor medio  1.4.2. Serie de Taylor  1.4.3. Funciones de varias variables  1.4.4. Derivada parcial  1.5. Integración  1.5.1. Integración de Riemann y Lebesgue  1.5.2. Integrales impropias  1.5.3. Teoría de la medida: una herramienta fundamental en la integración  1.5.4. Teorema de Fubini  1.6. Análisis funcional  1.6.1. Comprendiendo los espacios de Banach  1.6.2. Espacios de Hilbert  1.6.3. Operadores en espacios  1.6.4. Teoría espectral
  2. Álgebra abstracta  2.1. Entendiendo los grupos en el álgebra abstracta  2.1.1. Definiciones y ejemplos de grupos en álgebra abstracta  2.1.2. Homomorfismos de grupos  2.1.3. Introducción a los subgrupos normales  2.1.4. Teorema de Sylow  2.2. Anillos y campos  2.2.1. Ideales y anillos cociente  2.2.2. Extensiones de campos  2.2.3. Teoría de Galois  2.2.4. Anillos de polinomios  2.3. Introducción a los módulos en álgebra abstracta  2.3.1. Homomorfismo de módulos  2.3.2. Módulos libres  2.3.3. Introducción a los productos tensoriales  2.3.4. Secuencia exacta en módulos  2.4. Álgebra lineal  2.4.1. Espacio vectorial  2.4.2. Autovalores y autovectores  2.4.3. Espacio de producto interior  2.4.4. Diagonalización
  3. Topología  3.1. Topología general  3.1.1. Conjuntos abiertos y cerrados  3.1.2. Compacidad y conexión  3.1.3. Mapas continuos  3.1.4. Axioma de separación  3.2. Topología algebraica  3.2.1. Comprensión de los grupos fundamentales en la topología algebraica  3.2.2. Homotopía y homología  3.2.3. Complejo simplicial  3.2.4. Secuencias exactas en homología  3.3. Topología diferencial  3.3.1. Comprendiendo las variedades en topología diferencial  3.3.2. Funcionamiento suave  3.3.3. Espacio tangente y cotangente  3.3.4. Fibrados vectoriales
  4. Ecuaciones diferenciales  4.1. Ecuación diferencial ordinaria  4.1.1. Ecuaciones de primer orden  4.1.2. Ecuaciones lineales de segundo orden  4.1.3. Sistemas de ecuaciones diferenciales  4.1.4. Análisis de estabilidad en ecuaciones diferenciales ordinarias  4.2. Ecuaciones en derivadas parciales  4.2.1. Clasificación de EDP  4.2.2. Entendiendo las series de Fourier en ecuaciones diferenciales parciales  4.2.3. Introducción a las funciones de Green  4.2.4. Método de caracterización  4.3. Sistemas dinámicos en ecuaciones diferenciales  4.3.1. Teoría de la sostenibilidad  4.3.2. Ciclos límite en sistemas dinámicos  4.3.3. Teoría del caos  4.3.4. Teoría de bifurcación
  5. Probabilidad y estadística  5.1. Teoría de la probabilidad  5.1.1. Variables aleatorias  5.1.2. Distribuciones de probabilidad  5.1.3. Ley de los grandes números  5.1.4. Teorema del límite central  5.2. Inferencia estadística  5.2.1. Pruebas de hipótesis  5.2.2. Intervalo de confianza  5.2.3. Métodos bayesianos  5.2.4. Estimación de máxima verosimilitud  5.3. Procesos estocásticos  5.3.1. Cadenas de Markov  5.3.2. Movimiento browniano  5.3.3. Comprendiendo los procesos de Poisson  5.3.4. Martingalas: Un estudio integral en probabilidad y estadística
  6. Análisis numérico  6.1. Soluciones numéricas de ecuaciones  6.1.1. Descubrimiento original  6.1.2. Métodos iterativos  6.1.3. Análisis de convergencia  6.1.4. Cotas de error en soluciones numéricas de ecuaciones  6.2. Álgebra lineal numérica  6.2.1. Factorización de matrices  6.2.2. Cálculo de valores propios  6.2.3. Matrices dispersas  6.2.4. Técnicas de preacondicionamiento  6.3. Integración y diferenciación numérica  6.3.1. Métodos de cuadratura  6.3.2. Introducción a las diferencias finitas  6.3.3. Análisis de errores en la integración y diferenciación numérica  6.3.4. Métodos adaptativos en integración y diferenciación numérica
  7. Análisis complejo  7.1. Números complejos  7.1.1. Forma polar  7.1.2. Conjugados complejos  7.1.3. Forma exponencial de los números complejos  7.1.4. Raíces de la unidad  7.2. Funciones analíticas  7.2.1. Ecuaciones de Cauchy–Riemann  7.2.2. Series de potencias  7.2.3. Mapeo conforme  7.2.4. Funciones armónicas  7.3. Integración en el plano complejo  7.3.1. Teorema de Cauchy  7.3.2. Teorema del residuo  7.3.3. Integración de contornos  7.3.4. Transformaciones integrales
  8. Lógica matemática y fundamentos  8.1. Lógica proposicional  8.1.1. Tablas de verdad  8.1.2. Equivalencia lógica en la lógica proposicional  8.1.3. Técnicas de demostración en lógica proposicional  8.1.4. Solución en lógica proposicional  8.2. Lógica de predicados  8.2.1. Cuantificadores en lógica de predicados  8.2.2. Sistemas formales en lógica de predicados  8.2.3. Integridad y solidez  8.2.4. Teoría de modelos  8.3. Teoría de conjuntos  8.3.1. Cardinalidad y ordinalidad  8.3.2. Sistemas axiomáticos  8.3.3. Comprender la teoría de conjuntos de Zermelo-Fraenkel  8.3.4. Fuerzas en la teoría de conjuntos
  9. Personalización  9.1. Programación lineal  9.1.1. Método simplex  9.1.2. Dualidad en la programación lineal  9.1.3. Análisis de sensibilidad en programación lineal  9.1.4. Métodos de punto interior  9.2. Programación no lineal  9.2.1. Descenso de gradiente  9.2.2. Multiplicadores de Lagrange  9.2.3. Optimización convexa  9.2.4. Programación cuadrática  9.3. Optimización Combinatoria  9.3.1. Algoritmos de grafos  9.3.2. Programación entera  9.3.3. Flujo de red  9.3.4. Algoritmos de aproximación
  10. Matemáticas discretas  10.1. Teoría de grafos  10.1.1. Representación de grafos  10.1.2. Llanura y color  10.1.3. Algoritmo de camino más corto  10.1.4. Flujo de red  10.2. Compañerismo  10.2.1. Permutación y combinación  10.2.2. Función generadora  10.2.3. Relación de recurrencia  10.2.4. Comprendiendo el Principio de Inclusión-Exclusión  10.3. Criptografía  10.3.1. Aplicaciones de la teoría de números en criptografía  10.3.2. Criptografía Simétrica y Asimétrica  10.3.3. RSA y criptografía de curvas elípticas  10.3.4. Criptografía post-cuántica

Posgrado → Matemáticas discretas → Teoría de grafos ↓


Flujo de red


En el campo de la teoría de grafos, los flujos de red emergen como métodos poderosos para comprender una variedad de problemas relacionados con redes y sistemas. Estos incluyen sistemas de transporte, redes de comunicación, redes eléctricas e incluso redes de computadoras. En su núcleo, la teoría del flujo de red se ocupa de encontrar la manera más eficiente de mover una cierta cantidad de datos a través de una red desde una fuente hasta un destino.

Conceptos básicos del flujo de red

Para entender el flujo de red, es mejor comprender primero qué es una red de flujo.

Red de flujo

La red de flujo es un grafo dirigido donde cada arista tiene una capacidad y cada arista recibe un flujo. Los flujos deben satisfacer las restricciones de capacidad de la red. La red de flujo tiene un nodo fuente s donde comienza el flujo y un nodo sumidero t donde se consume el flujo.

S T C(E)

En el diagrama anterior, se muestra una simple red de flujo. Hay un único camino desde la fuente s hasta el sumidero t que tiene capacidad c(e).

Valor del flujo

El valor del flujo f en una red de flujo es la cantidad total de flujo que va desde la fuente s hasta el sumidero t.

f = sum_{(s, u) in E} f(s, u) - sum_{(v, s) in E} f(v, s)

Esta fórmula ayuda a calcular el flujo desde la fuente, teniendo en cuenta el vector de entrada y salida.

Restricciones de capacidad

Para cada arista (u, v) en la red, el flujo f(u, v) debe ser menor o igual a su capacidad c(u, v).

0 ≤ f(u, v) ≤ c(u, v)

Conservación del flujo

La regla de conservación del flujo estipula que para cada nodo, excepto s y t, la cantidad de flujo entrante es igual a la cantidad de flujo saliente.

sum_{(v, u) in E} f(v, u) = sum_{(u, w) in E} f(u, w)

Ejemplo

Considera una red sencilla con tres nodos: una fuente s, un nodo intermedio u y un sumidero t:

S U T 4 5 3

Las capacidades de las aristas (s, t), (s, u) y (u, t) son 4, 5 y 3, respectivamente. El problema es maximizar el flujo de s a t.

Algoritmo de Edmonds–Karp

El algoritmo de Edmonds-Karp es una implementación del método de Ford-Fulkerson para calcular el flujo máximo en redes de flujo. Utiliza una búsqueda en amplitud (BFS) para encontrar caminos de aumento.

Pasos del algoritmo

1. Comienzar el flujo en f 0.
2. Mientras exista un camino de aumento utilizando BFS:
a. Encuentra el flujo máximo c_f(p) a lo largo del camino p.
b. Aumentar el flujo a lo largo del camino.
c. Actualizar las capacidades residuales a lo largo del camino.
3. Retorna el flujo f.

Funcionamiento del algoritmo

Utilicemos un ejemplo simple para ver cómo funciona el algoritmo.

S U V T W X 3 4 3 6 5 8

En este ejemplo, comienza realizando una búsqueda BFS desde la fuente s hasta el sumidero t. El BFS selecciona el camino s - u - v - t con una capacidad de cuello de botella de 3. Aumenta el flujo y actualiza la red. Después de repetir estos pasos, aumenta el flujo tanto como la red lo permita.

Conceptos de redes residuales

Las redes residuales juegan un papel fundamental en la realización de análisis y la búsqueda de caminos de mejora. Las redes residuales capturan la diferencia entre las capacidades originales y los valores actuales del flujo.

Capacidad residual

La arista (u, v) c_f(u, v) se calcula como:

c_f(u, v) = c(u, v) - f(u, v)

Además, si f(u, v) > 0, c_f(v, u) = f(u, v) Esto tiene en cuenta la posibilidad de reducir el flujo en las aristas hacia atrás, lo cual es importante para encontrar caminos de aumento.

Red residual

La red residual incluye únicamente aristas con capacidad residual positiva. Las aristas con capacidad residual cero no afectan el flujo y no se incluyen en esta red.

S U V T W X 0 1 2 0 1 5

En la red residual anterior, las líneas rojas representan aristas que tienen capacidad cero y, por lo tanto, no son utilizables en cálculos futuros.

Aplicaciones de flujo de red

Las aplicaciones de los flujos de red son amplias y se pueden utilizar para optimizar sistemas en contextos tanto tecnológicos como sociales.

1. Transporte y logística

La facilitación de la gestión de flotas y la optimización de la entrega de mercancías a menudo depende de cuán eficientemente se mueven los bienes en la red.

2. Tráfico de Internet

El enrutar y controlar paquetes de datos utiliza los principios del flujo de red para reducir la congestión en la red y garantizar comunicaciones confiables.

3. Sistema de suministro de agua

La gestión de sistemas de distribución de agua se basa en modelos de flujo de red para optimizar la asignación y satisfacer la demanda sin exceder la capacidad.

4. Distribución de energía

Para asegurar el suministro estable y el control sobre el flujo de la red eléctrica es necesario utilizar principios de flujo de red para evitar la sobrecarga de los circuitos.

Desafíos y limitaciones

A pesar de su utilidad, los flujos de red se ven a veces desafiados por la escalabilidad en redes extremadamente grandes y complejas, donde se deben emplear estimaciones mediante métodos heurísticos.

Complejidad computacional

Las computaciones con redes extremadamente grandes requieren recursos sustanciales, por lo que se deben priorizar algoritmos eficientes, como Edmonds-Karp.

Transformación dinámica de la red

Los ajustes en tiempo real en la infraestructura de la red, como aquellos causados por fallas o mantenimiento, requieren una reprogramación dinámica de modelos de flujo.

Para abordar estos problemas, los enfoques híbridos utilizan el aprendizaje automático para predecir cambios en la demanda y el suministro de la red y adaptarse en consecuencia.

Conclusión

En resumen, el estudio de los flujos de red combina belleza teórica con aplicaciones prácticas, utilizando la base matemática para resolver problemas del mundo real. Mediante el uso de algoritmos como Edmonds-Karp y el marco conceptual de las redes residuales, estamos mejor equipados para diseñar, analizar y optimizar la eficacia de los sistemas interconectados.


Posgrado → 10.1.4


U
username
0%
completado en Posgrado

← Anterior (10.1.3)
Algoritmo de camino más corto
Siguiente (10.2) →
Compañerismo

Comentarios 



Flujo de red

https://www.buddymath.com/g/10.1.4?bmal=es