Вот задачка
"Предприятие, где вы работаете выиграло тендер на постройку сети лунных станций (количество станций оговорено). Вы на другой же день представили руководству готовый топологический план сети. Однако ваш начальник сказал, что решение подобных вопросов не в вашей компетенции, и план сети предстоит выбрать именно ему. В отместку вы решили подготовить полный список всех вариантов организации такой сети. Как профессионал вы, разумеется, в курсе, что в сети не должно быть «лишних» линий коммуникации."
Понятно, что нам нужны все связные графы с N вершинами, но что-то данных маловато. В постановке задачи еще записано, что надо юзнуть какой-нибудь конкретный алгоритм на графах, это сбивает. Я на свой вкус попробовал бы полный перебор с проверкой на связность. Но что-то не хочется, ибо вот последовательность числа всевозможных графов с n вершинами:
http://oeis.org/A000088. Может есть что-то поинтересней? Про циклы эйлера, гамильтона думал, они тут ни при чем.
02.05.2015, 12:16 
