A solução deste problema requer conhecimento sobre teoria dos grafos. Explicarei alguns dos termos utilizados na resposta, porém um estudo mais aprofundado pode auxiliar na compreensão da solução.
Primeiro, é importante explicar em que consiste o problema analisado. Matching, ou emparelhamento, em grafos é um subconjunto de arestas, no qual nenhum par de vértices compartilha uma aresta. O maximum matching ou emparelhamento máximo, de um grafo é o pareamento com o maior número de arestas.
Por sua vez, um grafo bipartido é um grafo onde todos os vértices podem ser separados entre dois conjuntos disjuntos \(V\) e \(U\), de modo que todas as arestas do grafo possuam um vértice final em \(U\) e outro inicial em \(V\).
Um bom exemplo seria o de pessoas procurando empregos, temos um conjunto de pessoas, \(U\), que procuram trabalho, um conjunto \(V\). Cada pessoa aceitaria um ou mais trabalhos, mas não todos do conjunto \(V\), e apenas uma pessoa pode ser contratada para cada trabalho. O maior número de pessoas contratadas seria o maximum matching do problema.
Uma abordagem iterativa para a solução do problema de maximum matching é o algoritmo de Hopcroft Karp, que utilizarei na resolução. O algoritmo consiste na utilização de buscas em caminhos ampliados (augmenting paths, em inglês), onde aumentamos o matching por meio do encontro de caminhos ampliados, adicionando as arestas utilizando novos caminhos ampliados ainda não utilizados no matching.
Um caminho ampliado é uma sequência de arestas em um grafo, onde alternamos entre arestas que pertencem ao matching e que não pertencem ao matching, considerando que os caminhos começam em um vértice livre e terminam em um vértice livre. As imagens abaixo exemplificam o processo realizado pelo algoritmo.
Acima está o matching antes e depois da incorporação de um caminho ampliado e abaixo está o caminho ampliado utilizado.
Vamos agora ao código. Primeiro, importamos as bibliotecas que são necessárias para a demonstração gráfica do resultado:
import networkx as nx
import matplotlib.pyplot as plt
O código a seguir transforma a input, caso criada em lista, em dicionário, para o cálculo do resultado. A escrita em lista pode ser vantajosa pois torna mais fácil a visualização das conexões possíveis.
def MatrizToDict(matriz):
dict = {}
i = -1
for u in matriz:
i += 1
dict[i] = []
j = 0
while j < len(u):
if u[j] == 1:
dict[i].append(j)
j += 1
else:
j += 1
return dict
Podemos iniciar o algoritmo com um dicionário vazio, mas utilizamos um algoritmo greedy, ou seja, pareamos os vértices com os primeiros vértices livres encontrados, para acelerar o processo. Em seguida, encontramos o maximum matching por meio de caminhos ampliados. O código retorna o número máximo de matchings possível e uma das possibilidades desse matching (é possível que haja mais de uma).
def bipartiteMatch(graph):
#transforma listas em dicionários
if type(graph) == list:
graph = MatrizToDict(graph)
matching = {}
for u in graph:
for v in graph[u]:
if v not in matching:
matching[v] = u
break
while 1:
preds = {}
unmatched = []
pred = dict([(u,unmatched) for u in graph])
for v in matching:
del pred[matching[v]]
layer = list(pred)
while layer and not unmatched:
newLayer = {}
for u in layer:
for v in graph[u]:
if v not in preds:
newLayer.setdefault(v,[]).append(u)
layer = []
for v in newLayer:
preds[v] = newLayer[v]
if v in matching:
layer.append(matching[v])
pred[matching[v]] = v
else:
unmatched.append(v)
if not unmatched:
unlayered = {}
for u in graph:
for v in graph[u]:
if v not in preds:
unlayered[v] = None
return (len(matching), matching)
def recurse(v):
if v in preds:
L = preds[v]
del preds[v]
for u in L:
if u in pred:
pu = pred[u]
del pred[u]
if pu is unmatched or recurse(pu):
matching[v] = u
return 1
return 0
for v in unmatched: recurse(v)
Em seguida, utilizamos a biblioteca networkx, criada para a manipulação de grafos, para gerar a imagem do resultado. Ela é auxiliada pela biblioteca matplotlib para a criação da imagem final.
def MostrarGrafo(graph):
if type(graph) == dict:
b = max(i for v in graph.values() for i in v)
else:
b = len(graph[0])
matching = bipartiteMatch(graph)[1]
tuplas = [(k, str(v)) for k, v in matching.items()]
ladoa = [i for i in range(len(graph))]
ladob = [str(i) for i in range(b)]
G = nx.Graph()
G.add_nodes_from(ladoa, bipartite=0)
G.add_nodes_from(ladob, bipartite=1)
G.add_edges_from(tuplas)
pos = nx.bipartite_layout(G, ladoa)
nx.draw(G, pos=pos, with_labels=True)
return plt.show()
Temos aqui duas entradas diferentes, uma no formato lista e outra em dicionário, assim como os seus resultados de maximum matching.
grafo1 = [[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]]
grafo2 = { 0:[0], 1:[0,2], 2:[1,2,3], 3:[2], 4:[2] }
bipartiteMatch(grafo1)
(5, {1: 0, 0: 1, 2: 2, 3: 3, 5: 5})
bipartiteMatch(grafo2)
(3, {0: 0, 2: 1, 1: 2})
Agora, mostramos de forma gráfica os resultados:
MostrarGrafo(grafo1)
MostrarGrafo(grafo2)
REFERENCIAS:
http://csl.mtu.edu/cs4321/www/Lectures/Lecture%2022%20-%20Maximum%20Matching%20in%20Bipartite%20Graph.htm
https://www.baeldung.com/cs/augmenting-path#:~:text=Given%20a%20flow%20network%20%2C%20an,the%20source%20to%20the%20sink.
https://code.activestate.com/recipes/123641-hopcroft-karp-bipartite-matching/