Algoritmo de Edmonds

Construir un grafico bipartito (los elementos de la izquierda están conectados solo a los elementos de la derecha por arcos, los elementos de la derecha no tienen conexión saliente) de modo que los elementos de la izquierda son las máquinas y los elementos de la derecha son las tareas a realizar . Los arcos son de capacidad 1 y costo según tabla de asignación. Si un flujo pasa por un borde (i, j), esto equivale a decir que la máquina i realiza la tarea j.

Para completar el gráfico bipartito y convertirlo en un problema de flujo, cada elemento de la izquierda se vincula como un vértice terminal a una fuente ficticia. Cada elemento de línea está vinculado como un vértice de origen a un pozo ficticio. Todos estos arcos tienen capacidad 1 y costo 0. Para resolver el problema de asignación, aplicamos un algoritmo de flujo maximo a un costo mínimo para el grafo bipartito construido.