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

จากวิกิพีเดีย สารานุกรมเสรี

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

1. ค่าของแต่ละเส้นเชื่อม จะไม่เกินน้ำหนักของเส้นเชื่อมนั้น (หรือเรียกว่า ความจุ (capacity))

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

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

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

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

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


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