ปัญหาการไหลมากสุด

ปัญหาการไหลมากสุด เป็นปัญหาเกี่ยวกับการไหลในเครือข่ายที่ต้องการหาการไหล (เส้นทางน้ำไหน; flow) ซึ่งจะทำให้น้ำที่ไหลออกจากแหล่งต้นทาง (source) ผ่านท่อต่าง ๆ ไปยังแหล่งปลายทาง (sink) มีปริมาณมากที่สุด

ปัญหานี้อาจจะนับเป็นกรณีพิเศษของปัญหาการไหลหมุนเวียนที่ซับซ้อนยิ่งกว่า มีทฤษฎีบทที่สำคัญมากมายเกี่ยวกับปัญหาดังกล่าว หนึ่งในทฤษฎีบทที่เป็นที่รู้จักมากที่สุดคือทฤษฎีบทการไหลมากสุด-คัทต่ำสุดซึ่งกล่าวไว้ว่าปริมาณการไหลที่มากที่สุด (ซึ่งก็คือคำตอบของปัญหาการไหลมากสุด) จะเท่ากับคัทที่ต่ำที่สุด

 ประวัติ 

 นิยามปัญหา 

 วิธีแก้ไขปัญหา 

 ทฤษฎีบท 
 ทฤษฎีบทการไหลมากสุด-คัทต่ำสุด 
ทฤษฎีบทการไหลมากสุด-คัทต่ำสุด กล่าวไว้ว่าปริมาณการไหลที่มากที่สุด จะเท่ากับคัทที่ต่ำที่สุด ทฤษฎีบทนี้ยังเป็นฐานให้กับทฤษฎีบทอีกมากมายเช่นทฤษฎีบทเมนเกอร์

 ทฤษฎีบทการไหลที่เป็นจำนวนเต็ม 
ทฤษฎีบทการไหลที่เป็นจำนวนเต็ม กล่าวไว้ว่าถ้าท่อทั้งหมดมีความจุเป็นจำนวนเต็ม คำตอบของปัญหาการไหลมากสุดก็จะเป็นจำนวนเต็มด้วย

 การนำไปใช้ 
 ปัญหาการไหลมากสุดหลายแหล่งต้นทาง หลายแหล่งปลายทาง 

 ปัญหาการจับคู่มากสุด 

 ปัญหาการไหลมากสุดโดยจุดยอดมีความจุ 

หมวดหมู่:การไหลในเครือข่าย
หมวดหมู่:ปัญหาทางคณิตศาสตร์