Köşeleri en az kesmek - kenarları değil, kenarları değil

Question

hepimiz s-t minimal kesim algoritmalarını biliyor ve seviyoruz, ancak hepsi grafikteki kenarları kesiyorlar. Düğümleri kesen varyantlar var mı?

Answer 1

S-t minimum kesim algoritmasını kullanmak için grafiğinizi bir akış ağına dönüştürmeniz gerekir. Bu, dolaylı yönlendirilmiş bir grafik (bir kenarın ileri akışının yönü) verir. Grafiği, bunu çözmesi gereken bir şeye dönüştürmek için bu yönlendirilmiş gösterimi kullanabilirsiniz. Esas olarak, her köşe (V) (kaynak ve havuz hariç) iki köşeye dönüştürülür, A ve B olarak adlandırılır. A, V'nin tüm kenarlarını alır, B, V'nin tüm kenarlarını alır. Daha sonra A -> B kenarını maksimum sonsuzluk kapasitesiyle yaratırsınız.

Sanırım her zamanki s-t minimum kesim algoritmasını çalıştırırsanız, yalnızca oluşturduğunuz kenarları seçersiniz. Gerekli olduğunu düşündüğüm tek değişiklik, A derecesinin bir olduğu durumlarda, bu kenarı kesmek için seçebilir, ancak o zaman köşe olarak A'yı seçebilir. (Bu, s-t algoritmasının uygulanmasına bağlıdır)

Umarım bu mantıklıdır. Bunun işe yarayıp yaramadığına emin değilim (yani uygun bir kanıtı düşünmek istemiyorum), ancak sezgisel bir anlam ifade eder. Sahip olduğum sezgisel fikir, "non-vertex" bir kenar kestiğinizde, grafiğin bağlantısını kesmek için aynı etkiye sahip olduğundan, bir "köşe" kenarını da kesebilirsiniz.