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 15 Tạo cung 𝑤𝑗 đến đỉnh thu 𝑇, 𝐸 = 𝐸 ∪ {(𝑤𝑗, 𝑇)}; if (𝑠𝑖 > 𝐿𝑎𝑢𝑡𝑤𝑗 ) then Tạo cung từ 𝑏𝑖 đến kênh 𝑤𝑗 , 𝐸 = 𝐸 ∪ {(𝑏𝑖, 𝑤𝑗 )}; deg−(𝑤𝑗) = deg−(𝑤𝑗); 𝑐𝑖,𝑗 = 1; 𝑐𝑗,𝑇 = deg−(𝑤𝑗); return 𝑮 = (𝑽, 𝑬); 2. Tìm đường tăng luồng: Sau khi mạng 𝐺 = (𝑉, 𝐸) được xây dựng thực hiện các cộng việc sau. • Đường tăng luồng là đường đi từ 𝑆 đến 𝑇 sao cho làm tăng giá trị lát cắt 𝐶 = (𝑉 − {𝑇}, {𝑇}), giá trị này được tình theo công thức dưới đây: 𝑉𝑎𝑙𝑢𝑒(𝐶) = ∑ ∑ (𝑒𝑖 − 𝑠𝑖)𝑓𝑖,𝑗 𝑏𝑖∈𝐿𝑗 𝑚 𝑗=1 (2) • Tăng luồng lên một đơn vị trên cung (𝑢, 𝑣) cần thảo mãn các điều kiện tăng luồng trên mạng 𝐺 như sau: − Có thể tăng luồng: 𝑓𝑢,𝑣 < 𝑐𝑢,𝑣 đối với tất cả các cung (𝑢, 𝑣); − Cân bằng luồng: Nếu cung (𝑢, 𝑣) là cung nối hai đỉnh 𝑏𝑖 và 𝑤𝑗 thì giảm luồng trên các cung (𝑏𝑘, 𝑤𝑗 ), (𝑠, 𝑏𝑘) trong đó 𝑏𝑘 là đỉnh thuộc 𝐿𝑗 và chồng lấp với 𝑏𝑖 (chồng lấp của hai đỉnh thuộc 𝐼 chính là chồng lấp của hai chùm tương ứng). Để tìm các đỉnh 𝑏𝑘 chúng tôi sử dụng phương pháp tìm kiếm nhị phân. Nếu luồng tới đỉnh 𝑤𝑗 được tăng hoặc giảm thì cập nhật lại danh sách 𝐿𝑗. Chi tiết giải thuật như sau: Function 𝐹𝑀𝐹_𝑂𝑃𝑇(𝐺): Input: Mạng 𝐺 = (𝑉, 𝐸); Output: Tập các đỉnh trong 𝐿𝑗 với mọi 𝑗 thuộc 𝑊; Process Khởi tạo 𝐺′ = 𝐺 và 𝑓𝑢,𝑣 = 0 với mọi 𝑢, 𝑣 ∈ 𝑉; 𝐿𝑗 = ∅ với mọi 𝑗 thuộc 𝑊; 𝑉𝑎𝑙𝑢𝑒 = 0; Do 𝑃𝑎𝑡ℎ = ∅; foreach 𝑖, 𝑗 ∈ 𝑉 − {𝑆, 𝑇} do if (𝑓𝑆,𝑖 < 𝑐𝑆,𝑖) ∧ (𝑓𝑖,𝑗 < 𝑐𝑆,𝑗) ∧ (𝑓𝑗,𝑇 < 𝑐𝑗,𝑇) then 𝑅 = {𝑘} trong đó 𝑏𝑘 ∈ 𝐿𝑗 và chồng lấp với 𝑏𝑖;