ส่วนตัดต่ำสุด

Network Flow Problem

ในทษฎีกราฟ Flow network หรือ transportation network เป็นกราฟแบบมีทิศทาง (Directed graph) ที่เส้นเชื่อมแต่ละเส้นนั้นจะมีค่าความจุ (Capacity) แต่ละเส้นเชื่อมจะรองรับ flow โดยปริมาณของ flow มีขนาดไม่เกินความจุ

ทฤษฎีกราฟการตัดขั้นต่ำ(Minimum cut)ของกราฟ เป็นการตัดการฟแบ่งออกเป็นสองส่วนย่อย

จำนวนการตัดน้อยที่สุด

กราฟที่มี n จุด สามารถมีการตัดขั้นต่ำได้ ${\displaystyle {\binom {n}{2}}={\frac {n(n-1)}{2}}}$

บริเวณที่เต็มไปด้ว ไซเคิลอย่างง่ายจำนวน n จุดนี้มี ${\displaystyle {\frac {n(n-1)}{2}}}$ minimum cuts.^[1]

Minimum cut problem

-นิยาม st-cut (cut) เป็นการแบง่โหนดออกเป็นเซต (A,B) ที่มี 𝑠 ∈ 𝐴และ 𝑡 ∈ 𝐵 นิยาม

-ความจุของ cut คือผลรวมความจุของเสน้เช่อืมทอ่ีอกจาก A ไป B

${\displaystyle cap(A,B)={\begin{matrix}\sum &\\outofA&\end{matrix}}c(e)}$

Min-cut problem คือหา cutที่มีความจุต่ำที่สุด

[1]

1. https://www.youtube.com/watch?v=qatLFXKwsM0 www.vcharkarn.com/vcafe/185266