อ่าน 1 นาที
การไหลแบบซับโมดูลาร์
ในทฤษฎี การเพิ่มประสิทธิภาพเชิงการจัดเรียง การไหลย่อยโมดูลาร์ เป็นปัญหาการเพิ่มประสิทธิภาพทั่วไปที่รวมถึงกรณีพิเศษต่างๆ เช่นปัญหา การไหลต้นทุนต่ำสุด การตัดกันของเมทริกซ์...
การไหลแบบซับโมดูลาร์
ในทฤษฎีการเพิ่มประสิทธิภาพเชิงการจัดเรียงการไหลย่อยโมดูลาร์เป็นปัญหาการเพิ่มประสิทธิภาพทั่วไปที่รวมถึงกรณีพิเศษต่างๆ เช่นปัญหาการไหลต้นทุนต่ำสุดการตัดกันของเมทริกซ์และปัญหาการคำนวณไดจอยน์ น้ำหนักต่ำสุด ในกราฟทิศทางที่ มีน้ำหนัก ปัญหา นี้ได้รับการกำหนดขึ้นครั้งแรกโดยJack Edmondsและ Rick Giles [ 1 ]และสามารถแก้ไขได้ในเวลาพหุนาม[ 2 ] [ 3 ] [ 4 ]
ในปัญหาการไหลต้นทุนต่ำสุดแบบคลาสสิก อินพุตคือเครือข่ายการไหลที่มีความจุที่กำหนด ซึ่งระบุขีดจำกัดล่างและบนของปริมาณการไหลต่อขอบ รวมถึงต้นทุนต่อหน่วยการไหลตามแต่ละขอบ เป้าหมายคือการหาสระบบของปริมาณการไหลที่สอดคล้องกับความจุบนแต่ละขอบ สอดคล้องกับกฎของ Kirchhoffที่ว่าปริมาณการไหลทั้งหมดที่เข้าสู่แต่ละจุดยอดเท่ากับปริมาณการไหลทั้งหมดออก และมีต้นทุนรวมต่ำสุด ในการไหลแบบซับโมดูลาร์เช่นกัน จะมีการกำหนดฟังก์ชันเซตซับโมดูลาร์บนเซตของจุดยอดของกราฟ แทนที่จะสอดคล้องกับกฎของ Kirchhoff ข้อกำหนดคือ สำหรับทุกเซตของจุดยอด การไหลส่วนเกิน (ฟังก์ชันที่แมปเซตไปยังความแตกต่างระหว่างการไหลเข้าและการไหลออก) จะต้องมีค่าไม่เกินค่าที่กำหนดโดยฟังก์ชันซับโมดูลาร์[ 4 ]
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ การไหลแบบซับโมดูลาร์
ในทฤษฎี การเพิ่มประสิทธิภาพเชิงการจัดเรียง การไหลย่อยโมดูลาร์ เป็นปัญหาการเพิ่มประสิทธิภาพทั่วไปที่รวมถึงกรณีพิเศษต่างๆ เช่นปัญหา การไหลต้นทุนต่ำสุด การตัดกันของเมทริกซ์...