Здравствуйте, ansi, Вы писали:

A>В некотором государстве любой город соединен авиалиниями не более чем с тремя другими. Из любого города в любой другой можно долететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в государстве?

10

Имеем:

Точку начала пути. Три точки, в которые можем попасть, из данной точки. Шесть точек (т.к. один путь занят под путь из точки начала пути в заданную точку), в которые можем попасть из точки начала пути. Итого: 1+3+6 = 10. Больше быть не может, в силу условия достижимости.

Граф путей, например такой:

0|1,2,3
1|0,4,5
2|0,6,7
3|0,8,9
4|1,6,8
5|1,7,9
6|2,4,9
7|2,5,8
8|3,4,7
9|3,5,6

---
С уважением, Сиваков Константин.