Coincidencia bipartita máxima

Una coincidencia en un gráfico bipartito es un conjunto de aristas elegidas de tal manera que no hay dos aristas que compartan un punto final. Una coincidencia máxima es una coincidencia de tamaño máximo (número máximo de aristas). En un emparejamiento máximo, si se le añade alguna arista, deja de ser un emparejamiento. Puede haber más de una coincidencia máxima para un gráfico bipartito dado. 

¿Por qué nos importa?  
Hay muchos problemas del mundo real que se pueden formar como emparejamiento bipartito. Por ejemplo, considere el siguiente problema:

Hay M solicitantes de empleo y N trabajos. Cada solicitante tiene un subconjunto de trabajos en los que está interesado. Cada vacante de trabajo solo puede aceptar un solicitante y un solicitante de empleo puede ser designado para un solo trabajo. Encuentre una asignación de trabajos a los solicitantes de tal manera que la mayor cantidad posible de solicitantes obtengan trabajo”.

maximum_matching1

Recomendamos encarecidamente leer la siguiente publicación primero. » Algoritmo de Ford-Fulkerson para el problema de flujo
máximo» Emparejamiento bipartito máximo y problema de flujo máximo  :

El problema de coincidencia bipartita máxima ( MBP ) se puede resolver convirtiéndolo en una red de flujo (vea este video para saber cómo llegamos a esta conclusión). Los siguientes son los pasos.
 

maximum_matching2

1) Construya una red de flujo  : debe haber una fuente y un sumidero en una red de flujo. Entonces agregamos una fuente y agregamos bordes desde la fuente a todos los solicitantes. Del mismo modo, agregue bordes de todos los trabajos para hundir. La capacidad de cada borde está marcada como 1 unidad.

maximum_matching2

2) Encuentre el flujo máximo: usamos el algoritmo de Ford-Fulkerson para encontrar el flujo máximo en la red de flujo construida en el paso 1. El flujo máximo es en realidad el MBP que estamos buscando.

¿Cómo implementar el enfoque anterior? 

Primero definamos formas de entrada y salida. La entrada tiene la forma de array de Edmonds, que es una array 2D ‘bpGraph[M][N]’ con M filas (para M solicitantes de empleo) y N columnas (para N trabajos). El valor bpGraph[i][j] es 1 si i-th solicitante está interesado en j-th trabajo, de lo contrario 0. 

La salida es el número máximo de personas que pueden conseguir trabajo. 

Una forma sencilla de implementar esto es crear una array que represente la representación de array de adyacencia de un gráfico dirigido con M+N+2 vértices. Llame a fordFulkerson() para la array. Esta implementación requiere O((M+N)*(M+N)) espacio extra. 

El espacio adicional se puede reducir y el código se puede simplificar usando el hecho de que el gráfico es bipartito y la capacidad de cada borde es 0 o 1. La idea es usar DFS transversal para encontrar un trabajo para un solicitante (similar a aumentar la ruta en Ford -Fulkerson). Llamamos a bpm() para cada solicitante, bpm() es la función basada en DFS que prueba todas las posibilidades para asignar un trabajo al solicitante.

En bpm(), probamos uno por uno todos los trabajos en los que está interesado un solicitante ‘u’ hasta que encontramos un trabajo, o todos los trabajos se prueban sin suerte. Para cada trabajo que intentamos, hacemos lo siguiente. 

Si un trabajo no está asignado a nadie, simplemente se lo asignamos al solicitante y devolvemos verdadero. Si un trabajo se asigna a otra persona, digamos x, entonces verificamos recursivamente si x se puede asignar a algún otro trabajo. Para asegurarnos de que x no obtenga el mismo trabajo nuevamente, marcamos el trabajo ‘v’ como se ve antes de hacer una llamada recursiva para x. Si x puede conseguir otro trabajo, cambiamos el solicitante del trabajo ‘v’ y devolvemos verdadero. Usamos una array maxR[0..N-1] que almacena los solicitantes asignados a diferentes trabajos.

Si bmp() devuelve verdadero, significa que hay una ruta de aumento en la red de flujo y se agrega 1 unidad de flujo al resultado en maxBPM(). 

Implementación:

C++

// A C++ program to find maximal
// Bipartite matching.
#include <iostream>
#include <string.h>
using namespace std;
 
// M is number of applicants
// and N is number of jobs
#define M 6
#define N 6
 
// A DFS based recursive function
// that returns true if a matching
// for vertex u is possible
bool bpm(bool bpGraph[M][N], int u,
         bool seen[], int matchR[])
{
    // Try every job one by one
    for (int v = 0; v < N; v++)
    {
        // If applicant u is interested in
        // job v and v is not visited
        if (bpGraph[u][v] && !seen[v])
        {
            // Mark v as visited
            seen[v] = true;
 
            // If job 'v' is not assigned to an
            // applicant OR previously assigned
            // applicant for job v (which is matchR[v])
            // has an alternate job available.
            // Since v is marked as visited in
            // the above line, matchR[v] in the following
            // recursive call will not get job 'v' again
            if (matchR[v] < 0 || bpm(bpGraph, matchR[v],
                                     seen, matchR))
            {
                matchR[v] = u;
                return true;
            }
        }
    }
    return false;
}
 
// Returns maximum number
// of matching from M to N
int maxBPM(bool bpGraph[M][N])
{
    // An array to keep track of the
    // applicants assigned to jobs.
    // The value of matchR[i] is the
    // applicant number assigned to job i,
    // the value -1 indicates nobody is
    // assigned.
    int matchR[N];
 
    // Initially all jobs are available
    memset(matchR, -1, sizeof(matchR));
 
    // Count of jobs assigned to applicants
    int result = 0;
    for (int u = 0; u < M; u++)
    {
        // Mark all jobs as not seen
        // for next applicant.
        bool seen[N];
        memset(seen, 0, sizeof(seen));
 
        // Find if the applicant 'u' can get a job
        if (bpm(bpGraph, u, seen, matchR))
            result++;
    }
    return result;
}
 
// Driver Code
int main()
{
    // Let us create a bpGraph
    // shown in the above example
    bool bpGraph[M][N] = {{0, 1, 1, 0, 0, 0},
                          {1, 0, 0, 1, 0, 0},
                          {0, 0, 1, 0, 0, 0},
                          {0, 0, 1, 1, 0, 0},
                          {0, 0, 0, 0, 0, 0},
                          {0, 0, 0, 0, 0, 1}};
 
    cout << "Maximum number of applicants that can get job is "
         << maxBPM(bpGraph);
 
    return 0;
}

Java

// A Java program to find maximal
// Bipartite matching.
import java.util.*;
import java.lang.*;
import java.io.*;
 
class GFG
{
    // M is number of applicants
    // and N is number of jobs
    static final int M = 6;
    static final int N = 6;
 
    // A DFS based recursive function that
    // returns true if a matching for
    // vertex u is possible
    boolean bpm(boolean bpGraph[][], int u,
                boolean seen[], int matchR[])
    {
        // Try every job one by one
        for (int v = 0; v < N; v++)
        {
            // If applicant u is interested
            // in job v and v is not visited
            if (bpGraph[u][v] && !seen[v])
            {
                 
                // Mark v as visited
                seen[v] = true;
 
                // If job 'v' is not assigned to
                // an applicant OR previously
                // assigned applicant for job v (which
                // is matchR[v]) has an alternate job available.
                // Since v is marked as visited in the
                // above line, matchR[v] in the following
                // recursive call will not get job 'v' again
                if (matchR[v] < 0 || bpm(bpGraph, matchR[v],
                                         seen, matchR))
                {
                    matchR[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
 
    // Returns maximum number
    // of matching from M to N
    int maxBPM(boolean bpGraph[][])
    {
        // An array to keep track of the
        // applicants assigned to jobs.
        // The value of matchR[i] is the
        // applicant number assigned to job i,
        // the value -1 indicates nobody is assigned.
        int matchR[] = new int[N];
 
        // Initially all jobs are available
        for(int i = 0; i < N; ++i)
            matchR[i] = -1;
 
        // Count of jobs assigned to applicants
        int result = 0;
        for (int u = 0; u < M; u++)
        {
            // Mark all jobs as not seen
            // for next applicant.
            boolean seen[] =new boolean[N] ;
            for(int i = 0; i < N; ++i)
                seen[i] = false;
 
            // Find if the applicant 'u' can get a job
            if (bpm(bpGraph, u, seen, matchR))
                result++;
        }
        return result;
    }
 
    // Driver Code
    public static void main (String[] args)
                       throws java.lang.Exception
    {
        // Let us create a bpGraph shown
        // in the above example
        boolean bpGraph[][] = new boolean[][]{
                              {false, true, true,
                               false, false, false},
                              {true, false, false,
                               true, false, false},
                              {false, false, true,
                               false, false, false},
                              {false, false, true,
                               true, false, false},
                              {false, false, false,
                               false, false, false},
                              {false, false, false,
                               false, false, true}};
        GFG m = new GFG();
        System.out.println( "Maximum number of applicants that can"+
                            " get job is "+m.maxBPM(bpGraph));
    }
}

Python3

# Python program to find
# maximal Bipartite matching.
 
class GFG:
    def __init__(self,graph):
         
        # residual graph
        self.graph = graph
        self.ppl = len(graph)
        self.jobs = len(graph[0])
 
    # A DFS based recursive function
    # that returns true if a matching
    # for vertex u is possible
    def bpm(self, u, matchR, seen):
 
        # Try every job one by one
        for v in range(self.jobs):
 
            # If applicant u is interested
            # in job v and v is not seen
            if self.graph[u][v] and seen[v] == False:
                 
                # Mark v as visited
                seen[v] = True
 
                '''If job 'v' is not assigned to
                   an applicant OR previously assigned
                   applicant for job v (which is matchR[v])
                   has an alternate job available.
                   Since v is marked as visited in the
                   above line, matchR[v]  in the following
                   recursive call will not get job 'v' again'''
                if matchR[v] == -1 or self.bpm(matchR[v],
                                               matchR, seen):
                    matchR[v] = u
                    return True
        return False
 
    # Returns maximum number of matching
    def maxBPM(self):
        '''An array to keep track of the
           applicants assigned to jobs.
           The value of matchR[i] is the
           applicant number assigned to job i,
           the value -1 indicates nobody is assigned.'''
        matchR = [-1] * self.jobs
         
        # Count of jobs assigned to applicants
        result = 0
        for i in range(self.ppl):
             
            # Mark all jobs as not seen for next applicant.
            seen = [False] * self.jobs
             
            # Find if the applicant 'u' can get a job
            if self.bpm(i, matchR, seen):
                result += 1
        return result
 
 
bpGraph =[[0, 1, 1, 0, 0, 0],
          [1, 0, 0, 1, 0, 0],
          [0, 0, 1, 0, 0, 0],
          [0, 0, 1, 1, 0, 0],
          [0, 0, 0, 0, 0, 0],
          [0, 0, 0, 0, 0, 1]]
 
g = GFG(bpGraph)
 
print ("Maximum number of applicants that can get job is %d " % g.maxBPM())
 
# This code is contributed by Neelam Yadav

C#

// A C# program to find maximal
// Bipartite matching.
using System;
 
class GFG
{
    // M is number of applicants
    // and N is number of jobs
    static int M = 6;
    static int N = 6;
 
    // A DFS based recursive function
    // that returns true if a matching
    // for vertex u is possible
    bool bpm(bool [,]bpGraph, int u,
             bool []seen, int []matchR)
    {
        // Try every job one by one
        for (int v = 0; v < N; v++)
        {
            // If applicant u is interested
            // in job v and v is not visited
            if (bpGraph[u, v] && !seen[v])
            {
                // Mark v as visited
                seen[v] = true;
 
                // If job 'v' is not assigned to
                // an applicant OR previously assigned
                // applicant for job v (which is matchR[v])
                // has an alternate job available.
                // Since v is marked as visited in the above
                // line, matchR[v] in the following recursive
                // call will not get job 'v' again
                if (matchR[v] < 0 || bpm(bpGraph, matchR[v],
                                         seen, matchR))
                {
                    matchR[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
 
    // Returns maximum number of
    // matching from M to N
    int maxBPM(bool [,]bpGraph)
    {
        // An array to keep track of the
        // applicants assigned to jobs.
        // The value of matchR[i] is the
        // applicant number assigned to job i,
        // the value -1 indicates nobody is assigned.
        int []matchR = new int[N];
 
        // Initially all jobs are available
        for(int i = 0; i < N; ++i)
            matchR[i] = -1;
 
        // Count of jobs assigned to applicants
        int result = 0;
        for (int u = 0; u < M; u++)
        {
            // Mark all jobs as not
            // seen for next applicant.
            bool []seen = new bool[N] ;
            for(int i = 0; i < N; ++i)
                seen[i] = false;
 
            // Find if the applicant
            // 'u' can get a job
            if (bpm(bpGraph, u, seen, matchR))
                result++;
        }
        return result;
    }
 
    // Driver Code
    public static void Main ()
    {
        // Let us create a bpGraph shown
        // in the above example
        bool [,]bpGraph = new bool[,]
                          {{false, true, true,
                            false, false, false},
                           {true, false, false,
                            true, false, false},
                           {false, false, true,
                            false, false, false},
                           {false, false, true,
                            true, false, false},
                           {false, false, false,
                            false, false, false},
                           {false, false, false,
                            false, false, true}};
        GFG m = new GFG();
    Console.Write( "Maximum number of applicants that can"+
                            " get job is "+m.maxBPM(bpGraph));
    }
}
 
//This code is contributed by nitin mittal.

PHP

<?php
// A PHP program to find maximal
// Bipartite matching.
 
// M is number of applicants
// and N is number of jobs
$M = 6;
$N = 6;
 
// A DFS based recursive function
// that returns true if a matching
// for vertex u is possible
function bpm($bpGraph, $u, &$seen, &$matchR)
{
    global $N;
     
    // Try every job one by one
    for ($v = 0; $v < $N; $v++)
    {
        // If applicant u is interested in
        // job v and v is not visited
        if ($bpGraph[$u][$v] && !$seen[$v])
        {
            // Mark v as visited
            $seen[$v] = true;
 
            // If job 'v' is not assigned to an
            // applicant OR previously assigned
            // applicant for job v (which is matchR[v])
            // has an alternate job available.
            // Since v is marked as visited in
            // the above line, matchR[v] in the following
            // recursive call will not get job 'v' again
            if ($matchR[$v] < 0 || bpm($bpGraph, $matchR[$v],
                                    $seen, $matchR))
            {
                $matchR[$v] = $u;
                return true;
            }
        }
    }
    return false;
}
 
// Returns maximum number
// of matching from M to N
function maxBPM($bpGraph)
{
    global $N,$M;
     
    // An array to keep track of the
    // applicants assigned to jobs.
    // The value of matchR[i] is the
    // applicant number assigned to job i,
    // the value -1 indicates nobody is
    // assigned.
    $matchR = array_fill(0, $N, -1);
 
    // Initially all jobs are available
 
    // Count of jobs assigned to applicants
    $result = 0;
    for ($u = 0; $u < $M; $u++)
    {
        // Mark all jobs as not seen
        // for next applicant.
        $seen=array_fill(0, $N, false);
 
        // Find if the applicant 'u' can get a job
        if (bpm($bpGraph, $u, $seen, $matchR))
            $result++;
    }
    return $result;
}
 
// Driver Code
 
// Let us create a bpGraph
// shown in the above example
$bpGraph = array(array(0, 1, 1, 0, 0, 0),
                    array(1, 0, 0, 1, 0, 0),
                    array(0, 0, 1, 0, 0, 0),
                    array(0, 0, 1, 1, 0, 0),
                    array(0, 0, 0, 0, 0, 0),
                    array(0, 0, 0, 0, 0, 1));
 
echo "Maximum number of applicants that can get job is ".maxBPM($bpGraph);
 
 
// This code is contributed by chadan_jnu
?>

Javascript

<script>
 
    // A JavaScript program to find maximal
    // Bipartite matching.
     
    // M is number of applicants
    // and N is number of jobs
    let M = 6;
    let N = 6;
   
    // A DFS based recursive function that
    // returns true if a matching for
    // vertex u is possible
    function bpm(bpGraph, u, seen, matchR)
    {
        // Try every job one by one
        for (let v = 0; v < N; v++)
        {
            // If applicant u is interested
            // in job v and v is not visited
            if (bpGraph[u][v] && !seen[v])
            {
                   
                // Mark v as visited
                seen[v] = true;
   
                // If job 'v' is not assigned to
                // an applicant OR previously
                // assigned applicant for job v (which
                // is matchR[v]) has an alternate job available.
                // Since v is marked as visited in the
                // above line, matchR[v] in the following
                // recursive call will not get job 'v' again
                if (matchR[v] < 0 || bpm(bpGraph, matchR[v],
                                         seen, matchR))
                {
                    matchR[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
   
    // Returns maximum number
    // of matching from M to N
    function maxBPM(bpGraph)
    {
        // An array to keep track of the
        // applicants assigned to jobs.
        // The value of matchR[i] is the
        // applicant number assigned to job i,
        // the value -1 indicates nobody is assigned.
        let matchR = new Array(N);
   
        // Initially all jobs are available
        for(let i = 0; i < N; ++i)
            matchR[i] = -1;
   
        // Count of jobs assigned to applicants
        let result = 0;
        for (let u = 0; u < M; u++)
        {
            // Mark all jobs as not seen
            // for next applicant.
            let seen =new Array(N);
            for(let i = 0; i < N; ++i)
                seen[i] = false;
   
            // Find if the applicant 'u' can get a job
            if (bpm(bpGraph, u, seen, matchR))
                result++;
        }
        return result;
    }
     
    // Let us create a bpGraph shown
    // in the above example
    let bpGraph = [
      [false, true, true,
        false, false, false],
          [true, false, false,
            true, false, false],
              [false, false, true,
                false, false, false],
                  [false, false, true,
                    true, false, false],
                      [false, false, false,
                        false, false, false],
                          [false, false, false,
                            false, false, true]];
     
    document.write( "Maximum number of applicants that can"+
                       " get job is "+ maxBPM(bpGraph));
   
</script>
Producción

Maximum number of applicants that can get job is 5

También puede ver a continuación: 
Algoritmo de Hopcroft-Karp para coincidencia máxima | Conjunto 1 (Introducción)  
Algoritmo de Hopcroft-Karp para coincidencia máxima | Conjunto 2 (Implementación)

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *