การไหลในเครือข่าย

ในทฤษฎีกราฟ การไหลในเครือข่าย (อังกฤษ: network flow) คือ การกำหนดค่าให้กับเส้นเชื่อมในกราฟระบุทิศทางถ่วงน้ำหนัก (เรียกว่า เครือข่ายการไหล (อังกฤษ: Flow network) ในกรณีนี้) ซึ่ง

1. ค่าของแต่ละเส้นเชื่อม จะไม่เกินน้ำหนักของเส้นเชื่อมนั้น (หรือเรียกว่า ความจุ (capacity))
2. การไหลเข้าทั้งหมดของจุดต่อ (ผลบวกของค่าของเส้นเชื่อมที่เข้ามาในจุดต่อนั้น) จะเท่ากับการไหลออกทั้งหมดเสมอ ยกเว้นจุดต่อพิเศษ 2 จุด คือ s และ t จุดต่อ s จะมีการไหลออกแต่ไม่มีการไหลเข้า จุดต่อ t จะมีการไหลเข้าแต่ไม่มีการไหลออก

ในกรณีนี้ s คือ แหล่งต้นทาง (source) และ t คือ แหล่งปลายทาง (sink)

ในการทำความเข้าใจกับการไหลในเครือข่าย ให้นึกถึงภาพท่อน้ำ ท่อแต่ละท่อจะมีความกว้างที่แน่นอน ซึ่งจะยอมให้น้ำไหลผ่านในปริมาณที่แน่นอน ที่ใดก็ตามที่ท่อเชื่อมกัน ปริมาณน้ำที่ไหลเข้าไปในตัวเชื่อม จะต้องเท่ากับปริมาณน้ำที่ไหลออก มิฉะนั้นแล้ว น้ำจะไหลออกจนหมดหรือเราจะเพิ่มน้ำขึ้นมา เราจะต้องมีทางเข้าของน้ำ นั่นคือแหล่งต้นทาง และเราจะต้องมีทางออกน้ำ ซึ่งแทนแหล่งปลายทาง การไหล (flow) จะเป็นเส้นทางที่น้ำไหลจากแหล่งต้นทางไปแหล่งปลายทางได้ ดังนั้น ปริมาณของน้ำที่ไหลออกจากทางออกจะคงที่ และการไหลรวม (total flow) ของการไหลในเครือข่าย คืออัตราการไหลของน้ำที่ออกจากทางออก

ปัญหาที่รู้จักกันดี คือการหา การไหลสูงสุด (max flow) ซึ่งเป็นค่าการไหลรวมสูงสุดของกราฟที่กำหนดให้ ขั้นตอนวิธีที่ใช้ในการแก้ปัญหานี้ที่รู้จักกันมากที่สุดคือ ขั้นตอนวิธีของฟอร์ด-เฟอลเกอสัน และขั้นตอนวิธีRelabel-to-front

มีปัญหาหลายปัญหาที่แก้ได้ด้วยขั้นตอนวิธีการไหลสูงสุด ถ้าเราแทนด้วยเครือข่ายการไหล เช่น การจับคู่สองส่วน (bipartite matching)