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

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

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

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

ประวัติ

นิยามปัญหา

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

ทฤษฎีบท

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

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

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

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

การนำไปใช้

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

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

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