ดูต้นฉบับสำหรับ ส่วนตัดต่ำสุด

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

{{ลิงก์ไปภาษาอื่น}}
ทฤษฎีกราฟการตัดขั้นต่ำ([[:en:Minimum_cut|Minimum cut]])ของกราฟ เป็นการตัดการฟแบ่งออกเป็นสองส่วนย่อย  

=== จำนวนการตัดน้อยที่สุ[[:en:Max-flow_min-cut_theorem|ด]] ===
กราฟที่มี n จุด สามารถมีการตัดขั้นต่ำได้ <math>\binom{n}{2} = \frac{n(n-1)}{2}</math>  

บริเวณที่เต็มไปด้ว ไซเคิลอย่างง่ายจำนวน n จุดนี้มี <math>\frac{n(n-1)}{2}</math> minimum cuts.<ref>https://www.youtube.com/watch?v=qatLFXKwsM0

www.vcharkarn.com/vcafe/185266</ref>

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

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

<math>cap(A,B) = \begin{matrix} \sum &  \\ out of A &  \end{matrix} c(e)</math>

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

[https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem]