В компьютерной игре главный герой перемещается по государству, состоящему из нескольких островов. Острова соединены мостами так, что из каждого можно добраться до любого другого. Герой обошёл все острова в поисках карты, пройдя по каждому мосту ровно один раз. Но на острове Тёмном он побывал целых 9 раз. Сколько мостов ведёт с острова Темного, если герой не с него начал и не на нём закончил свой поход?

18 Пояснение: - В эйлеровом маршруте, который проходит по каждому ребру ровно один раз и не начинается/не заканчивается на данной вершине, каждый раз, когда вершина проходит через неё (не как стартовая или конечная), маршрут входит в неё по одной дуге и выходит по другой. То есть используется две incident-рядыеEdges на такую посещение. - Значит число посещений вершины = deg(вершины) / 2. - Темная не является стартом и не является концом маршрута, значит каждая из её 9 посещений соответствуют прохождению через неё, и deg(Темного) = 2 * 9 = 18. Итак, у Темного 18 мостов.