บทความนี้ไม่มีจาก |
ในทฤษฎีกราฟ การไหลในเครือข่าย (อังกฤษ: network flow) คือ การกำหนดค่าให้กับเส้นเชื่อมในกราฟระบุทิศทางถ่วงน้ำหนัก (เรียกว่า เครือข่ายการไหล (อังกฤษ: Flow network) ในกรณีนี้) ซึ่ง
- ค่าของแต่ละเส้นเชื่อม จะไม่เกินน้ำหนักของเส้นเชื่อมนั้น (หรือเรียกว่า ความจุ (capacity))
- การไหลเข้าทั้งหมดของจุดต่อ (ผลบวกของค่าของเส้นเชื่อมที่เข้ามาในจุดต่อนั้น) จะเท่ากับการไหลออกทั้งหมดเสมอ ยกเว้นจุดต่อพิเศษ 2 จุด คือ s และ t จุดต่อ s จะมีการไหลออกแต่ไม่มีการไหลเข้า จุดต่อ t จะมีการไหลเข้าแต่ไม่มีการไหลออก
ในกรณีนี้ s คือ แหล่งต้นทาง (source) และ t คือ แหล่งปลายทาง (sink)
ในการทำความเข้าใจกับการไหลในเครือข่าย ให้นึกถึงภาพท่อน้ำ ท่อแต่ละท่อจะมีความกว้างที่แน่นอน ซึ่งจะยอมให้น้ำไหลผ่านในปริมาณที่แน่นอน ที่ใดก็ตามที่ท่อเชื่อมกัน ปริมาณน้ำที่ไหลเข้าไปในตัวเชื่อม จะต้องเท่ากับปริมาณน้ำที่ไหลออก มิฉะนั้นแล้ว น้ำจะไหลออกจนหมดหรือเราจะเพิ่มน้ำขึ้นมา เราจะต้องมีทางเข้าของน้ำ นั่นคือแหล่งต้นทาง และเราจะต้องมีทางออกน้ำ ซึ่งแทนแหล่งปลายทาง การไหล (flow) จะเป็นเส้นทางที่น้ำไหลจากแหล่งต้นทางไปแหล่งปลายทางได้ ดังนั้น ปริมาณของน้ำที่ไหลออกจากทางออกจะคงที่ และการไหลรวม (total flow) ของการไหลในเครือข่าย คืออัตราการไหลของน้ำที่ออกจากทางออก
ปัญหาที่รู้จักกันดี คือการหา (max flow) ซึ่งเป็นค่าการไหลรวมสูงสุดของกราฟที่กำหนดให้ ขั้นตอนวิธีที่ใช้ในการแก้ปัญหานี้ที่รู้จักกันมากที่สุดคือ ขั้นตอนวิธีของฟอร์ด-เฟอลเกอสัน และ
มีปัญหาหลายปัญหาที่แก้ได้ด้วย ถ้าเราแทนด้วยเครือข่ายการไหล เช่น การจับคู่สองส่วน (bipartite matching)
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
bthkhwamniimmikarxangxingcakaehlngthimaidkrunachwyprbprungbthkhwamni odyephimkarxangxingaehlngthimathinaechuxthux enuxkhwamthiimmiaehlngthimaxacthukkhdkhanhruxlbxxk eriynruwacanasaraemaebbnixxkidxyangiraelaemuxir inthvsdikraf karihlinekhruxkhay xngkvs network flow khux karkahndkhaihkbesnechuxminkrafrabuthisthangthwngnahnk eriykwa ekhruxkhaykarihl xngkvs Flow network inkrnini sung khakhxngaetlaesnechuxm caimekinnahnkkhxngesnechuxmnn hruxeriykwa khwamcu capacity karihlekhathnghmdkhxngcudtx phlbwkkhxngkhakhxngesnechuxmthiekhamaincudtxnn caethakbkarihlxxkthnghmdesmx ykewncudtxphiess 2 cud khux s aela t cudtx s camikarihlxxkaetimmikarihlekha cudtx t camikarihlekhaaetimmikarihlxxk inkrnini s khux aehlngtnthang source aela t khux aehlngplaythang sink inkarthakhwamekhaickbkarihlinekhruxkhay ihnukthungphaphthxna thxaetlathxcamikhwamkwangthiaennxn sungcayxmihnaihlphaninprimanthiaennxn thiidktamthithxechuxmkn primannathiihlekhaipintwechuxm catxngethakbprimannathiihlxxk michannaelw nacaihlxxkcnhmdhruxeracaephimnakhunma eracatxngmithangekhakhxngna nnkhuxaehlngtnthang aelaeracatxngmithangxxkna sungaethnaehlngplaythang karihl flow caepnesnthangthinaihlcakaehlngtnthangipaehlngplaythangid dngnn primankhxngnathiihlxxkcakthangxxkcakhngthi aelakarihlrwm total flow khxngkarihlinekhruxkhay khuxxtrakarihlkhxngnathixxkcakthangxxk pyhathiruckkndi khuxkarha max flow sungepnkhakarihlrwmsungsudkhxngkrafthikahndih khntxnwithithiichinkaraekpyhanithiruckknmakthisudkhux khntxnwithikhxngfxrd efxlekxsn aela mipyhahlaypyhathiaekiddwy thaeraaethndwyekhruxkhaykarihl echn karcbkhusxngswn bipartite matching bthkhwamkhxmphiwetxr xupkrntang hruxekhruxkhayniyngepnokhrng khunsamarthchwywikiphiediyidodykarephimetimkhxmuldkhk