1. **Nêu bài toán:** Cho đồ thị hướng biểu diễn các chuyến bay giữa các thành phố Boston, Newark, Miami, Detroit, Washington với số chuyến bay cụ thể. 2. **Phân tích từng trường hợp:** **a)** Một cạnh giữa các đỉnh biểu diễn các thành phố có chuyến bay theo hướng nào đó. - Đây là đồ thị có hướng (directed graph). - Mỗi cặp thành phố có ít nhất một cạnh hướng nếu có chuyến bay từ thành phố này đến thành phố kia. - Số cạnh là số cặp thành phố có chuyến bay (bỏ qua số chuyến bay cụ thể). **b)** Một cạnh giữa các đỉnh biểu diễn các thành phố cho mỗi chuyến bay theo hướng nào đó. - Đây là đồ thị đa hướng (directed multigraph). - Mỗi chuyến bay là một cạnh riêng biệt có hướng. - Ví dụ: Boston đến Newark có 4 chuyến bay nên có 4 cạnh hướng từ Boston đến Newark. **c)** Một cạnh giữa các đỉnh biểu diễn các thành phố cho mỗi chuyến bay theo cả hai chiều, thêm vào đó có một khuyến hiệu thị chuyến du lịch đặc biệt ngắm cảnh thành phố, cất cánh và hạ cánh tại Miami. - Đây là đồ thị đa vô hướng (undirected multigraph) vì mỗi chuyến bay được biểu diễn bằng một cạnh không hướng (cả hai chiều). - Khuyến hiệu đặc biệt là một chu trình bắt đầu và kết thúc tại Miami, có thể biểu diễn bằng một chu trình (cycle) trong đồ thị. **d)** Một cạnh từ một đỉnh biểu thị thành phố có chuyến bay tới một đỉnh khác biểu thị thành phố ở đó chuyến bay kết thúc. - Đây là đồ thị có hướng (directed graph). - Mỗi cạnh biểu diễn một chuyến bay từ thành phố xuất phát đến thành phố đích. - Không phân biệt số chuyến bay, chỉ có một cạnh cho mỗi cặp thành phố có chuyến bay. **e)** Một cạnh cho mỗi chuyến bay từ một đỉnh biểu thị thành phố nơi chuyến bay bắt đầu tới một đỉnh khác biểu thị thành phố ở đó chuyến bay kết thúc. - Đây là đồ thị đa hướng (directed multigraph). - Mỗi chuyến bay là một cạnh riêng biệt có hướng. 3. **Tóm tắt:** - Trường hợp a, d: đồ thị có hướng, mỗi cặp thành phố có tối đa một cạnh hướng. - Trường hợp b, e: đồ thị đa hướng, mỗi chuyến bay là một cạnh riêng. - Trường hợp c: đồ thị đa vô hướng, mỗi chuyến bay là một cạnh không hướng, có chu trình đặc biệt bắt đầu và kết thúc tại Miami. 4. **Kết luận:** - Loại đồ thị được dùng phụ thuộc vào cách biểu diễn cạnh (một hay nhiều cạnh cho mỗi chuyến bay, có hướng hay không hướng).