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



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

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

จำนวนการตัดน้อยที่สุด 
กราฟที่มี n จุด สามารถมีการตัดขั้นต่ำได้   

บริเวณที่เต็มไปด้ว ไซเคิลอย่างง่ายจำนวน n จุดนี้มี  minimum cuts.

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

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

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