โฟลว์เครือข่าย

ปัญหามากมายในวิทยาการคอมพิวเตอร์อาจแสดงเป็นกราฟที่ประกอบด้วยโหนดและลิงก์ระหว่างรายการเหล่านั้น ตัวอย่างเช่น ปัญหาโฟลว์เครือข่ายซึ่งเกี่ยวข้องกับการขนส่งสินค้าหรือวัสดุในเครือข่ายต่างๆ เช่น ระบบรถไฟ

คุณแสดงโฟลว์เครือข่ายได้ด้วยกราฟที่มีโหนดเป็นเมืองและกราฟโค้งเป็นเส้นเชื่อมต่อ (เรียกว่าการไหล เนื่องจากพร็อพเพอร์ตี้คล้ายกับก๊อกน้ําที่ไหลผ่านท่อ)

ข้อจํากัดสําคัญในการไหลเวียนของเครือข่ายคือโครงสร้างแต่ละรายการมีความจุ ซึ่งเป็นจํานวนเงินสูงสุดที่ถ่ายโอนระหว่างโครงสร้างได้ในระยะเวลาที่กําหนด

ปัญหาโฟลว์สูงสุดคือการระบุจํานวนเงินรวมสูงสุดขนส่งระหว่างกราฟทั้งหมดในเครือข่ายได้ โดยขึ้นอยู่กับข้อจํากัดด้านความจุ

บุคคลแรกที่ทําการศึกษาปัญหานี้คือ คณิตศาสตร์ N.N. Tolstoi นักคณิตศาสตร์ชาวรัสเซียในช่วงทศวรรษ 1930 แผนที่ด้านล่างแสดงเครือข่ายทางรถไฟจริงที่เธอต้องการค้นหาโฟลว์สูงสุด

"หรือ" มีเครื่องมือแก้ปัญหาหลายอย่างสําหรับโฟลว์โฟลว์เครือข่ายในไลบรารีกราฟ

ส่วนต่อไปนี้จะแสดงตัวอย่างปัญหาโฟลว์เครือข่ายและแสดงวิธีแก้โจทย์ปัญหา

• โฟลว์สูงสุด
• โฟลว์ค่าใช้จ่ายขั้นต่ํา
• การกําหนดเป็นโฟลว์ต้นทุนขั้นต่ํา
• การมอบหมายร่วมกับทีมผู้ปฏิบัติงาน