56858b1bb91d031

http://nhiro.org.s3.amazonaws.com/2/c/2c4f2e550ef51194c1482485d153127f.jpg https://gyazo.com/2c4f2e550ef51194c1482485d153127f

(OCR text)

32

Vertex Cover

グラフを白黒2色で塗り分けて

「辺の少なくとも片方は黒である」

という条件を満たしつつ、

黒の頂点を最少にするにはどうしたらよいか。

「黒の頂点を最少にする」

という条件がなければ全部黒で塗ればいい

補足: