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

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

ตัวอย่างของเครือข่ายการไหลซึ่งมีการไหลมากสุด แหล่งต้นทางคือ s และแหล่งปลายทางคือ t เลข a/b แสดงให้เห็นปริมาณการไหลในท่อนั้นกับความจุของท่อนั้นตามลำดับ

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

ประวัติแก้ไข

นิยามปัญหาแก้ไข

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

ทฤษฎีบทแก้ไข

ทฤษฎีบทการไหลมากสุด-คัทต่ำสุดแก้ไข

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

ทฤษฎีบทการไหลที่เป็นจำนวนเต็มแก้ไข

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

การนำไปใช้แก้ไข

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

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

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