Câu hỏi 3
Hãng hàng không Beaver Airlines có những đường bay kết nối giữa các thành phố như hình vẽ dưới đây.
Để hạn chế tình trạng ô nhiễm môi trường, hãng hàng không cam kết bỏ một số đường bay. Tuy nhiên các đường bay còn lại phải đảm bảo rằng hải ly ở thành phố bất kì có thể đến một thành phố bất kì khác. Ví dụ nếu đường bay giữa hai thành phố San Francisco và Washington, D.C bị bỏ, thì hải ly có thể di chuyển giữa hai thành phố bằng cách đi qua New York. Hỏi số lượng đường bay tối đa mà hãng hàng không Beaver Airline có thể bỏ là bao nhiêu?
Để hạn chế tình trạng ô nhiễm môi trường, hãng hàng không cam kết bỏ một số đường bay. Tuy nhiên các đường bay còn lại phải đảm bảo rằng hải ly ở thành phố bất kì có thể đến một thành phố bất kì khác. Ví dụ nếu đường bay giữa hai thành phố San Francisco và Washington, D.C bị bỏ, thì hải ly có thể di chuyển giữa hai thành phố bằng cách đi qua New York. Hỏi số lượng đường bay tối đa mà hãng hàng không Beaver Airline có thể bỏ là bao nhiêu?