ส่วนตัดต่ำสุด
Network Flow Problem
แก้ในทษฎีกราฟ Flow network หรือ transportation network เป็นกราฟแบบมีทิศทาง (Directed graph) ที่เส้นเชื่อมแต่ละเส้นนั้นจะมีค่าความจุ (Capacity) แต่ละเส้นเชื่อมจะรองรับ flow โดยปริมาณของ flow มีขนาดไม่เกินความจุ
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
ทฤษฎีกราฟการตัดขั้นต่ำ(Minimum cut)ของกราฟ เป็นการตัดการฟแบ่งออกเป็นสองส่วนย่อย
กราฟที่มี n จุด สามารถมีการตัดขั้นต่ำได้
บริเวณที่เต็มไปด้ว ไซเคิลอย่างง่ายจำนวน n จุดนี้มี minimum cuts.[1]
Minimum cut problem
แก้-นิยาม st-cut (cut) เป็นการแบง่โหนดออกเป็นเซต (A,B) ที่มี 𝑠 ∈ 𝐴และ 𝑡 ∈ 𝐵 นิยาม
-ความจุของ cut คือผลรวมความจุของเสน้เช่อืมทอ่ีอกจาก A ไป B
Min-cut problem คือหา cutที่มีความจุต่ำที่สุด
- ↑ https://www.youtube.com/watch?v=qatLFXKwsM0 www.vcharkarn.com/vcafe/185266