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

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

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

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

ประวัติ[แก้]

นิยามปัญหา[แก้]

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

ทฤษฎีบท[แก้]

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

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

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

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

การนำไปใช้[แก้]

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

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

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