¿Qué son las funciones coincidentes?
Emparejamiento (primero explique lo que descubrió Baidu):
Empareja pǐpèi
(1) Conviértase en pareja
(2) Coopere; Clasificación o disposición en pares o grupos
(3) Coordinación [componentes de radio, etc.]
(4) Coincidencia de impedancia
(5) [Computadora] Dado un gráfico bipartito G, en un subgrafo M de G, si dos aristas cualesquiera en el conjunto de aristas de M no están unidas al mismo vértice, entonces M se denomina coincidencia.
Coincidencia de gráficos
[Editar este párrafo] Concepto
1 Definición de gráfico
Gráfico no dirigido: gráfico no dirigido G Se refiere a. el grupo binario (VG, EG) compuesto por un conjunto finito no vacío VG y un conjunto EG de pares desordenados de ciertos elementos en VG. VG se llama conjunto de vértices de G, y sus elementos se llaman vértices de G. EG se llama conjunto de aristas de g, y los elementos que contiene se llaman aristas de g. Sin confusión, a veces se registra que v =. VG, e = ej. Si V = {V1,…,VN}, entonces el elemento E en E corresponde al par desordenado (vi, vj) formado por dos elementos en V, el cual se registra como E = VIVJ o E = VJVI. Al analizar problemas, generalmente podemos usar círculos pequeños para representar vértices y líneas circulares pequeñas para representar aristas.
Gráfico bipartito: Sea G un gráfico. Si VG tiene una partición X, Y tal que un punto final de cada lado de G está en X y el otro punto final está en Y, entonces G se llama gráfico bipartito, G = (x, Y, e). Si cada vértice de X en G es adyacente a cada vértice de Y, entonces G se llama gráfico bipartito completo.
2. Conceptos relacionados de coincidencia
Supongamos que G = (v, e) es un gráfico. Si M no contiene un ciclo y dos lados cualesquiera no son adyacentes, entonces M es. llamado Una coincidencia de G. La coincidencia con el mayor número de aristas en G se llama la coincidencia máxima de G.
Para el gráfico g = (v, e), dale a cada arista e un peso real w(e). Supongamos que m es una coincidencia de G. Defina y llámelo el peso de la coincidencia m. La coincidencia con el peso más grande en G se llama coincidencia de peso máxima de G. Si para todo, e∈E, w (e) = 1, entonces la coincidencia de G La coincidencia de peso máximo es la coincidencia máxima de G.
Supongamos que m es la coincidencia del gráfico G = (V, E), vi ∈ v. Si vi está asociado con una arista en m, entonces se dice que vi es el punto de saturación de m; se llama inconsistencia de m punto de saturación.
Si cada vértice en G es un punto de saturación de M, entonces se dice que M es una coincidencia perfecta de G.
Supongamos que M es una coincidencia de g y P es una coincidencia de g. Una cadena, si un borde de P es alternativamente un borde en M y el otro no es un borde en M, entonces P se llama cadena escalonada en M. De manera similar, podemos definir el ciclo de intersección de G, y es fácil saber que el ciclo de intersección de G debe ser un ciclo par.
La cadena M-escalonada que conecta dos puntos M-insaturados diferentes se llama cadena M-aumentante.
La operación XOR de dos conjuntos S1 y S2 S1⊕S2 significa que el conjunto s 1⊕S2 = (s 1∪S2)\(s 1∪S2).
Es fácil ver que si m es una coincidencia de g y p es una cadena aumentada de m en g, entonces M⊕P también es una coincidencia de g, y.
Gráfico 1 Operación XOR
Se puede demostrar que la coincidencia M en G es la coincidencia máxima si y sólo si no hay cadenas de aumento M en G..
Algoritmo de coincidencia
1. Coincidencia máxima del gráfico bipartito
Hay m trabajadores x 1, x2,..., xm, n trabajos y 1, y2,.. ., yn, estipulado Cada trabajador puede realizar como máximo un trabajo, y a cada trabajo se le puede asignar como máximo un trabajador. Por diversas razones, cada trabajador sólo puede estar calificado para una o más de ellas. Pregunte cómo distribuir el trabajo de modo que al mayor número posible de trabajadores se les puedan asignar trabajos para los que estén calificados. Este problema se llama problema de asignación de personal.
Los problemas de personal se pueden expresar en el lenguaje de los gráficos.
Supongamos ≤i≤m, 1≤j≤n, si y sólo si el trabajador está calificado para el trabajo yi y tiene una ventaja en G, entonces el problema de asignación de personal se convierte en un problema de encontrar la máxima coincidencia en G
El algoritmo húngaro se usa a menudo para encontrar la coincidencia máxima. Su idea básica es: para una coincidencia conocida M, a partir de M puntos insaturados seleccionados arbitrariamente en X, use el método de etiquetado para encontrar M cadenas de aumento. Si se encuentra la cadena aumentada de m, entonces m se puede aumentar; de lo contrario, comenzando desde otro punto m-insaturado en x, continúe encontrando la cadena m-aumentadora. Repita este proceso hasta que no haya ninguna cadena de aumento en G. La coincidencia en este momento es la coincidencia máxima de G. Este algoritmo a menudo se denomina algoritmo húngaro porque el método de etiquetado para encontrar cadenas de aumento presentado aquí fue propuesto por primera vez por el dentista húngaro Egerváry. .
Gráfico 2 Algoritmo húngaro
Después de comprender este algoritmo, no es difícil escribir una solución al problema de asignación de personal. Antes de dar el programa, haga algunas suposiciones:
Para simplificar, suponga que el número de trabajadores es igual al número de puestos de trabajo, es decir, N=M y N≤100. Aquí, n también puede considerarse como |X| y |Y| del gráfico bipartito.
Lea los datos del archivo input.txt, comenzando con n y |E|, y hay dos números (I, J) en la siguiente línea |E|, lo que indica que el trabajador I está calificado para el trabajo. J. Es decir, la arista xiyj en el gráfico bipartito.
Los resultados se envían al archivo output.txt. La primera línea es el número máximo coincidente S, y las siguientes líneas S tienen dos números (I, J) en cada línea, lo que indica que el trabajador asignado. Estoy haciendo el trabajo J., es decir, haciendo coincidir el borde xiyj.
La siguiente es una solución de referencia al problema de asignación de personal. La complejidad temporal de este algoritmo es O (n3).
2. Coincidencia de peso máximo del gráfico bipartito
Para el problema de asignación de personal anterior, si también se tiene en cuenta la eficiencia laboral de los trabajadores, se puede plantear el llamado problema de asignación. : ¿Cómo asignar talentos para maximizar la eficiencia general?
Igual que en la sección anterior, podemos construir un gráfico bipartito G. Si la eficiencia wij de los trabajadores que realizan el trabajo yi se considera como el peso en G, entonces el problema de asignación es equivalente al gráfico bipartito ponderado G. Encontrar una coincidencia completa máxima en un gráfico bipartito G
Desde el conocimiento de la programación lineal, la coincidencia de peso máxima de un gráfico bipartito G se puede obtener mejorando solo ligeramente el algoritmo húngaro. La idea básica es numerar los vértices del gráfico bipartito, luego construir un nuevo gráfico bipartito G' basado en los números y finalmente convertir la coincidencia de peso máximo de G en la coincidencia perfecta de G'.
El siguiente teorema es la base teórica de este algoritmo.
Teorema: Sea la coincidencia perfecta de un gráfico bipartito completo de un gráfico ponderado (peso no negativo), aquí. Si hay un grupo que está satisfecho y lo tiene todo, es el de igualación de peso máximo.
A continuación se detalla el procedimiento para encontrar el peso máximo coincidente. En el archivo de entrada, hay n y |E| primero, y hay tres números (I, J, W) en la siguiente línea |E|, lo que indica que la eficiencia del trabajador I al realizar el trabajo J es W. El programa La producción incluye la selección de cada trabajador y el ingreso total final. Para otros supuestos, consulte los supuestos del algoritmo en la sección anterior. La complejidad temporal de este algoritmo también es O (n3).
3. Coincidencia de gráficos arbitrarios
El algoritmo de coincidencia máxima de cualquier gráfico también se basa en encontrar la cadena aumentada, pero la cadena aumentada de cualquier gráfico es más difícil que el gráfico bipartito. Encuentra más. Este algoritmo es relativamente complejo y rara vez se utiliza en competiciones, por lo que no se presentará en detalle aquí.