MergedFile

picture. CO2 emissions are a major cause of global warming.
In order to reduce CO2 emissions, the airline wants to drop
some of the flight routes without disrupting the ability of the
customers to fly to any city. For example, if the flight route
between San Francisco and Washington, D.C. were to be
dropped, customers could fly from San Francisco to New York
and then from New York to Washington, D.C. For the flight
routes shown, what is the maximum number of routes the
airline can drop?
У Авиакомпании Bebras есть много авиарейсов между
городами, как показано ниже. Из-за сокращения бюджета
авиакомпания хочет убрать некоторые рейсы, но чтобы
при этом можно было долететь (с пересадками) из каждого
города в любой другой. Например, рейс между San
Francisco и Washington, D.C. можно убрать, так как можно
перелететь из San Francisco в New York, а потом из New
York в Washington, D.C. Для показанной карты рейсов,
какое наибольшее число рейсов можно убрать, чтобы при
этом можно было (с пересадками) долететь из каждого
города в любой другой на карте?
Bebras Airlines aviakompaniyasida shaharlar o'rtasida ko'plab
reyslar mavjud, quyida ko'rsatilgan. Byudjetning qisqarishi
sababli aviakompaniya ba'zi reyslarni olib tashlamoqchi, ammo
u har bir shahardan boshqa shaharga uchishi uchun (boshqa
samolyotga o’tish bilan). Masalan, San-Fransisko va
Vashington o'rtasidagi parvoz, olib tashlanishi mumkin, chunki
San-Frantsiskodan Nyu-Yorkka, keyin Nyu-Yorkdan
Vashingtonga uchish mumkin. Ko'rsatilgan parvoz xaritasida
har bir shahardan xaritaning boshqa qismiga parvoz qilish
uchun qancha parvozlarni olib tashlashingiz mumkin?

---

11. 4)