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

Nguyễn Hồng Quốc và CS. Tập 132, Số 2A, 2023 16 𝑑𝑒𝑙𝑡𝑎 = (𝑒𝑖 − 𝑠𝑖 ) − ∑ (𝑒𝑘 − 𝑠𝑘) 𝑘∈𝑅 if (𝑑𝑒𝑙𝑡𝑎 > 0) then 𝑝𝑎𝑡ℎ = [𝑆, 𝑖, 𝑗, 𝑇]; break; if (𝑝𝑎𝑡ℎ ≠ ∅) then Tăng luồng trên đường đi 𝑝𝑎𝑡ℎ lên 1 đơn vị; Giảm luồng trên cung (𝑗, 𝑡) xuống |𝑅| đơn vị với mọi 𝑗 ∈ 𝑝𝑎𝑡ℎ; Giảm luồng cho các cung (𝑆, 𝑘), (𝑘, 𝑗) xuống 1 đơn vị với mọi 𝑘 ∈ 𝑅 và 𝑗 ∈ 𝑝𝑎𝑡ℎ; 𝐿𝑗 = 𝐿𝑗 − {𝑏𝑘} và 𝐿𝑗 = 𝐿𝑗 ∪ {𝑏𝑖} với mọi 𝑘 ∈ 𝑅 và 𝑖 ∈ 𝑝𝑎𝑡ℎ; 𝑉𝑎𝑙𝑢𝑒 = 𝑉𝑎𝑙𝑢𝑒 + 𝑑𝑒𝑙𝑡𝑎 While (𝑝𝑎𝑡ℎ ≠ ∅) return (𝑉𝑎𝑙𝑢𝑒, 𝐿 = {𝐿𝑗 |𝑗 ∈ 𝑊}); 3. Lập lịch lên các kênh: Sau khi đã tìm được luồng cực đại, chúng ta có các danh sách 𝐿. Như vậy, ta có được các chùm được lập lịch trên các kênh chính là các đỉnh tương ứng thuộc 𝐿𝑗. 4. Phân tích giải thuật tính đúng đắn vầ độ phức tạp: 4.1. Tính đúng đắn: Chứng minh lát cắt cực đại cho ta cách lập lịch tối ưu. • Ta có: Với mọi 𝑤𝑗 = 1 , . . . 𝑚, 𝐿𝑗 ≠ ∅ chính là tập các chùm được lập lịch. Với mỗi 𝑏𝑖 ∈ 𝐿𝑗 ta có 𝑓𝑖,𝑗 = 1 nên ∑ (𝑒𝑖 − 𝑠𝑖 )𝑓𝑖,𝑗 𝑏𝑖∈𝐿𝑗 chính là tổng độ dài các chùm được lập lịch lên kênh j. • Giải thuật tìm được luồng cực đại nên giá trị 𝑉𝑎𝑙𝑢𝑒(𝐶) đạt lớn nhất, do đó tổng chiều dài các chùm được lập lịch là lớn nhất. 4. 2. Độ phức tạp tính toán: Giải thuật gồm 3 bước độc lập và rõ ràng. Bước 3 có độ phức tạp tính toán là thấp nhất chỉ là 𝑂(𝑛), bây giờ chúng tôi phân tích độ phức tạp của hai bước còn lại: • Xây dựng mạng 𝑮 = (𝑽, 𝑬): Dễ thấy rằng, việc xây dựng tập cung nối các đỉnh thuộc 𝐼 và 𝑊 là có chi phí lớn nhất, việc này có độ phức tạp 𝑂(𝑛 × 𝑚);

• Tìm luồng cực đại: Do mạng 𝐺 có khả năng thông qua và luồng trên nó là số nguyên, nên giải thuật đảm bảo dừng. Chúng tôi sử dụng một biến thể của giải thuật Ford- Fulkerson là Edmonds-Karp [1] để tìm luồng cực đại kết hợp với giải thuật tìm kiếm nhị phân trong việc tìm đỉnh không chồng lấp (như đã trình bày ở mục 2. Tìm đường tăng luồng nên độ phức tạp tính toán của bước này là 𝑂(|𝑉| × |𝐸|2 × 𝑙𝑜𝑔 (|𝑉|)). Độ phức tạp tính toán của giải thuật: 𝑂(|𝑉| × |𝐸|2 × 𝑙𝑜𝑔 (|𝑉|)).