Câu hỏi 5
Một quốc gia có $n$ thành phố, trong đó $n \geq 100$ là một số nguyên dương. Một số cặp thành phố được nối với nhau bởi các chuyến bay (hai chiều). Với hai thành phố $A$ và $B$, một đường đi là một dãy các thành phố đôi một khác nhau $C_0, C_1, C_2, \ldots, C_k, C_{k+1}$ sao cho có chuyến bay giữa $C_i$ và $C_{i+1}$ với mọi $0 \leq i \leq k$, với $C_0 = A$ và $C_{k+1} = B$.
Một đường đi dài giữa $A$ và $B$ được định nghĩa là một đường đi sao cho không có đường đi nào khác có nhiều đỉnh hơn. Tương tự, một đường đi ngắn được định nghĩa là một đường đi có ít đỉnh nhất. Đặc biệt, nếu $A$ và $B$ có chuyến bay trực tiếp thì đó là đường đi ngắn nhất.
Giả sử rằng với mọi cặp thành phố $A$ và $B$ trong nước, tồn tại một đường đi dài và một đường đi ngắn giữa chúng không có thành phố chung nào (ngoại trừ $A$ và $B$). Với $n$ cho trước, tìm tất cả các giá trị có thể của số chuyến bay trong nước.
Một đường đi dài giữa $A$ và $B$ được định nghĩa là một đường đi sao cho không có đường đi nào khác có nhiều đỉnh hơn. Tương tự, một đường đi ngắn được định nghĩa là một đường đi có ít đỉnh nhất. Đặc biệt, nếu $A$ và $B$ có chuyến bay trực tiếp thì đó là đường đi ngắn nhất.
Giả sử rằng với mọi cặp thành phố $A$ và $B$ trong nước, tồn tại một đường đi dài và một đường đi ngắn giữa chúng không có thành phố chung nào (ngoại trừ $A$ và $B$). Với $n$ cho trước, tìm tất cả các giá trị có thể của số chuyến bay trong nước.