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

- http://en.wikipedia.org/wiki/Hopcroft–Karp_algorithm
- http://www.cse.iitb.ac.in/~sundar/cs435/lecture23.pdf
- http://stackoverflow.com/questions/6366516/how-does-the-hopcroft-karp-algorithm-work

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."

page revision: 3, last edited: 17 Sep 2012 17:57