เครื่องคำนวณการไหลสูงสุด

เครื่องคำนวณการไหลในเครือข่าย (การไหลสูงสุด)

คำนวณการไหลสูงสุดจากต้นทางไปยังปลายทางในเครือข่ายแบบระบุทิศทางที่มีความจุ โดยใช้วิธี Ford-Fulkerson (Edmonds-Karp) แสดงภาพเคลื่อนไหวของทุกวิถีเพิ่มพูน แสดงความจุที่เหลืออยู่ เส้นเชื่อมที่อิ่มตัว และการแบ่งรอยตัดขั้นต่ำที่พิสูจน์ความเหมาะสมที่สุด

ตัวอย่างด่วน:

ตำราเรียน (6 จุด) เครือข่ายขนาดเล็ก CLRS คลาสสิก Bipartite-ish อินพุตเมทริกซ์

↦ รายการขอบพร้อมความจุ ▦ เมทริกซ์ความจุ

ข้อมูลเครือข่าย

รูปแบบขอบ: A -> B : 10 (ลูกศรพร้อมความจุ) หรือ A, B, 10 รูปแบบเมทริกซ์: หนึ่งแถวต่อหนึ่งบรรทัด C[i][j] คือความจุของขอบ i → j (ใช้ 0 หากไม่มีขอบ) เส้นทแยงมุมต้องเป็น 0

ป้ายกำกับเมทริกซ์ (ไม่บังคับ)

ป้ายกำกับคั่นด้วยจุลภาคหรือช่องว่าง หนึ่งป้ายต่อหนึ่งแถวเมทริกซ์ ค่าเริ่มต้นคือ S, A, B, …, T

จุดยอดแหล่งกำเนิด (Source) ⭘

จุดยอดปลายทาง (Sink) ⬤

Embed เครื่องคำนวณการไหลในเครือข่าย (การไหลสูงสุด) Widget

เกี่ยวกับ เครื่องคำนวณการไหลในเครือข่าย (การไหลสูงสุด)

เครื่องคำนวณการไหลในเครือข่าย จะคำนวณ การไหลสูงสุด จากแหล่งกำเนิด (source) s ไปยังปลายทาง (sink) t ที่เลือกในเครือข่ายแบบมีทิศทางที่มีความจุ เบื้องหลังการทำงานจะใช้ วิธี Ford-Fulkerson ร่วมกับ การค้นหาเส้นทางที่เพิ่มขึ้นแบบ Breadth-First (อัลกอริทึม Edmonds-Karp) จากนั้นจะบันทึกทุกเส้นทางที่พบเพื่อให้คุณสามารถย้อนดูขั้นตอนการตัดสินใจทั้งหมดได้ทีละรายการ หน้าผลลัพธ์ยังแสดง min-cut ซึ่งเป็นส่วนแบ่งคอขวดที่พิสูจน์ว่าค่าการไหลของคุณนั้นเหมาะสมที่สุดแล้วจริงๆ

ปัญหาการไหลสูงสุดคืออะไร?

เครือข่ายการไหล (flow network) คือกราฟมีทิศทาง G = (V, E) พร้อมกับฟังก์ชันความจุ c: E → ℝ_≥0 โดยมีจุดยอดสองจุดที่แยกกันคือ แหล่งกำเนิด s (จุดที่การไหลเริ่มต้น) และ ปลายทาง t (จุดที่การไหลถูกใช้ไป) การไหล f คือการกำหนดค่า f(u, v) ≥ 0 บนขอบที่เป็นไปตามกฎ:

ความจุ: 0 ≤ f(u, v) ≤ c(u, v) สำหรับทุกขอบ (u, v) การอนุรักษ์: Σ f(w, v) = Σ f(v, w) สำหรับทุก v ∈ V \ {s, t} ค่าการไหล: |f| = Σ f(s, w) − Σ f(w, s) (การไหลสุทธิที่ออกจาก s)

ปัญหาการไหลสูงสุด คือการหาการไหล f ที่ทำให้ค่า |f| มีค่าสูงสุด เปรียบเทียบได้ง่ายๆ ว่า: หากขอบเป็นท่อน้ำที่มีความจุที่กำหนด คุณจะสามารถส่งน้ำจาก s ไปยัง t ได้กี่ลิตรต่อวินาที?

อัลกอริทึมทำงานอย่างไร — Ford-Fulkerson ด้วย BFS

อัลกอริทึมจะรักษา กราฟส่วนเหลือ (residual graph) ควบคู่ไปกับการไหลปัจจุบัน สำหรับทุกขอบ (u, v) ที่มีความจุ c และการไหลปัจจุบัน f กราฟส่วนเหลือจะประกอบด้วย:

ขอบส่วนเหลือไปข้างหน้า (u, v) ที่มีความจุ c − f (ยังผลักเพิ่มได้อีกเท่าไหร่) และ
ขอบส่วนเหลือย้อนกลับ (v, u) ที่มีความจุ f (สามารถยกเลิกการไหลที่ส่งไปแล้วได้เท่าไหร่)

ในการทำซ้ำแต่ละครั้ง จะมีการดำเนินการ Breadth-First Search (BFS) จาก s ไปยัง t บนกราฟส่วนเหลือ หากพบเส้นทาง ความจุที่น้อยที่สุดบนเส้นทางนั้น — หรือ คอขวด — จะถูกนำไปบวกเข้ากับการไหลในทุกขอบไปข้างหน้า และลบออกในทุกขอบย้อนกลับตามเส้นทางนั้น สิ่งนี้เรียกว่า เส้นทางที่เพิ่มขึ้น (augmenting path) เมื่อ BFS ไม่สามารถเข้าถึง t ได้อีกต่อไป การไหลปัจจุบันจะถือว่าเหมาะสมที่สุด

ตราบใดที่ ยังมีเส้นทางที่เพิ่มขึ้น P จาก s ไป t ในกราฟส่วนเหลือ: b ← min c_residual(u, v) สำหรับขอบ (u, v) ใน P ผลักการไหล b หน่วยตามเส้นทาง P // อัปเดตกราฟส่วนเหลือ + การไหล คืนค่าการไหลรวม |f|

การใช้ BFS (แทนที่จะเป็นกลยุทธ์การหาเส้นทางแบบสุ่ม) จะเปลี่ยน Ford-Fulkerson เป็น Edmonds-Karp โดยรับประกันเวลาการทำงานที่ O(V · E²) นอกจากนี้ยังรับประกันการสิ้นสุดการทำงานในกรณีความจุที่เป็นจำนวนอตรรกยะ ซึ่ง Ford-Fulkerson แบบธรรมดาอาจทำไม่ได้

ทฤษฎีบท Max-Flow Min-Cut

คัต (cut) คือการแบ่งจุดยอดออกเป็นสองเซต (S, T) โดยที่ s ∈ S และ t ∈ T ความจุ ของคัตคือผลรวมของความจุของขอบที่ส่งจาก S ไปยัง T:

cap(S, T) = Σ c(u, v) สำหรับ u ∈ S, v ∈ T

ทฤษฎีบท max-flow min-cut (Ford & Fulkerson, 1956) ระบุว่า:

ค่าการไหลสูงสุด = ความจุของคัตที่น้อยที่สุด (min-cut)

เครื่องมือนี้จะหา min-cut โดยอัตโนมัติ หลังจาก Edmonds-Karp สิ้นสุดลง มันจะรัน BFS อีกหนึ่งครั้งจาก s บนกราฟส่วนเหลือ จุดยอดที่เข้าถึงได้จะรวมเป็นเซต S ส่วนที่เหลือคือ T และทุกขอบที่ข้ามจาก S → T ในกราฟต้นฉบับจะอิ่มตัว ผลรวมความจุของขอบเหล่านี้จะเท่ากับค่าการไหลสูงสุดพอดี — สามารถดูได้ในส่วนผลลัพธ์ที่ระบุว่า "ความจุ Min-cut ✓ ยืนยันความเหมาะสมที่สุด"

คุณสมบัติที่สร้างมาเพื่อการเรียนรู้

แอนิเมชันทีละขั้นตอน: เล่นซ้ำทุกเส้นทางที่เพิ่มขึ้นพร้อมตัวควบคุมการเล่น หยุดชั่วคราว และเลื่อนทีละขั้น ดูว่า BFS เลือกเส้นทางไหน ขอบไหนเป็นคอขวด และยอดรวมการไหลเพิ่มขึ้นอย่างไร
เมทริกซ์สามตัวที่ซิงโครไนซ์กัน: สลับระหว่างเมทริกซ์ความจุ C, เมทริกซ์การไหลสุดท้าย f และเมทริกซ์ส่วนเหลือ C − f — ภาพสามภาพที่รวมกันเพื่ออธิบายลักษณะการไหลใดๆ
มุมมองการแบ่ง Min-cut: รายชื่อจุดยอดฝั่ง S และฝั่ง T จะแสดงเป็นชิป พร้อมเน้นขอบอิ่มตัวที่ข้ามคัตด้วยสีแดง
ตารางแยกตามขอบ: สำหรับทุกขอบ: แสดงความจุ การไหล ส่วนเหลือ แถบแสดงเปอร์เซ็นต์การใช้งาน และสถานะความอิ่มตัว
เลย์เอาต์แบบเลเยอร์จากซ้ายไปขวา: การวาดกราฟจะคำนวณจากระยะทาง BFS จากแหล่งกำเนิด เพื่อให้น้ำ "ไหล" จากซ้ายไปขวาอย่างชัดเจน เหมือนที่วาดในตำราเรียน

รูปแบบข้อมูลนำเข้า

1. รายการขอบพร้อมความจุ

หนึ่งขอบต่อหนึ่งบรรทัด รูปแบบลูกศรอ่านง่ายที่สุดแต่รองรับรูปแบบอื่นด้วย:

S -> A : 10 S -> B : 13 A -> B : 10 B -> A : 4 B -> T : 14

รูปแบบที่ยอมรับเช่นกัน: A, B, 10 · A B 10 · A -> B , 10 หากมีขอบหลายเส้นระหว่างจุดคู่เดียวกัน ความจุจะถูกนำมารวมกัน

2. เมทริกซ์ความจุ

หนึ่งแถวต่อหนึ่งบรรทัด คั่นค่าด้วยช่องว่างหรือจุลภาค ค่าใน C[i][j] คือความจุของขอบจากจุดยอด i ไปยังจุดยอด j ใช้ 0 สำหรับ "ไม่มีขอบ" เมทริกซ์ต้องเป็นรูปสี่เหลี่ยมจัตุรัสและเส้นทแยงมุมต้องเป็น 0 (ไม่มีลูปกลับเข้าหาตัวเอง)

S A B C D T S [ 0 10 0 10 0 0 ] A [ 0 0 4 2 8 0 ] B [ 0 0 0 0 0 10 ] C [ 0 0 0 0 9 0 ] D [ 0 0 6 0 0 10 ] T [ 0 0 0 0 0 0 ]

ป้อนชื่อป้ายกำกับจุดยอดที่ตรงกันในช่อง ป้ายกำกับเมทริกซ์ (คั่นด้วยจุลภาคหรือช่องว่าง) หากละเว้น จะใช้ค่าเริ่มต้นเป็น S, A, B, …, T

การประยุกต์ใช้การไหลสูงสุด

โดเมน	การใช้งานการไหลสูงสุด
การขนส่งและโลจิสติกส์	เครือข่ายรถไฟ/ถนน/ท่อส่งน้ำมันสามารถเคลื่อนย้ายสินค้าจากต้นทางไปยังปลายทางได้เท่าใดต่อวัน?
การจับคู่แบบสองส่วน (Bipartite matching)	การมอบหมายงานให้คนงาน หรือนักเรียนให้โปรเจกต์ การไหลสูงสุดที่มีความจุหนึ่งหน่วยจะให้ผลลัพธ์เป็นการจับคู่ที่มากที่สุด
การแบ่งส่วนภาพ (Image segmentation)	Boykov–Kolmogorov min-cut ในคอมพิวเตอร์วิทัศน์ช่วยแยกพิกเซลพื้นหน้าออกจากพื้นหลัง
ความน่าเชื่อถือของเครือข่าย	Min-cut จะระบุจุดเชื่อมต่อที่อ่อนแอที่สุดซึ่งหากล้มเหลวจะทำให้เครือข่ายขาดออกจากกัน
การวางแผนโครงการ	ปัญหาการปิดโครงการ (Closure problems) และปัญหาการเลือกสามารถลดรูปเป็นปัญหา min-cut ได้
การคัดออกในกีฬาเบสบอล	ใช้ตัดสินว่าทีมใดทีมหนึ่งหมดสิทธิ์คว้าแชมป์ลีกในทางคณิตศาสตร์แล้วหรือไม่

ตัวอย่างการคำนวณ

ตัวอย่างด่วนแบบ "ตำราเรียน" เข้ารหัสเครือข่าย 6 จุดโดยมีแหล่งกำเนิด S และปลายทาง T การรัน Edmonds-Karp จะได้เส้นทางที่เพิ่มขึ้นสี่เส้นทาง:

S → A → B → T ด้วยคอขวด 4 (ขอบ A-B เป็นตัวจำกัด) การไหลรวม: 4
S → A → D → T ด้วยคอขวด 6 การไหลรวม: 10
S → C → D → T ด้วยคอขวด 4 (ตอนนี้ขอบ D-T เป็นตัวจำกัด เหลือเพียง 4) การไหลรวม: 14
S → C → D → B → T ด้วยคอขวด 5 การไหลรวม: 19

อัลกอริทึมจะหยุดลงเพราะไม่มีเส้นทางที่เพิ่มขึ้นเหลืออยู่ min-cut คือ (S = {S, C}, T = {A, B, D, T}) โดยมีขอบที่ข้ามคัตคือ S → A (ความจุ 10) และ C → D (ความจุ 9) รวมเป็น 19 ซึ่งเท่ากับค่าการไหลสูงสุดพอดี

วิธีใช้เครื่องคำนวณนี้

เลือกรูปแบบข้อมูลนำเข้า โดยใช้แท็บ — รายการขอบ (แนะนำ) หรือเมทริกซ์ความจุ
ป้อนเครือข่ายของคุณ คุณสามารถเริ่มจากตัวอย่างด่วนแล้วแก้ไขข้อมูลได้ สำหรับอินพุตเมทริกซ์ โปรดระบุชื่อป้ายกำกับหากคุณต้องการชื่ออื่นนอกเหนือจาก S, A, B, …, T
ระบุแหล่งกำเนิดและปลายทาง (หรือปล่อยว่างไว้เพื่อตรวจหา S และ T อัตโนมัติ)
คลิก คำนวณการไหลสูงสุด หน้าผลลัพธ์จะแสดงค่าการไหลสูงสุด การแบ่ง min-cut ภาพจำลองกราฟแบบเลเยอร์ ทุกเส้นทางที่เพิ่มขึ้น ตารางการใช้งานขอบ และเมทริกซ์สามตัว (ความจุ, การไหล, ส่วนเหลือ)
เล่นแอนิเมชัน ใต้กราฟเพื่อดูการตัดสินใจของอัลกอริทึมซ้ำ คลิกที่ขั้นตอนเส้นทางที่เพิ่มขึ้นใดก็ได้เพื่อข้ามไปยังจุดนั้นโดยตรง

ข้อจำกัด

จุดยอด: สูงสุด 30 จุด — เพื่อให้การแสดงผลและเมทริกซ์ยังอ่านง่าย
ขอบ: สูงสุด 200 ขอบ
ความจุ: ไม่เป็นลบ สูงสุด 10⁹ รองรับความจุที่เป็นทศนิยม
ไม่มีลูปกลับเข้าหาตัวเอง: Self-loops ไม่มีการไหลในสูตรการไหลสูงสุดมาตรฐานและจะถูกปฏิเสธ

คำถามที่พบบ่อย

ปัญหาการไหลสูงสุดคืออะไร?

กำหนดเครือข่ายแบบมีทิศทางซึ่งแต่ละขอบมีความจุที่ไม่เป็นลบ ปัญหาการไหลสูงสุดถามว่า: สามารถส่งการไหลจากจุดยอดแหล่งกำเนิด s ที่กำหนดไปยังจุดยอดปลายทาง t ที่กำหนดได้มากเพียงใด ภายใต้กฎที่ว่าการไหลในแต่ละขอบต้องไม่เกินความจุ และการไหลที่เข้าสู่จุดยอดทุกจุดที่ไม่ใช่แหล่งกำเนิดหรือปลายทางต้องเท่ากับการไหลที่ออกจากจุดนั้น? คำตอบเรียกว่าค่าการไหลสูงสุด

วิธี Ford-Fulkerson คืออะไร?

Ford-Fulkerson เป็นเทคนิคทั่วไปสำหรับการคำนวณการไหลสูงสุด โดยจะค้นหาเส้นทางที่เพิ่มขึ้น (augmenting path) จากแหล่งกำเนิดไปยังปลายทางในกราฟส่วนเหลือซ้ำๆ และผลักการไหลให้ได้มากที่สุดตามเส้นทางนั้น (ความจุคอขวด) จากนั้นจึงอัปเดตกราฟส่วนเหลือ กระบวนการจะสิ้นสุดลงเมื่อไม่มีเส้นทางที่เพิ่มขึ้นเหลืออยู่ เมื่อนำมาใช้กับ Breadth-First Search สำหรับการเลือกเส้นทาง จะเรียกว่า Edmonds-Karp และรันในเวลา O(V · E²) time

min-cut ของเครือข่ายการไหลคืออะไร?

คัตคือการแบ่งจุดยอดออกเป็นสองเซต S และ T โดยที่แหล่งกำเนิดอยู่ใน S และปลายทางอยู่ใน T ความจุของคัตคือผลรวมของความจุของขอบจาก S ไปยัง T ส่วน min-cut คือคัตที่มีความจุน้อยที่สุด ทฤษฎีบท max-flow min-cut ที่มีชื่อเสียงพิสูจน์ว่าค่าการไหลสูงสุดจะเท่ากับความจุของ min-cut เสมอ ดังนั้นการหาค่าหนึ่งจึงทำให้ได้อีกค่าหนึ่งโดยอัตโนมัติ

กราฟส่วนเหลือคืออะไร?

กราฟส่วนเหลือจะติดตามว่ายังสามารถผลักการไหลเพิ่มได้อีกเท่าใดในแต่ละขอบ สำหรับทุกขอบเดิม (u, v) ที่มีความจุ c และการไหลปัจจุบัน f กราฟส่วนเหลือจะประกอบด้วยขอบไปข้างหน้า (u, v) ที่มีความจุ c ลบ f (ความจุที่เหลือ) และขอบย้อนกลับ (v, u) ที่มีความจุ f (การไหลที่ยกเลิกได้) เส้นทางที่เพิ่มขึ้นจะใช้ขอบของกราฟส่วนเหลือ ซึ่งช่วยให้อัลกอริทึมสามารถยกเลิกการตัดสินใจก่อนหน้านี้ได้

ทำไมเครื่องมือนี้ถึงใช้ BFS สำหรับเส้นทางที่เพิ่มขึ้น?

การเลือกเส้นทางที่เพิ่มขึ้นด้วย Breadth-First Search (Edmonds-Karp) รับประกันการสิ้นสุดในเวลาพหุนามโดยไม่คำนึงถึงความจุของขอบ Ford-Fulkerson แบบธรรมดาที่มีกลยุทธ์การหาเส้นทางแบบสุ่มอาจวนลูปเป็นจำนวนครั้งแบบเอกซ์โพเนนเชียลในข้อมูลนำเข้าที่ซับซ้อน และในกรณีความจุที่เป็นจำนวนอตรรกยะอาจไม่สิ้นสุดเลย นอกจากนี้ BFS ยังสร้างเส้นทางที่เพิ่มขึ้นที่สั้นที่สุด ซึ่งอ่านและทำความเข้าใจได้ง่ายกว่า

ขอบอิ่มตัวหมายถึงอะไร?

ขอบจะอิ่มตัวเมื่อการไหลเท่ากับความจุ ทำให้ไม่สามารถผลักการไหลเพิ่มเติมผ่านขอบนั้นได้ ขอบอิ่มตัวคือคอขวดของเครือข่าย และทุกๆ min-cut จะประกอบด้วยขอบอิ่มตัวทั้งหมดจากฝั่ง S ไปยังฝั่ง T ของคัต เครื่องมือนี้จะเน้นขอบอิ่มตัวด้วยสีแดงเพื่อให้คุณเห็นโครงสร้างคอขวดได้ทันที

อ่านเพิ่มเติม

อ้างอิงเนื้อหา หน้าหรือเครื่องมือนี้ว่า:

"เครื่องคำนวณการไหลในเครือข่าย (การไหลสูงสุด)" ที่ https://MiniWebtool.com/th/เครื่องคำนวณการไหลในเครือข่าย-การไหลสูงสุด/ จาก MiniWebtool, https://MiniWebtool.com/

โดยทีม miniwebtool อัปเดตเมื่อ: 22 เม.ย. 2026

คุณสามารถลองใช้ AI แก้ปัญหาคณิตศาสตร์ GPT ของเรา เพื่อแก้ไขปัญหาทางคณิตศาสตร์ของคุณผ่านคำถามและคำตอบด้วยภาษาธรรมชาติ.

เครื่องคำนวณการไหลในเครือข่าย (การไหลสูงสุด)

เกี่ยวกับ เครื่องคำนวณการไหลในเครือข่าย (การไหลสูงสุด)

ปัญหาการไหลสูงสุดคืออะไร?

อัลกอริทึมทำงานอย่างไร — Ford-Fulkerson ด้วย BFS

ทฤษฎีบท Max-Flow Min-Cut

คุณสมบัติที่สร้างมาเพื่อการเรียนรู้

รูปแบบข้อมูลนำเข้า

1. รายการขอบพร้อมความจุ

2. เมทริกซ์ความจุ

การประยุกต์ใช้การไหลสูงสุด

ตัวอย่างการคำนวณ

วิธีใช้เครื่องคำนวณนี้

ข้อจำกัด

คำถามที่พบบ่อย

ปัญหาการไหลสูงสุดคืออะไร?

วิธี Ford-Fulkerson คืออะไร?

min-cut ของเครือข่ายการไหลคืออะไร?

กราฟส่วนเหลือคืออะไร?

ทำไมเครื่องมือนี้ถึงใช้ BFS สำหรับเส้นทางที่เพิ่มขึ้น?

ขอบอิ่มตัวหมายถึงอะไร?

อ่านเพิ่มเติม

การดำเนินการทางคณิตศาสตร์ขั้นสูง:

เครื่องมือเด่น: