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

เครือข่ายคือ กราฟแบบมีทิศทางG = ( V , E ) ที่มี ฟังก์ชันความจุ ที่ไม่เป็นลบcสำหรับแต่ละขอบ และไม่มีส่วนโค้งหลายส่วน (กล่าวคือ ขอบที่มีโหนดต้นทางและปลายทางเดียวกัน) โดยไม่เสียความเป็นทั่วไปเราอาจสมมติว่า ถ้า( u , v ) ∈ Eแล้ว( v , u )ก็เป็นสมาชิกของE ด้วย นอกจากนี้ ถ้า( v , u ) ∉ Eแล้ว เราอาจเพิ่ม( v , u )เข้าไปในEแล้วกำหนดให้c ( v , u ) = 0

ถ้าโหนดสองโหนดในGถูกแยกแยะ – โหนดหนึ่งเป็นแหล่งกำเนิดsและอีกโหนดหนึ่งเป็นปลายทางt – แล้ว( G , c , s , t )เรียกว่าเครือข่ายการไหล^{[ 1 ]}

ฟังก์ชันการไหลจำลองการไหลสุทธิของหน่วยระหว่างคู่ของโหนด และมีประโยชน์เมื่อถามคำถามเช่นจำนวนหน่วยสูงสุดที่สามารถถ่ายโอนจากโหนดต้นทาง s ไปยังโหนดปลายทาง t คือเท่าใดปริมาณการไหลระหว่างสองโหนดใช้เพื่อแสดงปริมาณสุทธิของหน่วยที่ถูกถ่ายโอนจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง

ฟังก์ชันส่วนเกินx   : V → ℝ แสดงถึงกระแสสุทธิ ที่ไหลเข้าสู่โหนดu ที่กำหนด (กล่าวคือ ผลรวมของกระแสที่ไหลเข้าสู่u ) และถูกกำหนดโดย$${\displaystyle x_{f}(u)=\sum _{w\in V}f(w,u)-\sum _{w\in V}f(u,w).}$$กล่าวได้ว่าโหนดu เป็นโหนด ที่ทำงานอยู่ (active)ถ้าx ( u ) > 0 (นั่นคือ โหนดuใช้การไหล) เป็นโหนด ที่ขาดแคลน (deficient)ถ้าx ( u ) < 0 (นั่นคือ โหนดuผลิตการไหล) หรือ เป็นโหนด ที่อนุรักษ์ (conserving)ถ้าx ( u ) = 0ในเครือข่ายการไหล แหล่งกำเนิดsเป็นโหนดที่ขาดแคลน และปลายทางtเป็นโหนดที่ทำงานอยู่ การไหลเสมือน (pseudo-flows) การไหลที่เป็นไปได้ (feasible flows) และการไหลก่อนหน้า (pre-flows) ล้วนเป็นตัวอย่างของฟังก์ชันการไหล

โฟลว์เสมือน (pseudo-flow)คือฟังก์ชันf ของแต่ละขอบในเครือข่ายที่สอดคล้องกับข้อจำกัดสองข้อต่อไปนี้สำหรับทุกโหนดuและv :

• ข้อจำกัดสมมาตรแบบเฉียง : การไหลบนส่วนโค้งจากuไปvเทียบเท่ากับการกลับทิศทางการไหลบนส่วนโค้งจากvไปuนั่นคือf ( u , v ) = −f ( v , u )เครื่องหมายของการไหลบ่งบอกถึงทิศทางการไหล
• ข้อจำกัดด้านความจุ : การไหลของส่วนโค้งต้องไม่เกินความจุ กล่าวคือf ( u , v ) ≤ c ( u , v )

พรีโฟลว์คือซูโดโฟลว์ที่สำหรับทุกv ∈ V \{ s }จะเป็นไปตามข้อจำกัดเพิ่มเติมดังต่อไปนี้:

• การไหลที่ไม่ขาดดุล : การไหลสุทธิที่เข้าสู่โหนดvมีค่าไม่เป็นลบ ยกเว้นแหล่งกำเนิดซึ่ง "สร้าง" การไหล นั่นคือ: x f v ) ≥ 0สำหรับทุกv ∈ V \{ s }

กระแสการไหลที่เป็นไปได้หรือเรียกสั้น ๆ ว่ากระแสการไหลคือ กระแสการไหลเสมือน ที่สำหรับทุกv ∈ V \{ s , t }จะเป็นไปตามข้อจำกัดเพิ่มเติมดังต่อไปนี้:

• ข้อจำกัดการอนุรักษ์การไหล : ผลรวมของการไหลสุทธิที่เข้าสู่โหนดvจะเป็นศูนย์สำหรับทุกโหนดในเครือข่าย ยกเว้นแหล่งกำเนิดsและปลายทางtนั่นคือx ( v ) = 0สำหรับทุกv ∈ V \{ s , t }กล่าวอีกนัยหนึ่ง สำหรับทุกโหนดในเครือข่าย ยกเว้นแหล่งกำเนิดsและปลายทางtผลรวมของการไหลเข้าของโหนดจะเท่ากับการไหลออก (เช่น${\displaystyle \sum _{(u,v)\in E}f(u,v)=\sum _{(v,z)\in E}f(v,z)}$สำหรับแต่ละจุดยอดv ∈ V \{ s , t } )

ค่า| f |ของการไหลที่เป็นไปได้fสำหรับเครือข่าย คือการไหลสุทธิเข้าสู่จุดรับt ของเครือข่ายการไหล นั่นคือ |f| = xf( )โปรดทราบว่าค่าการไหลในเครือข่ายยังเท่ากับการไหลออกทั้งหมดของแหล่งกำเนิดsนั่นคือ| f | = −xf ( )นอกจากนี้ หากเรากำหนดAเป็นเซตของโหนดในGโดยที่s ∈ Aและt ∉ A ค่าการไหลจะเท่ากับการไหลสุทธิทั้งหมดที่ออกจาก A (นั่นคือ| f | = f ^out ( A ) − f ⁱⁿ ( A ) ) ^{[ 2 ]}ค่าการไหลในเครือข่ายคือปริมาณการไหลทั้งหมดจากsไปยังt

ในรูปที่ 1 คุณจะเห็นเครือข่ายการไหลที่มีแหล่งกำเนิดระบุด้วยs ปลายทางระบุ ด้วยtและโหนดเพิ่มเติมอีกสี่โหนด การไหลและความจุแสดงด้วย${\displaystyle f/c}$สังเกตว่าเครือข่ายนี้รักษาข้อจำกัดด้านความจุและข้อจำกัดด้านการอนุรักษ์การไหล ปริมาณการไหลทั้งหมดจากsไปtคือ 5 ซึ่งสามารถเห็นได้ง่ายจากข้อเท็จจริงที่ว่าปริมาณการไหลออกทั้งหมดจากsคือ 5 ซึ่งก็คือปริมาณการไหลเข้าสู่t เช่นกัน ภายใต้ข้อจำกัดด้านสมมาตรเฉียง ปริมาณการไหลจากcไปaคือ -2 เนื่องจากปริมาณการไหลจากaไปcคือ 2

ในรูปที่ 2 คุณจะเห็นเครือข่ายส่วนที่เหลือสำหรับการไหลที่กำหนดไว้แบบเดียวกัน สังเกตว่ามีความจุส่วนที่เหลือเป็นบวกบนขอบบางส่วนที่ความจุเดิมเป็นศูนย์ในรูปที่ 1 ตัวอย่างเช่น สำหรับขอบ${\displaystyle (d,c)}$เครือข่ายนี้ยังไม่ถึงระดับปริมาณการใช้งานสูงสุดยังมีพื้นที่ว่างเหลืออยู่ตามเส้นทางต่างๆ${\displaystyle (s,a,c,t)}$,${\displaystyle (s,a,b,d,t)}$และ${\displaystyle (s,a,b,d,c,t)}$ซึ่งก็คือเส้นทางเสริมเหล่านั้น

จุดคอขวดของ${\displaystyle (s,a,c,t)}$เส้นทางเท่ากับ${\displaystyle \min(c(s,a)-f(s,a),c(a,c)-f(a,c),c(c,t)-f(c,t))}$${\displaystyle =\min(c_{f}(s,a),c_{f}(a,c),c_{f}(c,t))}$${\displaystyle =\min(5-3,3-2,2-1)}$${\displaystyle =\min(2,1,1)=1}$.

ลองนึกภาพท่อน้ำหลายๆ ท่อที่ต่อกันเป็นเครือข่าย ท่อแต่ละท่อมีเส้นผ่านศูนย์กลางที่แน่นอน ดังนั้นจึงสามารถรองรับปริมาณน้ำไหลได้ในปริมาณที่จำกัด ตรงจุดที่ท่อมาบรรจบกัน ปริมาณน้ำทั้งหมดที่ไหลเข้ามาต้องเท่ากับปริมาณน้ำที่ไหลออกไป มิฉะนั้นน้ำจะหมดเร็ว หรืออาจเกิดการขังน้ำได้ เรามีทางเข้าของน้ำ ซึ่งเป็นแหล่งน้ำ และทางออก ซึ่งเป็นอ่างล้างจาน ดังนั้น อัตราการไหล จึงหมายถึงวิธีหนึ่งที่น้ำจะไหลจากแหล่งน้ำไปยังอ่างล้างจาน โดยที่ปริมาณน้ำทั้งหมดที่ไหลออกจากทางออกนั้นคงที่ โดยทั่วไปแล้ว อัตราการไหลรวมของเครือข่ายก็คืออัตราที่น้ำไหลออกจากทางออกนั่นเอง

การไหลอาจหมายถึงการไหลผ่านของคนหรือวัสดุบนเครือข่ายการขนส่ง หรือการไหลผ่านกระแสไฟฟ้าใน ระบบ จำหน่ายไฟฟ้าสำหรับเครือข่ายทางกายภาพใดๆ การไหลที่เข้ามาในโหนดกลางใดๆ จะต้องเท่ากับการไหลที่ออกจากโหนดนั้น ข้อจำกัดในการอนุรักษ์นี้เทียบเท่ากับกฎกระแสของเคิร์ชฮอฟฟ์

เครือข่ายการไหลยังพบการประยุกต์ใช้ในด้านนิเวศวิทยา ด้วย กล่าวคือ เครือข่ายการไหลเกิดขึ้นตามธรรมชาติเมื่อพิจารณาการไหลของสารอาหารและพลังงานระหว่างสิ่งมีชีวิตต่าง ๆ ใน ห่วงโซ่ อาหารปัญหาทางคณิตศาสตร์ที่เกี่ยวข้องกับเครือข่ายดังกล่าวแตกต่างจากปัญหาที่เกิดขึ้นในเครือข่ายการไหลของของเหลวหรือการจราจรอย่างสิ้นเชิง สาขาการวิเคราะห์เครือข่ายระบบนิเวศ ซึ่งพัฒนาโดยโรเบิร์ต อูลาโนวิชและคนอื่นๆ เกี่ยวข้องกับการใช้แนวคิดจากทฤษฎีสารสนเทศและอุณหพลศาสตร์เพื่อศึกษาการวิวัฒนาการของเครือข่ายเหล่านี้เมื่อเวลาผ่านไป

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

อัลกอริทึมที่เป็นที่รู้จักกันดีสำหรับปัญหาการไหลสูงสุด

ผู้ประดิษฐ์	ปี	ความซับซ้อนเชิงเวลา(โดยมี โหนด nโหนดและ ส่วนโค้ง mส่วน)
อัลกอริทึมของ Dinic	1970	O ( mn 2 )
อัลกอริทึม Edmonds–Karp	พ.ศ. 2515	O ( m 2 n )
อัลกอริทึมMPM (Malhotra, Pramodh-Kumar และ Maheshwari) [ 6 ]	พ.ศ. 2521	O ( n 3 )
อัลกอริธึม Push–relabel ( Goldberg & Tarjan )	1988	O ( n 2 m )
เจมส์ บี. ออร์ลิน[ 7 ]	2013	โอ ( ม.น )
หลี่ เฉิน, ราสมุส คิง, หยาง พี. หลิว, ริชาร์ด เผิง, แม็กซิมิเลียน พรบสต์ กูเทนเบิร์ก, สุชานต์ ซัคเดวา	2022	${\displaystyle O(m^{1+o(1)})}$

ในปัญหาการไหลเวียนของสินค้าหลายชนิดคุณจะมีแหล่งที่มาและปลายทางหลายแห่ง และ "สินค้า" หลากหลายชนิดที่จะต้องไหลจากแหล่งที่มาที่กำหนดไปยังปลายทางที่กำหนด ตัวอย่างเช่น อาจเป็นสินค้าหลายชนิดที่ผลิตในโรงงานหลายแห่ง และจะต้องส่งไปยังลูกค้าหลายรายที่กำหนดผ่านเครือข่ายการขนส่งเดียวกัน

ในปัญหาการไหลที่มีต้นทุนต่ำสุดแต่ละขอบ${\displaystyle u,v}$มีต้นทุนที่กำหนดไว้${\displaystyle k(u,v)}$และต้นทุนในการส่งกระแสข้อมูล${\displaystyle f(u,v)}$ข้ามขอบนั้นคือ${\displaystyle f(u,v)\cdot k(u,v)}$เป้าหมายคือการส่งปริมาณการไหลที่กำหนดจากแหล่งกำเนิดไปยังปลายทางด้วยต้นทุนที่ต่ำที่สุดเท่าที่จะเป็นไปได้

ในปัญหาเกี่ยวกับการไหลเวียนคุณจะมีขอบเขตล่าง${\displaystyle \ell (u,v)}$ที่ขอบ นอกเหนือจากขอบเขตบนแล้ว${\displaystyle c(u,v)}$แต่ละเส้นเชื่อมก็มีต้นทุนเช่นกัน บ่อยครั้งที่หลักการอนุรักษ์การไหลใช้ได้กับทุกโหนดในปัญหาการไหลเวียน และมีการเชื่อมต่อจากจุดรับกลับไปยังจุดกำเนิด ด้วยวิธีนี้ คุณสามารถกำหนดปริมาณการไหลทั้งหมดได้ด้วย${\displaystyle \ell (t,s)}$และ${\displaystyle c(t,s)}$กระแสไหลหมุนเวียนผ่านเครือข่าย จึงเป็นที่มาของชื่อปัญหาดังกล่าว

ในเครือข่ายที่มีอัตราขยายหรือเครือข่ายทั่วไปแต่ละขอบจะมีอัตราขยายซึ่งเป็นจำนวนจริง (ไม่ใช่ศูนย์) โดยที่หากขอบมีอัตราขยายgและมีปริมาณxไหลเข้าสู่ขอบที่ปลายด้านหนึ่ง ปริมาณgxจะไหลออกที่ปลายด้านตรงข้าม

ในปัญหาการระบุตำแหน่งแหล่งที่มาอัลกอริทึมจะพยายามระบุโหนดแหล่งที่มาที่มีความเป็นไปได้มากที่สุดของการแพร่กระจายข้อมูลผ่านเครือข่ายที่สังเกตได้บางส่วน ซึ่งสามารถทำได้ในเวลาเชิงเส้นสำหรับต้นไม้และเวลาลูกบาศก์สำหรับเครือข่ายใดๆ และมีการใช้งานที่หลากหลายตั้งแต่การติดตามผู้ใช้โทรศัพท์มือถือไปจนถึงการระบุแหล่งที่มาของการระบาดของโรค^{[ 8 ]}

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