El valor mínimo de la selección de cobertura en línea recta en el método húngaro

El valor mínimo de selección de cobertura de línea en el método húngaro: el número máximo de coincidencias en el gráfico bipartito = la cobertura mínima de puntos.

Comprensión de la cobertura mínima de puntos de un gráfico bipartito: encuentre el número mínimo de puntos para que todos los bordes del gráfico bipartito tengan al menos un punto final entre estos puntos. Por otro lado, todos los bordes se pueden eliminar eliminando los bordes que contienen estos puntos.

Cobertura mínima de puntos: seleccione el número mínimo de puntos de modo que se seleccione al menos un punto final de cualquier borde. Número máximo independiente: seleccione la mayor cantidad de puntos para que dos puntos seleccionados no estén conectados.

Cobertura mínima de ruta: Para DAG (gráfico acíclico dirigido), seleccione el número mínimo de rutas para que cada vértice pertenezca a una sola ruta. La longitud del camino puede ser 0 (es decir, un solo punto).

Hungría

El algoritmo húngaro es un algoritmo que utiliza rutas de aumento para encontrar la coincidencia máxima de gráficos bipartitos. Su núcleo es encontrar rutas de aumento. El algoritmo húngaro es un algoritmo de optimización combinatoria que resuelve el problema de asignación de tareas en el problema P (tiempo polinómico). Promovió el posterior método primitivo de la dualidad.

El algoritmo húngaro fue propuesto por el matemático estadounidense Harold Kuhn en 1955. Este algoritmo se llama algoritmo húngaro porque gran parte de él está basado en el ex matemático húngaro Dénes K? ¿Negro y Jane? Basado en la obra de Egervari.