Да фиг с ней, этой олимпиадой! Задачи же интересные... Я возвратил эту обратно.
В стране шесть городов: А, B, C, D, E и F. Их хотят связать пятью авиалиниями так, чтобы из каждого города можно было (быть может, с пересадками) долететь до любого другого. Сколькими различными способами это можно сделать?

задан 20 Янв '13 12:44

изменен 20 Янв '13 13:13

%D0%A5%D1%8D%D1%88%D0%9A%D0%BE%D0%B4's gravatar image


5525

Это, кажется, называется "дерево".

(20 Янв '13 12:50) DocentI

Да, оно самое. А что, есть готовая формула для количества деревьев?

(20 Янв '13 12:58) chameleon

Кстати, а что считать "различными способами"? Форму сети или также ее расположение? Если только форму, получаем 6 решений (см. мой ответ)

(20 Янв '13 15:51) DocentI

Города упорядочены, так что различные - это и по расположению, в том числе. То есть, различная матрица графа = различные способы.

(20 Янв '13 16:04) chameleon
10|600 символов нужно символов осталось
2

Общая формула в этом случае имеется: число способов равно $%n^{n-2}$%, что совпадает с найденным выше ответом при $%n=6$%. Это довольно старый (конец XIX века) классический результат в теории графов: теорема Кэли (Cayley) о перечислении размеченных деревьев.

Известно много доказательств, но все они достаточно нетривиальны. Лично мне больше всего нравится рассуждение, которое каждому размеченному дереву сопоставляет код по некоторому правилу. Например, есть весьма удобное кодирование Прюфера, хотя это далеко не единственный способ.

ссылка

отвечен 22 Янв '13 14:42

да вообще-то не совпадает, ну да ладно

(22 Янв '13 15:14) chameleon

Да, я невнимательно посмотрел. Должно быть, конечно, $%6^4=1296$% --- просто числа очень похожие. Там в случае (5) должно быть слагаемое не 60, а 120: мы имеем 6 вариантов для "узла", 5 вариантов для соседней с ним "невисячей" вершины, и 4 для крайней слева на рисунке. Итого $%6\cdot5\cdot4=120$%, то есть ответ увеличивается на 60, и получается 1296, как и должно быть.

Кстати, могу описать общий принцип кодирования, если хотите. Я сейчас понял, что это можно сделать достаточно коротко.

(22 Янв '13 15:31) falcao

Спасибо, не надо. Мне имён будет достаточно, чтоб самому нагуглить.

(22 Янв '13 15:34) chameleon

Жаль, что я ошиблась в подсчете, а то заметила бы, что это степень 6 :-)

(22 Янв '13 17:14) DocentI

Да, это часто бывает, что числа "говорят" что-то сами за себя, и по ним можно бывает сформулировать общую гипотезу.

А я когда на число посмотрел, то мне сразу в нём увиделось 1296, то есть я даже не стал вчитываться, потому что сам по себе метод подсчёта вполне естественный. Вот если бы там вместо 9 было 7, то тогда бы "подвох" сразу стал заметнее :)

(22 Янв '13 17:24) falcao
10|600 символов нужно символов осталось
2

В общем случае задача перечисления графов (в данном случае - помеченных деревьев) достаточно сложна. Но для небольшой размерности можно применить перебор. Например, перечислить всевозможные топологические классы, а потом посмотреть, сколькими способами их можно пометить буквами.

Дополнение. Вот все топологически различные деревья (перебор делала по длине самой длинной цепочки):
alt text

В первом случае пометки можно расставить 6!/2 = 360 способами, так как фигура имеет одну симметрию (можно пометить вершины в обратном порядке, получим ту же сеть)

Во втором - также (можно безболезненно поменять местами листья, висящие на "коротких черенках".

В третьем случае взаимозаменяемы длинные отростки.

В четвертом дереве можно поменять местами два "куста" (две тройные вершины), а также листья в каждом из них. Получаем 6!/8 вариантов.

В пятом можно произвольно переставлять листья на коротких черенках, 3! = 6 перестановок.

В шестом случае есть всего 6 вариантов (в зависимости от того, какой именно город лежит в центре).

Итого получаем 360 + 360 + 360 + 90 + 60 + 6 = 1236 вариантов.

Когда построите более общее решение, сравните, может, наши ответы совпадут! ;-))
Исправление. В случае 5 имеем 6!/6 = 120 вариантов. Общая сумма - 1296.

ссылка

отвечен 20 Янв '13 13:05

изменен 22 Янв '13 17:26

Как-то это несерьезно... Я всё-таки попытаюсь вывести формулу на общий случай. Если не будет ответов за сутки, то помечу принятым

(20 Янв '13 13:16) chameleon

А Вы смотрели литературу по перечислению графов? Ее очень много, и там решается множество задач. В частности, методом производящих функций.

(20 Янв '13 15:17) DocentI

Ну не знаю... По крайней мере, составить алгоритм нахождения этого числа можно, при помощи динамического программирования, и по идее он должен иметь полиномиальную сложность.

(20 Янв '13 16:07) chameleon
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×869
×119

задан
20 Янв '13 12:44

показан
1173 раза

обновлен
22 Янв '13 17:26

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru