Высшая проба

[Nikita432472]

В стране шесть городов: А, Б, В, Г, Д и Е. Их хотят связать
пятью авиалиниями так, чтобы из каждого города можно было (возможно, с пересадками)
долететь до любого другого. Сколькими различными способами это можно сделать?

Как можно решить эту задачу не применяя теорему Кэли? Ведь на олимпиадах не должны столько требовать.

[levtsn]

Тут вроде число перестановок, кроме симметричных. Соответственно 6!×0.5. Или как?

[12d3]

Nikita432472 в сообщении #1240677 писал(а):

Как можно решить эту задачу не применяя теорему Кэли?

Ручками считать. Нарисовать все неизоморфные деревья о шести вершинах, а потом подсчитать различные способы перенумеровать вершины в каждом дереве.

[Pphantom]

Да, на полный перебор вариантов вместе с подсчетами уходит минут 15. Ну или действительно теорема Кэли - элементарная теория графов в общем-то обычно считается стандартной для участия в математических олимпиадах базой.