Hapus jumlah minimum simpul untuk memutuskan grafik

Pertimbangkan grafik yang tidak diarahkan dengan sumber dan simpul wastafel. Kami ingin menghapus jumlah minimum simpul dalam grafik itu untuk memutuskan jalur apa pun antara sumber dan wastafel.

Bisakah kita melakukan ini menggunakan katakanlah algoritma max-flow, min-cut?

(Jawaban ini awalnya diberikan sebagai bagian dari pertanyaan, dengan tujuan untuk diverifikasi.)

Intuisi saya memberi tahu saya bahwa kita dapat menggunakan algoritma max-flow, min-cut untuk menyelesaikan masalah ini:

1. Ganti setiap tepi yang tidak terarah dengan sepasang tepi yang diarahkan.
2. Mengganti setiap vertex dengan dua simpul v di dan v keluar dihubungkan dengan tepi. semua tepi masuk v akan terhubung dengan v in , semua tepi keluar v akan terhubung dengan v out .$v$$v_\text{in}$$v_\text{out}$$v$$v_\text{in}$$v$$v_\text{out}$
3. Cobalah untuk menemukan minimum cut . Tepi M merujuk pada simpul yang perlu kita hapus.$M$$M$