Рассмотрим все возможные тройки цифр в качестве 1000 вершин ориентированного графа. Дугу между двумя вершинами проведем тогда и только тогда когда последние две цифры первой вершины равны первым двум цифрам последней вершины. В нашем графе будет 1000 вершин каждая степени исхода и захода 100.

Существует ли в орграфе гамильтонова орцепь?

задан 21 Дек '16 3:38

изменен 21 Дек '16 3:38

Это вроде бы известный факт, но надо ссылку поискать.

(21 Дек '16 11:40) falcao

Мне понравилось как здесь построение Гамильтоновой цепи сводится к построению Эйлерова цикла уже в другом графе из 100 вершин и 1000 дуг. Попозже опишу этот процесс. А вообще это очень известная задача: какое наименьшее число клавиш с цифрами нужно нажать, чтобы в получаемой последовательности цифр имелись все варианты кодов из 3 цифр.

(21 Дек '16 14:23) abc

Я помню, что в книге Липского "Математика для программистов" есть какие-то примеры этого типа. Скажем, надо перечислить все двоичные последовательности данной длины, или все перестановки на n символах. Тогда строится длинное слово, у которого циклические подслова данной длины дают нужную перестановку, причём в единственном варианте.

Книги в бумажном варианте у меня нет, а в Сети я пробовал скачать, но без успеха. Так и не удалось пока выяснить, есть ли там это всё в готовом виде.

(21 Дек '16 18:16) falcao
1

@falcao, Липский "Математика для программистов": http://mexalib.com/download/10402

(24 Май '17 17:20) Isaev

@Isaev: спасибо. У меня бумажной версии книги нет, я её когда-то брал почитать у одного из коллег-программистов. А в Сети не смог найти. Теперь скачал, и буду заглядывать при случае.

(24 Май '17 18:11) falcao
10|600 символов нужно символов осталось
1

До Липского я так и не добрался, но здесь, видимо, имеется в виду такая идея. Рассматриваются двухразрядные числа в качестве вершин нового графа, и из ab в bc идёт стрелка с меткой abc. Тогда получается эйлеров орграф, так как входящих и выходящих стрелок для каждой вершины будет ровно 10. Тогда можно построить полный обход всех направленных рёбер по разу. Обходить можно почти как угодно, соблюдая какие-то простые ограничения -- наподобие того, как это происходит с алгоритмом Флёри для случая обычных эйлеровых графов.

Здесь интересно то, есть ли какая-то "симпатичная" закономерность для какого-нибудь из способов обхода. Возможно, её следует искать, начиная с примеров меньшего размера -- когда цифр не 10, а две, три, и так далее.

ссылка

отвечен 21 Дек '16 23:06

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

(22 Дек '16 1:00) abc

@abc: я где-то и когда-то эту идею встречал, но не помню, в связи с чем. В любом случае, это красивый пример.

(22 Дек '16 1:01) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×437

задан
21 Дек '16 3:38

показан
475 раз

обновлен
24 Май '17 18:11

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

по почте:

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

по RSS:

Ответы

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

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