Эрэлттэй урсгал¶

Энгийн урсгалын сүлжээнд ирмэгийн урсгал зөвхөн дээрээсээ багтаамж $c(e)$-ээр, доороосоо 0-ээр хязгаарлагдана. Энэ өгүүлэлд бид ирмэг бүрийн урсгал тодорхой хэмжээтэй байхыг нэмж шаардах урсгалын сүлжээг хэлэлцэнэ, өөрөөр хэлбэл бид урсгалыг доороос нь эрэлт функц $d(e)$-ээр хязгаарлана:

$$ d(e) \le f(e) \le c(e)$$

Тэгэхээр ирмэг бүр ирмэгийн дагуу дамжуулах ёстой хамгийн бага урсгалын утгатай болно.

Энэ нь энгийн урсгалын бодлогын ерөнхийлөлт юм, учир нь бүх ирмэг $e$-ийн хувьд $d(e) = 0$ гэж тохируулбал энгийн урсгалын сүлжээ гарна. Энгийн урсгалын сүлжээнд хүчинтэй урсгал олох нь туйлын энгийн болохыг анхаарна уу, зүгээр л $f(e) = 0$ гэж тохируулахад аль хэдийн хүчинтэй болно. Гэвч ирмэг бүрийн урсгал эрэлтийг хангах ёстой бол хүчинтэй урсгал олох нь гэнэт нэлээд төвөгтэй болно.

Бид хоёр бодлого авч үзнэ:

бүх хязгаарлалтыг хангах дурын урсгалыг олох
бүх хязгаарлалтыг хангах хамгийн бага урсгалыг олох

Дурын урсгалыг олох¶

Бид сүлжээнд дараах өөрчлөлтийг хийнэ. Бид шинэ эх $s'$ ба шинэ цорго $t'$, эх $s'$-ээс бусад орой бүр рүү шинэ ирмэг, орой бүрээс цорго $t'$ рүү шинэ ирмэг, мөн $t$-ээс $s$ рүү нэг ирмэг нэмнэ. Түүнчлэн бид шинэ багтаамжийн функц $c'$-г дараах байдлаар тодорхойлно:

$c'((s', v)) = \sum_{u \in V} d((u, v))$ for each edge $(s', v)$.
$c'((v, t')) = \sum_{w \in V} d((v, w))$ for each edge $(v, t')$.
$c'((u, v)) = c((u, v)) - d((u, v))$ for each edge $(u, v)$ in the old network.
$c'((t, s)) = \infty$

Хэрэв шинэ сүлжээ ханасан урсгалтай бол ($s'$-ээс гарах ирмэг бүр бүрэн дүүрсэн урсгал, энэ нь $t'$ рүү орох ирмэг бүр бүрэн дүүрсэнтэй эквивалент) эрэлттэй сүлжээ хүчинтэй урсгалтай бөгөөд бодит урсгалыг шинэ сүлжээнээс хялбархан сэргээж болно. Эс бөгөөс бүх нөхцөлийг хангах урсгал оршин байхгүй. Ханасан урсгал нь хамгийн их урсгал байх ёстой тул түүнийг Эдмондс-Карпын алгоритм эсвэл Түлхэх-дахин шошголох алгоритм зэрэг дурын хамгийн их урсгалын алгоритмаар олж болно.

Эдгээр хувиргалтын зөв байдлыг ойлгоход илүү хэцүү. Бид үүнийг дараах байдлаар бодож болно: $d(e) > 0$ байх ирмэг $e = (u, v)$ бүрийг анх хоёр ирмэгээр солино: нэг нь $d(i)$ багтаамжтай, нөгөө нь $c(i) - d(i)$ багтаамжтай. Бид эхний ирмэгийг ханадаг урсгалыг олохыг хүсэж байна (өөрөөр хэлбэл энэ ирмэгийн дагуух урсгал түүний багтаамжтай тэнцүү байх ёстой). Хоёр дахь ирмэг нь бага чухал — түүний багтаамжаас хэтрэхгүй л бол түүний дагуух урсгал ямар ч байж болно. Ханах ёстой ирмэг бүрийг авч үзээд бид дараах үйлдлийг гүйцэтгэнэ: бид шинэ эх $s'$-ээс түүний төгсгөл $v$ рүү ирмэг татаж, түүний эхлэл $u$-ээс шинэ цорго $t'$ рүү ирмэг татаж, ирмэгийг өөрийг нь хасаад хуучин цорго $t$-ээс хуучин эх $s$ рүү төгсгөлгүй багтаамжтай ирмэг татна. Эдгээр үйлдлээр бид энэ ирмэг ханасан гэдэг баримтыг загварчилна — $v$-ээс нэмэлт $d(e)$ урсгал гарах ба (бид үүнийг $v$ рүү зөв хэмжээний урсгал өгдөг шинэ эхээр загварчилна), $u$ мөн нэмэлт $d(e)$ урсгал түлхэнэ (гэхдээ хуучин ирмэгийн дагуу биш, энэ урсгал шууд шинэ цорго $t'$ руу очно). Анх $s - \dots - u - v - \dots t$ замын дагуу урсаж байсан $d(e)$ утгатай урсгал одоо $s' - v - \dots - t - s - \dots - u - t'$ гэсэн шинэ замаар явж болно. Шинэ сүлжээний тодорхойлолтод хялбарчилсан цорын ганц зүйл бол хэрэв энэ үйл ажиллагаа ижил оройн хосын хооронд олон ирмэг үүсгэсэн бол тэдгээрийг багтаамжийг нь нийлбэрлэн нэг ирмэг болгон нэгтгэсэн явдал юм.

Хамгийн бага урсгал¶

$\infty$ багтаамжтай $(t, s)$ ирмэгийн дагуу (хуучин цоргоос хуучин эх рүү) харгалзах хуучин сүлжээний бүхэл урсгал урсдагийг анхаарна уу. Өөрөөр хэлбэл энэ ирмэгийн багтаамж хуучин сүлжээний урсгалын утгад нөлөөлнө. Энэ ирмэгт хангалттай том багтаамж (өөрөөр хэлбэл $\infty$) өгснөөр хуучин сүлжээний урсгал хязгааргүй болно. Энэ ирмэгийг илүү бага багтаамжаар хязгаарласнаар урсгалын утга буурна. Гэвч хэрэв бид энэ ирмэгийг хэт бага утгаар хязгаарлавал сүлжээ ханасан шийдгүй болно, жишээ нь анхны сүлжээний харгалзах шийд ирмэгүүдийн эрэлтийг хангахгүй. Энд бүх хязгаарлалт хангагдсан хэвээр байх хамгийн бага утгыг олохын тулд хоёртын хайлт ашиглаж болох нь илэрхий. Энэ нь анхны сүлжээний хамгийн бага урсгалыг өгнө.