Câu hỏi 12
Vương quốc Anisotropy bao gồm $n$ thành phố. Cứ hai thành phố thì tồn tại chính xác một con đường một chiều nối liền chúng. Chúng ta nói rằng đường đi từ $X$ đến $Y$ là một dãy các con đường sao cho người ta có thể di chuyển từ $X$ đến $Y$ dọc theo dãy này mà không cần quay lại thành phố đã ghé thăm. Một tập hợp các đường đi được gọi là đa dạng nếu không có đường nào thuộc hai hoặc nhiều đường đi trong tập hợp đó.
Đặt $A$ và $B$ là hai thành phố phân biệt ở Anisotropy. Đặt $N_{A B}$ biểu thị số lượng đường đi cực đại trong một tập hợp các đường đi đa dạng từ $A$ đến $B$. Tương tự, hãy đặt $N_{B A}$ biểu thị số lượng đường đi cực đại trong một tập hợp các đường đi đa dạng từ $B$ đến $A$. Chứng minh rằng đẳng thức $N_{A B}=N_{B A}$ đúng khi và chỉ khi số đường đi ra từ $A$ bằng số đường đi ra từ $B$.
Đặt $A$ và $B$ là hai thành phố phân biệt ở Anisotropy. Đặt $N_{A B}$ biểu thị số lượng đường đi cực đại trong một tập hợp các đường đi đa dạng từ $A$ đến $B$. Tương tự, hãy đặt $N_{B A}$ biểu thị số lượng đường đi cực đại trong một tập hợp các đường đi đa dạng từ $B$ đến $A$. Chứng minh rằng đẳng thức $N_{A B}=N_{B A}$ đúng khi và chỉ khi số đường đi ra từ $A$ bằng số đường đi ra từ $B$.