Сорок островов Лукьяненко

[dmd]

В романе "Рыцари сорока островов" описан мир сорока островов, каждый из которых соединён тремя мостами с тремя соседними островами.

Вопрос: сколько имеется принципиально-различных способов изобразить такие сорок островов так, чтобы мосты не пересекались?

(Оффтоп)

Один способ мне известен - "петля ромбиков". Чуть позже попробую её нарисовать.

[Neloth]

Можно набрать любое четное количество не меньшее шести из пар треугольников. Из одной вершины каждого треугольника выходит мост, соединяющий его с другим треугольником из этой пары, из двух других — мосты, соединяющие данную пару с предыдущей и последующей. Концы этой цепи всегда можно замкнуть, а если требуется количество, не кратное шести — между парами можно вставлять перемычки: два моста, которые должны были соединять одну пару с другой, разбиваются островами на два сегмента каждый и новые острова соединяются между собой.

-- Пт фев 12, 2016 22:58:44 --

Собственно говоря, суть-то тут в чем: берем цепочку из островов замкнутую, одна штука. Каждый остров в ней соединен с двумя другими, а нам нужно, чтоб с тремя. Поэтому берем вторую цепочку той же длины и соединяем попарно все острова в двух цепочках. Получилось вроде бы то, что нужно.

Теперь можно модифицировать эту цепь. Во первых, мосты, соединяющие острова из параллельных цепей, можно объединить в пары и каждую пару превратить в такую же двойную цепь, разбив мосты на сегменты. Во-вторых, двойную цепь можно местами превращать в одинарную, при чем каждый одинарный участок состоит из двух островов, каждый из которых соединяется с концом двойной цепи и с другим островом из этого одинарного сегмента.
В-третьих, можно соединить две двойных цепочки: если вставить в каждую из них одинарный фрагмент длиной более двух островов, средние острова будут соединены только двумя мостами, и к ним можно будет присоединить перемычку.

Вот ваши ромбики, например — это чередование участков двойной цепи с участками одинарной, а пары треугольников, которые пришли в голову мне — это двойная цепочка, соединенная перемычками из одинарных.

-- Пт фев 12, 2016 23:05:24 --

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

[Sender]

Иными словами, сколько имеется планарных кубических графов на сорока вершинах? Более $3443$, если верить данным, изложенным в статье http://arxiv.org/pdf/1207.7010v2.pdf. Там в $40$-й строке таблицы 2 подсчитаны некоторые подклассы интересующего нас множества графов.

-- Пт фев 12, 2016 23:22:10 --

Neloth в сообщении #1098936 писал(а):

Вот что действительно интересно — так это выяснить, можно ли соединить таким образом нечетное число островов, или показать, что нельзя.

Поскольку каждый остров соединён мостами ровно с тремя другими, количество мостов ровно в полтора раза больше количества островов.

[sergei1961]

Sender -"Иными словами, сколько имеется планарных кубических графов на сорока вершинах?" Любой такой граф пойдёт? Разве условие, что с тремя именно соседними-это не дополнительное ограничение?

[dmd]

Один вариант "петли" может быть таким:

$\xymatrix{ *+[o]+[F]{}\ar@{-}[r]\ar@{-}[rd]\ar@{-}[d]&*+[o]+[F]{}\ar@{-}[r]\ar@{-}[d]&*+[o]+[F]{}\ar@{-}[d]\ar@{-}[dl]&*+[o]+[F]{}\ar@{-}[d]\ar@{-}[dl]\ar@{-}[r]&*+[o]+[F]{}\ar@{-}[d]\ar@{-}[dl]\\ *+[o]+[F]{}\ar@{-}[d]\ar@{-}[dr]&*+[o]+[F]{}&*+[o]+[F]{}\ar@{-}[r]&*+[o]+[F]{}&*+[o]+[F]{}\ar@{-}[d]\ar@{-}[dl]\\ *+[o]+[F]{}\ar@{-}[d]\ar@{-}[r]&*+[o]+[F]{}\ar@{-}[dl]&*+[o]+[F]{}\ar@{-}[d]\ar@{-}[dr]\ar@{-}[dl]&*+[o]+[F]{}\ar@{-}[r]\ar@{-}[dr]&*+[o]+[F]{}\ar@{-}[d]\\ *+[o]+[F]{}\ar@{-}[d]&*+[o]+[F]{}\ar@{-}[d]\ar@{-}[r]&*+[o]+[F]{}\ar@{-}[r]&*+[o]+[F]{}\ar@{-}[r]&*+[o]+[F]{}\\ *+[o]+[F]{}\ar@{-}[d]\ar@{-}[dr]&*+[o]+[F]{}\ar@{-}[r]\ar@{-}[dr]&*+[o]+[F]{}\ar@{-}[d]\ar@{-}[r]&*+[o]+[F]{}\ar@{-}[dl]\ar@{-}[r]&*+[o]+[F]{}\ar@{-}[d]\ar@{-}[dl]\\ *+[o]+[F]{}\ar@{-}[d]\ar@{-}[r]&*+[o]+[F]{}\ar@{-}[dl]&*+[o]+[F]{}&*+[o]+[F]{}\ar@{-}[dr]\ar@{-}[r]&*+[o]+[F]{}\ar@{-}[d]\\ *+[o]+[F]{}\ar@{-}[d]&*+[o]+[F]{}\ar@{-}[d]\ar@{-}[dl]\ar@{-}[dr]&*+[o]+[F]{}\ar@{-}[d]\ar@{-}[r]\ar@{-}[dr]&*+[o]+[F]{}\ar@{-}[d]\ar@{-}[dr]&*+[o]+[F]{}\ar@{-}[d]\\ *+[o]+[F]{}\ar@{-}[r]&*+[o]+[F]{}\ar@{-}[r]&*+[o]+[F]{}&*+[o]+[F]{}\ar@{-}[r]&*+[o]+[F]{} }$


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

[INGELRII]

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

[dmd]

Есть такой вариант:

$\xymatrix{ *+[o]+[F]{}\ar@{-}[r]\ar@{-}[d]\ar@{-}[dr]&*+[o]+[F]{}\ar@{-}[r]\ar@{-}[dr]&*+[o]+[F]{}\ar@{-}[d]\ar@{-}[r]&*+[o]+[F]{}\ar@{-}[d]\ar@{-}[r]&*+[o]+[F]{}\ar@{-}[d]\ar@{-}[dl]\\ *+[o]+[F]{}\ar@{-}[d]\ar@{-}[r]&*+[o]+[F]{}\ar@{-}[d]&*+[o]+[F]{}\ar@{-}[r]&*+[o]+[F]{}&*+[o]+[F]{}\ar@{-}[d]\ar@{-}[dl]\\ *+[o]+[F]{}\ar@{-}[d]\ar@{-}[r]&*+[o]+[F]{}\ar@{-}[dl]&*+[o]+[F]{}\ar@{-}[d]\ar@{-}[dr]\ar@{-}[dl]&*+[o]+[F]{}\ar@{-}[r]\ar@{-}[d]&*+[o]+[F]{}\ar@{-}[d]\\ *+[o]+[F]{}\ar@{-}[d]&*+[o]+[F]{}\ar@{-}[d]\ar@{-}[r]&*+[o]+[F]{}\ar@{-}[d]&*+[o]+[F]{}\ar@{-}[r]&*+[o]+[F]{}\ar@{-}[d]\\ *+[o]+[F]{}\ar@{-}[d]\ar@{-}[dr]&*+[o]+[F]{}\ar@{-}[r]\ar@{-}[dr]&*+[o]+[F]{}\ar@{-}[d]&*+[o]+[F]{}\ar@{-}[dl]\ar@{-}[r]\ar@{-}[d]&*+[o]+[F]{}\ar@{-}[d]\\ *+[o]+[F]{}\ar@{-}[d]\ar@{-}[r]&*+[o]+[F]{}\ar@{-}[d]&*+[o]+[F]{}&*+[o]+[F]{}\ar@{-}[dr]\ar@{-}[r]&*+[o]+[F]{}\ar@{-}[d]\\ *+[o]+[F]{}\ar@{-}[d]\ar@{-}[r]&*+[o]+[F]{}\ar@{-}[dl]&*+[o]+[F]{}\ar@{-}[d]\ar@{-}[r]\ar@{-}[dl]&*+[o]+[F]{}\ar@{-}[d]\ar@{-}[dr]&*+[o]+[F]{}\ar@{-}[d]\\ *+[o]+[F]{}\ar@{-}[r]&*+[o]+[F]{}\ar@{-}[r]&*+[o]+[F]{}\ar@{-}[r]&*+[o]+[F]{}\ar@{-}[r]&*+[o]+[F]{} }$

[venco]

INGELRII в сообщении #1099139 писал(а):

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

На гексагональном поле выбираете произвольный шестиугольник с 40 узлами внутри. Эти 40 узлов можно множеством способов соединить рёбрами по 3 из каждого узла. Все мосты будут одинаковой длины.

[Neloth]

dmd в сообщении #1099150 писал(а):

Есть такой вариант:

Это пары звеньев двойной цепочки разделенные одинарными промежутками, если не считать перемычки справа, соединяющей два участка основной цепи и соединенной перемычками покороче еще с двумя участками.

Попробуйте, например, разорвать цепь.

[Sender]

venco в сообщении #1099163 писал(а):

На гексагональном поле выбираете произвольный шестиугольник с 40 узлами внутри.

Признаться, никак не могу взять в толк, о какой конструкции идёт речь . Вы не могли бы сделать поясняющий рисунок для небольшого количества узлов?

[dmd]

(вопрос по \xypolygon)

Подскажите, как рисовать вложенные \xypolygon? Т.е. как нарисовать аналог фигуры $C_{30}(D_{5h})$ из статьи?

[venco]

Sender в сообщении #1099243 писал(а):

venco в сообщении #1099163 писал(а):

На гексагональном поле выбираете произвольный шестиугольник с 40 узлами внутри.

Признаться, никак не могу взять в толк, о какой конструкции идёт речь . Вы не могли бы сделать поясняющий рисунок для небольшого количества узлов?

Вот полный пример:

[ET]

dmd в сообщении #1098909 писал(а):

Вопрос: сколько имеется принципиально-различных способов изобразить такие сорок островов так, чтобы мосты не пересекались?

А связность нужна?
А то каждая четверка островов может образовать отдельный мирок

[Sender]

Спасибо, venco.

(Оффтоп)

Просто гексагональное поле у меня ассоциировалось с чем-то таким:

http://mathworld.wolfram.com/HexagonalGrid.html

[Sender]

Sender в сообщении #1099519 писал(а):

А связность нужна?

У Лукьяненко, насколько помню, связность присутствовала.