Nam đang tìm hiểu cách các máy tính trong 1 mạng được kết nối với nhau. Mạng máy tính có N máy tính được kết nối bởi N - 1 dây cáp mạng. Các máy tính được đánh số từ 1 đến N và mỗi dây cáp mạng nối hai máy tính khác nhau.
Nam muốn tìm hành trình tối ưu có độ dài chính xác là 2 nếu một gói dữ liệu được gửi từ máy u đến máy v. Đường đi ngắn nhất giữa u và v phải đi qua đúng một máy trung gian (tức là đường đi hành trình có độ dài chính xác là 2).
Mô tả chi tiết: Một hành trình dài K từ máy S đến máy T là một dãy thứ tự các máy: V_0 → V_1 → V_2 → ⋯ → V_k. Trong đó:
- V_0=S
- V_k =T
- Với mọi chỉ số hợp lệ i, V_i và V_{i+1} được kết nối trực tiếp bằng một dây cáp.
Một hành trình được gọi là tối ưu nếu:
- Không có hành trình nào ngắn hơn với cùng điểm bắt đầu và kết thúc.
- Hai hành trình: V_0 → V_1 → V_2 → ⋯ → V_k và W_0 → W_1→ W_2 → ⋯ → W_l được xem là khác nhau nếu k≠ℓ hoặc tồn tại ít nhất một chỉ số j sao cho V_i≠ W_j
Yêu cầu bài toán: Nam cần xác định có bao nhiêu các cặp máy tính có thể được nối với nhau bằng một hành trình tối ưu có độ dài chính xác là 2.
