MỘT HƯỚNG TIẾP CẬN LẬP LỊCH NHÓM TỐI ƯU TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG

jos.hueuni.edu.vn Tập 132, Số 2A, 2023 13 1. Xây dựng mạng 𝑮 = (𝑽, 𝑬) như sau: • Tập các đỉnh 𝑉 = {𝐼} ∪ {𝑊} ∪ { 𝑆, 𝑇}, trong đó, 𝐼 là tập các chùm, 𝑊 là tập các kênh, 𝑆 là đỉnh phát, và 𝑇 là đỉnh thu. • Tập các cạnh 𝐸 = {(𝑆, 𝑏𝑖=1:𝑛), (𝑤𝑗=1:𝑚, 𝑇)} ∪ {(𝑏𝑖 , 𝑤𝑗)| 𝑠𝑖 ≥ 𝐿𝑎𝑢𝑡𝑤𝑗 ; ∀𝑏𝑖 ∈ 𝐼, 𝑤𝑗 ∈ 𝑊} • Khả năng thông qua của các cung của 𝐺 được khởi tạo như sau: 𝑐𝑆,𝑖 = 1, 𝑐𝑖,𝑗 = 1, 𝑐𝑗,𝑇 = deg−(𝑤𝑗 ); ; trong đó deg−(𝑤𝑗) là tổng số các cung đi vào đỉnh 𝑤𝑗 , 𝑖 = 1,2, … , 𝑛 và 𝑗 = 1,2, … , 𝑚. • Luồng trên tất cả các cung của 𝐺 được khởi tạo bằng 0. S b1 b3 b6 w1 b5 b2 b4 w2 T F=1 L1={b1} L2= Æ S b1 b3 b6 w1 b5 b2 b4 w2 T F=1 L1={b2} L2= Æ (a) (b) S b1 b3 b6 w1 b5 b2 b4 w2 T F=1 L1={b1,b5} f=1 L2={b3, b6} (c) Hình 4. Các bước tìm đường tăng luồng trên mạng 𝐺 = (𝑉, 𝐸) Hình 5. mô tả mạng 𝐺, luồng (flow) và khả năng thông qua (capacity) của nó. Sau khi có mạng 𝐺, bài toán lập lịch nhóm có thể được giải quyết bằng việc tìm luồng cực đại trên 𝐺. Giả sử