Cho mạng quang có 6 nút (A, B, C, D, E và F) với 8 liên kết (AB, AF, BC, BF, CD, CE, DE và EF). Giả sử các yêu cầu kết nối tuyến quang (lightpath) là: {A-B-C}, {A, B, C, E}, {F, E, C}, {B, C, D}, {B, F, E}. Kết quả gán bước sóng nào sau đây là đúng khi các bước sóng được gán theo giải thuật tô màu đồ thị ở lần tô thứ 3

Để giải quyết bài toán này, ta cần áp dụng giải thuật tô màu đồ thị để gán bước sóng cho các lightpath, đồng thời tuân thủ nguyên tắc sử dụng ít bước sóng nhất có thể và tránh xung đột bước sóng trên cùng một liên kết. Các yêu cầu kết nối tuyến quang (lightpath) là: {A-B-C}, {A, B, C, E}, {F, E, C}, {B, C, D}, {B, F, E}. Chúng ta cần xây dựng đồ thị xung đột, trong đó mỗi đỉnh đại diện cho một lightpath và một cạnh giữa hai đỉnh cho biết hai lightpath đó chia sẻ ít nhất một liên kết và do đó không thể sử dụng cùng một bước sóng. * **Lightpath 1: A-B-C** * **Lightpath 2: A, B, C, E** * **Lightpath 3: F, E, C** * **Lightpath 4: B, C, D** * **Lightpath 5: B, F, E** **Bước 1: Xác định các cặp lightpath xung đột:** * Lightpath 1 (A-B-C) xung đột với: * Lightpath 2 (A, B, C, E) (do chia sẻ các liên kết AB, BC) * Lightpath 4 (B, C, D) (do chia sẻ liên kết BC) * Lightpath 2 (A, B, C, E) xung đột với: * Lightpath 1 (A-B-C) * Lightpath 3 (F, E, C) (do chia sẻ liên kết CE) * Lightpath 4 (B, C, D) (do chia sẻ liên kết BC) * Lightpath 5 (B, F, E) (do chia sẻ liên kết BE, CE) * Lightpath 3 (F, E, C) xung đột với: * Lightpath 2 (A, B, C, E) * Lightpath 5 (B, F, E) (do chia sẻ liên kết FE, CE) * Lightpath 4 (B, C, D) xung đột với: * Lightpath 1 (A-B-C) * Lightpath 2 (A, B, C, E) * Lightpath 5 (B, F, E) xung đột với: * Lightpath 2 (A, B, C, E) * Lightpath 3 (F, E, C) **Bước 2: Tô màu đồ thị (gán bước sóng):** Chúng ta sẽ tô màu đồ thị theo thứ tự lightpath 1, 2, 3, 4, 5. Ở lần tô thứ 3, chúng ta đang gán bước sóng cho lightpath 3. * **Lần 1:** Gán lightpath 1 (A-B-C) bước sóng 1 (λ0). * **Lần 2:** Lightpath 2 (A, B, C, E) xung đột với lightpath 1, nên gán bước sóng 2 (λ1). * **Lần 3:** Lightpath 3 (F, E, C) xung đột với lightpath 2 (đã gán λ1). Kiểm tra xem nó có xung đột với lightpath 1 không. Vì lightpath 3 không xung đột với lightpath 1, ta có thể gán lightpath 3 bước sóng 1 (λ0). Như vậy, sau 3 lần tô, ta có: * Đỉnh 1 (Lightpath 1): Bước sóng 1 (λ0) * Đỉnh 2 (Lightpath 2): Bước sóng 2 (λ1) * Đỉnh 3 (Lightpath 3): Bước sóng 1 (λ0) Vậy, đáp án đúng là: Đỉnh 1: Bước sóng 1 (lamda 0), Đỉnh 2: bước sóng 2 (lamda 1), Đỉnh 3: bước sóng 1 (lamda 0).