Matching en grafos

Decimos que en un grafo existe matching cuando existe un conjunto de vértices que no tienen nodos en común. Es decir, si dado un grafo $G = (V, X)$ , podemos encontrar un subconjunto $M$ de $X$ , en el que suceda que todas las aristas $(e = (v \to w)) \in M$ cumplen que no va a haber otra en $M$ que contenga a $v$ o a $w$ , entonces en $G$ existe un matching, y ese matching es $M$ .

Llamamos cardinal de un matching a $| M |$ , es decir, la cantidad de parejas que se encuentran en nuestro conjunto.

Supongamos que tenemos un taller donde se construye de manera artesanal algun producto, no importa que exactamente. La construcción de dicho producto se divide en 4 tareas, a las que enumeraremos del 1 al 4. Por otro lado, tenemos 4 empleados, que representaremos con las letras de sus nombres (Amalia, Benito, Carmen y Damian). Dadas las capacidades de cada empleado (que fueron representadas en el grafo orientado de abajo), necesitamos determinar si podemos o no cumplir con la fabricación del producto de manera optima, esto es, haciendo que cada empleado haga un trabajo diferente simultaneamente. Es decir, queremos asignarle a cada empleado un unico trabajo, para maximizar la producción.

flowchart TD

nodeA((A))
nodeB((B))
nodeC((C))
nodeD((D))

node1((2))
node2((3))
node3((1))
node4((4))

nodeA --- node3
nodeA --- node1

nodeB --- node1
nodeB --- node2

nodeD --- node4
nodeD --- node1

nodeC --- node3
nodeC --- node4

Esto es un problema de matching: queremos encontrar un conjunto de vertices $M$ tal que cubramos todos los nodos, pero cada vertice no contenga el nodo de otro vertice en $M$ . Una posible solución podria ser:

flowchart TD

nodeA((A)):::pair1
nodeB((B)):::pair2
nodeC((C)):::pair3
nodeD((D)):::pair4

node1((2)):::pair4
node2((3)):::pair2
node3((1)):::pair1
node4((4)):::pair3

nodeA --- node3
nodeA --- node1

nodeB --- node1
nodeB --- node2

nodeD --- node4
nodeD --- node1

nodeC --- node3
nodeC --- node4

classDef pair1 stroke:#f00
linkStyle 0 stroke:#f00

classDef pair2 stroke:#0f0
linkStyle 3 stroke:#0f0

classDef pair3 stroke:#00f
linkStyle 7 stroke:#00f

classDef pair4 stroke:#f0f
linkStyle 5 stroke:#f0f

Este conjunto solución $M = {(A, 1), (B, 3), (C, 4), (D, 2)}$ es un posible matching para el grafo propuesto.

En particular, podemos buscar matching en cualquier tipo de grafo, pero es muy interesante el caso de los grafos bipartitos. Recordando, en estos grafos podemos separar los nodos en dos conjuntos, de modo que cada conjunto tiene nodos inconexos. En el ejemplo de arriba, el grafo es uno bipartito ya que claramente podriamos separar los nodos en ${A, B, C, D}$ y ${1, 2, 3, 4}$ .

Si queremos buscar el máximo cardinal de un posible matching $M$ para un grafo bipartito $G$ , podemos transformar a $G$ a una red agregando un nodo fuente $s$ y un nodo sumidero $t$ y utilizar el algoritmo Ford-Fulkerson.

En el ejemplo de arriba, lo primero que hariamos es transformar el grafo a una red, quedando de la siguiente forma:

flowchart TD

nodeS((s))
nodeT((t))

nodeA((A))
nodeB((B))
nodeC((C))
nodeD((D))

node1((2))
node2((3))
node3((1))
node4((4))

nodeS --- nodeA
nodeS --- nodeB
nodeS --- nodeC
nodeS --- nodeD

nodeA --- node3
nodeA --- node1

nodeB --- node1
nodeB --- node2

nodeD --- node4
nodeD --- node1

nodeC --- node3
nodeC --- node4

node1 --- nodeT
node2 --- nodeT
node3 --- nodeT
node4 --- nodeT

Ahora nuestro grafo es una red valida. Si corremos el algoritmo antes mencionado, podremos obtener el máximo flujo de esta red. Lo util radica en que este flujo máximo es igual al máximo cardinal de un posible matching sobre el grafo $G$ .

La complejidad del algoritmo no cambia en este caso, resultando identicamente en una complejidad final de $O (F | E |)$ , donde $F$ es el máximo cardinal del matching y $| E |$ es la cantidad de aristas.