01204512/congestion1

หน้านี้เป็นเอกสารประกอบวิชา 01204512

ปัญหา congestion minimization

ให้กราฟ $G=(V,E)$ และเซตของคู่ของจุดยอด $(s_{1},t_{1}),(s_{2},t_{2}),\ldots ,(s_{k},t_{k})$ จำนวน $k$ คู่ เราต้องการหาเซตของ path ที่เชื่อมจุดยอดแต่ละคู่ โดยต้องการทำให้จำนวน path ที่ผ่านเส้นเชื่อมใด ๆ มีค่าน้อยที่สุด (เราจะเรียกจำนวนผ่านที่ผ่านเส้นเชื่อมใด ๆ ว่าเป็น congestion ของเส้นเชื่อมนั้น)