Grafos Bipartidos

(Desculpem a bagunça de links e referências, depois eu arrumo direitinho)

Definição

http://en.wikipedia.org/wiki/Bipartite_graph

Maximum matching

Ou você pode modelar um fluxo (que tem complexidade equivalente ao Hopcroft-Karp se você usar o Dinic – http://en.wikipedia.org/wiki/Dinic%27s_algorithm)

Minimum Vertex Cover

Problemas:

Minha solução: http://pastebin.com/bpHNYTw8

Maximum Independent Set

http://en.wikipedia.org/wiki/Vertex_cover_problem – "A set of vertices is a vertex cover, if and only if its complement is an independent set."

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License