Обойти как можно больше клеток, как нарисовать путь?
В задании для младших классов нужно попытаться обойти путь по белым клеточкам. После нескольких попыток у меня получилось использовать максимальное количество клеток (нетронутой осталась единственная клеточка).
Результат смотрите на скриншоте.
Для удобства начало пути отмечено стрелочкой, а конечная остановка треугольником.
На скрине видно, что только одна точка осталась неиспользованной (синий цвет).
Мышь двух отцов
Клетки кожи мышиных самцов превратили в яйцеклетки, пригодные для оплодотворения.
Скоро двадцать лет как мы знаем, что любую нашу клетку можно превратить в клетку другого вида, например, клетку кожи в нейрон. Нужно только произвести некоторые молекулярно-биологические операции. В 2006 году Синья Яманака с коллегами показал, как коктейль из четырёх белков возвращает зрелую, специализированную клетку в детство — она утрачивает свои взрослые функции и становится очень похожа на стволовую клетку эмбриона. Такие клетки получили название индуцированных стволовых плюрипотентных клеток — они могут очень, очень долго делиться и их развитие можно направить в любую сторону. (Плюрипотентность как раз и означает, что такая клетка, как настоящая эмбриональная клетка, может превратиться в любую функциональную клетку — мышечную, эпителиальную, нервную и т. д.) Нужно только подобрать верные белковые инструкции: как и с превращением зрелой клетки в индуцированную стволовую, тут всё решают белки, управляющие активностью генов. Только сначала мы обрабатываем зрелую клетку белками, которые включают в ней, грубо говоря, эмбриональные гены, а потом получившуюся стволовую клетку обрабатываем белками, которые дадут ей новую специализацию.
Синья Яманака получил за своё открытие Нобелевскую премию, а число исследований с индуцированными стволовыми клетками с тех пор достигло астрономической величины. Обычно клетки для такого превращения берут из кожи — это проще всего. Что до того, во что их можно превратить, то справедливости ради стоит сказать, что проделать нужное перепрограммирование далеко не всегда легко. Например, как сделать яйцеклетку из клетки кожи самца? Как можно догадаться, проблема тут в хромосомах. У клетки кожи будет, разумеется, самцовый набор половых хромосом: X и Y. Индуцированная стволовая клетка тоже будет с «иксом» и «игреком». Дальше нам нужно получить то, что называется клеткой-предшественницей половых клеток. Такие клетки-предшественницы и у самцов, и у самок делятся особым образом, так что на выходе получаются половые клетки не с двойным (диплоидным), а с одинарным (гаплоидным) набором всех хромосом. У самцов образуются сперматозоиды, несущие либо X, либо Y; у самок — яйцеклетки, несущие только X. Можно попытаться стволовую клетку с самцовым набором половых хромосом направить в сторону самочьей клетки-предшественницы. Однако из-за того, что в ней будут разные половые хромосомы (то есть X и Y, а не X и X), клетка-предшественник не сумеет поделиться «по-самочьи», то есть с образованием полноценной яйцеклетки.
Всё же эту задачу удалось решить сотрудникам Университета Кюсю, Университета Осаки и других научных центров Японии. Они воспользовались тем, что стволовые клетки при делении пусть редко, но всё же иногда теряют одну из половых хромосом. В жизни такие утраты бесследно не проходят и неправильная клетка погибает. Но в лаборатории стволовую клетку, в которой оказалась одна-единственная Х-хромосома, можно поймать, чтобы эту одну-единственную Х-хромосому удвоить. Удвоить хромосому можно с помощью специальных веществ, которые влияют на распределение генетического материала в делящейся клетке. Нужно вмешаться, когда клетка с одним «иксом» захочет поделиться и сделает копию Х-хромосомы, и вмешаться так, чтобы одной дочерней клетке досталось два «икса», а другой ничего. Теперь у нас будет стволовая клетка, которую мы получили от клетки кожи самца, но у которой, тем не менее, обе половые хромосомы женские. И теперь из неё можно спокойно сделать клетку-предшественницу яйцеклетки, а из предшественницы — саму яйцеклетку. А яйцеклетку оплодотворить настоящим сперматозоидом, пересадив эмбрион в суррогатную мать.
Все эти молекулярно-клеточные выкрутасы описаны в вышедшей позавчера статье в Nature. Исследователям удалось получить настоящих живых мышат, которые таким образом родились от двух отцов. Однако из шестисот тридцати эмбрионов мышатами стали только семь, то есть чуть больше 1%. Эффективность процедуры, мягко говоря, не слишком выдающаяся, и не очень понятно, можно ли её увеличить. Впрочем, даже с такой эффективностью вполне можно попытаться восстановить численность некоторых исчезающих животных, от которых остались считанные самцы и самки, категорически не желающие спариваться друг с другом.
Кстати, пять лет назад мы писали о других экспериментах, в которых лабораторные мышата рождались от двух самок или от двух самцов. Хотя подход в том исследовании был немного другой, процент жизнеспособных эмбрионов был также весьма невелик.
Динамическое программирование — базовые понятия
Числа Фибоначчи определяются так: \(F_0 = 0, F_1 = 1, F_n = F_
Эту задачу можно решить рекурсивно:
Однако это будет работать очень долго. 20-е число посчитать еще можно будет, а 40-е число — нет. И не потому, что числа большие. А потому, что мы будем делать слишком много лишней работы. Число операций будет экспоненциально относительно \(N\) .
Почему? Потому что, чтобы посчитать N-е число, нам нужно будет независимо посчитать (N-1)-е число и (N-2)-е число, и это в минимум в два раза больше действий, чем нужно для (N-2). А значит, для подсчета N-го числа Фибоначчи необходимо 2 раза посчитать (N-2)-е число, и это занимает в два раза больше времени, а значит это хотя бы \(2^\frac
Это ну слишком долго, и главное, что это легко исправляется. Давайте просто не считать лишних действий — если мы один раз посчитали \(F_k\) , то давайте запомним, чему оно равно, и в следующий раз, когда оно нам понадобится, мы используем его сразу. Удобнее всего сохранить числа Фибоначчи прямо в массиве:
И этот способ легко работает для больших \(N\) , так как работает за \(O(N)\) — всего один проход по массиву (правда здесь ответ мы будем считать по модулю \(10^9\) , потому что иначе числа получатся слишком слишком большими):
Это и называется динамическим программированием (или динамикой, ДП). Основная идея состоит в том, чтобы * свести задачу для \(N\) к задаче для чисел, меньших, чем \(N\) (с помощью формулы) * хранить все ответы в массиве * заполнить начало массива вручную (для которых формула не работает) * обойти массив и заполнить ответы по формуле * вывести ответ откуда-то из этого массива
Чтобы решить задачу по динамике вы должны ответить на 5 вопросов: * Что лежит в массиве? (самый важный вопрос чаще всего) * Как инициализировать начало массива? * Как обходить массив? (чаще всего слева направо, но не всегда) * Какой формулой считать элементы массива? * Где в массиве лежит ответ?
Одномерная динамика: кузнечик
Рассмотрим такую задачу:
Есть полоска \(1\times N\) , кузнечик стоит на первой клетке, он может прыгать вперед на 1, 2, 3 клетки. Сколько есть способов добраться от начальной клетки до последней?
Как решать такие задачи? Нужно придумать рекуррентную формулу, как ответ для N зависит от ответа для меньших чисел.
Очень помогает посмотреть на маленькие числа (!! одна из самых важных идей для придумывания решений):
Пусть dp[x] — это количество способов добраться от 1 клетки до клетки номер x.
- dp[1] = 1 способ (стоять на месте)
- dp[2] = 1 способ ( \(1 \rightarrow 2\) )
- dp[3] = 2 способа ( \(1 \rightarrow 2 \rightarrow 3\) и \(1 \rightarrow 3\) )
- dp[4] = 4 способа ( \(1 \rightarrow 2 \rightarrow 3 \rightarrow 4\) и \(1 \rightarrow 3 \rightarrow 4\) и \(1 \rightarrow 2 \rightarrow 4\) и \(1 \rightarrow 4\) )
- dp[5] = 7 способов ( \(1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5\) и \(1 \rightarrow 3 \rightarrow 4 \rightarrow 5\) и \(1 \rightarrow 2 \rightarrow 4 \rightarrow 5\) и \(1 \rightarrow 4 \rightarrow 5\) и \(1 \rightarrow 2 \rightarrow 3 \rightarrow 5\) и \(1 \rightarrow 3 \rightarrow 5\) и \(1 \rightarrow 2 \rightarrow 5\) )
Дальше становится сложнее. Но можно заметить закономерность. А можно и не заметить, но зато если мы сейчас придумаем формулу, мы легко проверим, работает ли она. Заодно мы получили наши значения на маленьких числах, которые нам все равно понадобится вбить в программу.
Какой последний прыжок кузнечика в его пути до N-й клетки? Один из трех вариантов: * \((N — 1) \rightarrow N\) * \((N — 2) \rightarrow N\) * \((N — 3) \rightarrow N\)
То есть все пути до \(N\) разбиваются на 3 группы. Причем мы знаем сколько путей в каждой группе. В первой из них ровно dp[N — 1] путей — столько путей идут до (N-1)-й клетки, и дальше идет еще один прыжок. Во второй и третьей группах поэтому тоже dp[N — 2] и dp[N-3] путей.
Так что формула получается такой: dp[N] = dp[N — 3] + dp[N — 2] + dp[N — 1].
Очень похоже на числа Фибоначчи, да? Можете посмотреть на числа, которые мы уже выписали, там все отлично подходит:
dp[4] = 4 = 1 + 1 + 2 = dp[1] + dp[2] + dp[3]
dp[5] = 7 = 1 + 2 + 4 = dp[2] + dp[3] + dp[4].
Так что программа пишется легко:
Давайте изменим немного задачу: Теперь некоторые из клеток закрыты. То есть нам известно про конкретные клетки, что на них кузнечик прыгать не может. Тогда задача все еще решается так же, только нужно убедиться, что dp[x] = 0 для всех запрещенных x!
Также немного перепишем код, чтобы не писать отдельно случаи для 2 и 3, а также чтобы не писать в формуле сумму трех чисел (а представьте, что в задаче не 3, а 100). Будем инициализировать только dp[1]. А ко всем следующим значениям dp[i] будет прибавлять dp[i — k], где k = 1, 2, 3. Причем, если i — k < 1, то мы будем игнорировать такие клетки, и этим самым мы избавились от необходимости прописывать ответ для dp[2] и dp[3].
Двумерная динамика: черепашка
Теперь рассмотрим такую задачу:
На каждой клетке двумерной таблички написано, сколько там лежит монет. Черепашка стоит в клетке 1×1 (верхней левой), и может двигаться только на одну клетку вниз, или на одну клетку вправо. Нужно найти максимальное число монет, которое может набрать черепашка по пути к нижней правой клетке NxM.
Первое, что приходит в голову — это просто идти черепашкой в ту клетку из соседних, где лежит больше монет. К сожалению, эта жадная стратегия не всегда работает. Например, на такой доске жадная черепашка пошла бы по следу из единичек, хотя гораздо выгоднее пойти сначала по нулям, а потом найти там большие горстки монет (40, 70, 100):
Тут нас снова спасает динамика. Давайте сводить задачу к предыдущей! Задачей назовем “сколько максимально монет можно набрать на пути от \(0\times0\) до \(i\times j\) ” (заменим 1-нумерацию на 0-нумерацию). Будем хранить это в двумерном массиве dp в клетке dp[i][j].
Сразу понятны некоторые свойства этого массива: * Он размера NxM * dp[0][0] = COINS[0][0] * ответ на всю задачу лежит в dp[N — 1][M — 1]
Но гораздо важнее придумать формулу для подсчета dp[i][j] через предыдущие. Легко посчитать первую строку и первый столбец: * dp[0][k] = dp[0][k — 1] + COINS[0][k] * dp[k][0] = dp[k — 1][0] + COINS[k][0]
Так как до этих клеток есть ровно один путь.
Но что делать, если есть много путей до клетки dp[i][j]? Снова разобьем их на на несколько групп в зависимости от последнего хода (! важный трюк, запомните). Последний ход был: * либо из [i][j — 1] * либо из [i — 1][j]
Поэтому формула для максимального числа монет такая: dp[i][j] = max(dp[i — 1][j], dp[i][j — 1]) + COINS[i][j].
Ну все, достаточно пройтись правильно по двумерному массиву (построчно сверху вних, а в каждой строке слева направо) и заполнить этот массив.
В отличие от жадного алгоритма, динамическое программирование находит оптимальное решение — это, в данном случае, 113 монет.
Восстановление ответа
В последней задаче было здорово найти, что в оптимальном пути черепашки набирается 113 монет, но интересно, что именно это за путь. Такую задачу называют восстановлением ответа в динамике.
Есть два способа, которыми можно это сделать.
- Хранить в массив prev откуда ты пришел в эту клетку.
Когда мы выбираем максимум из левой и верхней клетки, мы на самом деле решаем, какой последний ход будет в оптимальном пути до этой клетки — сверху или слева, и берем ответ для той клетки, сложнный с монетами в этой клетке. Давайте координаты клетки, откуда мы пришли, хранить в массиве prev. Или, в данном случае, можно хранить не координаты а просто 1, если пришли слева, и 0, если пришли сверху.
И, чтобы восстановить ответ, надо просто пройтись с конца по этим клеткам до самого начала, и развернуть получившуюся последовательность.
- Вместо хранения массива prev догадаться по массиву dp, откуда именно черепашка пришла в эту клетку.
В данном примере это довольно легко. Если мы уже посчитали весь массив dp, то теперь можно начиная с конца легко понять, пришла черепашка туда сверху или слева в оптимальном маршруте — она пришла из клетки с максимальным числом монет.
Задание
Решите как можно больше задач из простого контеста:
А также решите как можно больше задач из сложного контеста:
Разбор еще нескольких задач
Давайте разберем еще несколько задач.
Последовательности без 3 единиц подряд
Условие:
Определите количество последовательностей из нулей и единиц длины \(N\) , в которых никакие три единицы не стоят рядом.
Решение:
Давайте хранить в \(dp[N]\) ровно число таких последовательностей длины \(N\) (это первое, что должно приходить в голову).
Давайте посмотрим для начала для маленьких чисел:
- \(dp[0] = 1 (\text<пустая последовательность>)\)
- \(dp[1] = 2 (0, 1)\)
- \(dp[2] = 4 (00, 01, 10, 11)\)
- \(dp[3] = 7 (000, 001, 010, 011, 100, 101, 110)\)
- \(dp[4] = 13 (0000, 0001, 0010, 0011, 0100, 0101, 0110, 1000, 1001, 1010, 1011, 1100, 1101)\)
Сходу закономерность можно не увидеть. Нужно догадаться сгруппировать эти числа по том, сколько в конце единичек. Например, для dp[4]:
- 0 единичек в конце: \(0000, 0010, 0100, 0110, 1000, 1010, 1100\) — их ровно семь, как для \(N=3\) , потому что первые 3 числа могут быть любые (но без трех единиц подряд), а четвертое — 0
- 1 единичка в конце: \(0001, 0101, 1001, 1101\) — их ровно четыре, как для \(N=2\) , потому что первые 2 числа могут быть любые (но без 3 единиц подряд), а два последних — 01
- 2 единички в конце: \(0011, 1011\) — их ровно две, как для \(N=1\) , потому что первое число может быть любым (но без 3 единиц подряд), а три последних — 011
Так мы замечаем и доказываем формулу: \(dp[N] = dp[N-1] + dp[N-2] + dp[N-3]\)
Теперь за \(O(N)\) ее легко посчитать.
Лесенки
Условие:
Лесенкой называется набор кубиков, в котором каждый горизонтальный слой содержит меньше кубиков, чем слой под ним. Подсчитать количество различных лесенок, которые могут быть построены из N кубиков.
Решение:
Если считать, что \(dp[N]\) — это число лесенок из \(N\) кубиков, то никакой закономерности скорее всего найти не получится.
- \(dp[1] = 1\)
- \(dp[2] = 1\)
- \(dp[3] = 2\)
- \(dp[4] = 2\)
- \(dp[5] = 3\)
- \(dp[6] = 4\)
По числам построить закономерность сложно, и по самим лесенкам тоже. Не видно какого-то рассуждения вида “ко всем лесенкам размера N-1 можно положить на любой слой еще один кубик”, иногда ведь и нельзя.
Тут нам помогает введение дополнительного параметра. Нас просят решить одномерную задачу (для \(N\) ), а мы решим двумерную задачу для \(n\) и \(m\) . Давайте зафиксируем размер самого нижнего слоя и назовем его размер \(m\) .
То есть $dp[n][m] = $“число лесенок, состоящих из \(N\) кубиков, таких, что самый нижний слой состоит из \(M\) кубиков”.
Как это связано с нашей задачей? Ответ на нашу задачу равен \(dp[N][1] + dp[N][2] + \ldots + dp[N][N]\) .
Какая есть формула для такой постановки задачи? Размер нижнего слоя у нас зафиксирован и равен \(m\) , осталость \(n-m\) кубиков на верхних слоях. Логично перебрать размер второго снизу слоя, который может быть любым от \(1\) до \(m-1\) : \(dp[n][m] = dp[n-m][1] + dp[n-m][2] + \ldots + dp[n-m][m-1]\)
Это все пир условии, что \(n \geq m\) . Иначе \(dp[n][m] = 0\) .
Теперь осталось понять как инициализировать этот массив и аккуратно по нему пройтись. Давайте инициализируем его ровно для случая \(n=0, m=0\) :
Пройдемся по массиву сначала для всех m при n = 1, потому для всех m при всех n = 2 и так далее — то есть по строчкам обычными двумя циклами \(for\) .
Для \(m > 0\) в ячейках \(dp[0][m]\) наш алгоритм будет работать и возвращать 0, так как \(n < m\) .
Для всех \(n > 0\) наша формула будет находить ответ через числа с меньшим n, а значит алгоритм корректен.
Он заполняет табличку размера \(N^2\) , обрабатывая каждую клетку за \(O(N)\) операций, итоговое время работы — \(O(N^3)\) .
Миролюбивые шахматные кони
Клетки доски 5×5 раскрашены в шахматном порядке (рис. 1). а) Какое наибольшее число шахматных коней можно расставить на этой доске так, чтобы они не били друг друга? б) Сколькими способами это можно сделать?
Подсказка
Кони, стоящие на одной диагонали, друг друга не бьют.
В пункте б) ответ — один способ. Но это надо доказать.
Решение
Расстановка 13 коней показана слева на рис. 2. Докажем, что большее число не бьющих друг друга коней расставить на такой доске нельзя. Для этого мысленно разобьем клетки на пары так, чтобы в каждую пару входили клетки, отстоящие друг от друга на один ход коня. Одной клетке, естественно, пары не найдется. В том, что такое разбиение существует, можно убедиться, посмотрев на правую часть рис. 2.
Очевидно, что, как ни расставляй коней на доске, в каждой паре можно будет занять не больше одной клетки. Это означает, что коней заведомо не больше, чем количество пар, которых 12, плюс один (одна непарная клетка) — то есть 13.
Чтобы показать, что расстановка 13 коней на этой доске всего одна, идею с разбиением клеток на пары удобно несколько модифицировать.
Рассмотрим граф, вершинами которого будут центры клеток доски. Две вершины соединим ребром, если из одной в другую можно попасть за один ход коня. Этот граф показан слева на рис. 3. Важно, что в этом графе есть последовательность ребер, которая проходит через каждую из 25 вершин ровно по одному разу (рис. 3, справа).
На языке теории графов последовательности вершин, соединенных по цепочке ребрами, называют путями. Ясно, что из любых двух клеток, которые встречаются подряд на нашем пути, конь может стоять только в одной. Поэтому для того, чтобы «уместить» максимальное число коней, начинать надо прямо с первой клетки этого пути. Это и даст расстановку, показанную на рис. 2.
Послесловие
Рис. 4. Уильям Гамильтон, фотопортрет середины XIX века. Изображение из твиттера библиотеки Дублинского университета
Путь в графе, который помог нам решить задачу, проходил через все вершины графа по одному разу. Такие пути называются гамильтоновыми. Если в графе есть замкнутый гамильтонов путь (у которого совпадают начало и конец, путь в таком случае является циклом), то сам граф называется гамильтоновым. Название дано в честь ирландского математика Уильяма Гамильтона (1805–1865), которого по праву называют одним из величайших математиков XIX столетия: он оставил значительный вклад в разных областях математики (про некоторые важнейшие разделы вообще можно сказать, что они впоследствии выросли из его работ), механики и оптики.
Известно, что по мотивам своих исследований Гамильтон даже придумал игру-головоломку «Икосиан» (осторожно: перейдя по этой ссылке вы увидите решение головоломки!), которая одно время продавалась и была довольно популярной. Цель игры — построить гамильтонов цикл (то есть пройти по всем вершинам, каждый раз переходя в соседнюю по ребру, и вернуться в начало пути) в правильном додекаэдре (рис. 5, слева). Поскольку изготавливать такой правильный многогранник, а затем распространять его и, главное, играть с ним не очень удобно, игра представляла собой плоскую доску с выемками для фишек, соединенными линиями, соответствовавшими ребрам додекаэдра (рис. 5, справа). Фишек было 20 (столько же, сколько вершин у додекаэдра), они были пронумерованы, чтобы их можно было расставлять в порядке обхода.
Рис. 5. Слева: додекаэдр — один из пяти правильных многогранников; у него 12 граней, являющихся одинаковыми правильными пятиугольниками, 30 ребер и 20 вершин. Рисунок с сайта ru.wikipedia.org. Справа: оригинальный экземпляр игры «Икосиан». Любопытно, что игра названа «в честь» икосаэдра, а обходить в ней надо додекаэдр. Связано это с тем, что эти два многогранника двойственны друг другу Фото с сайта researchgate.net
В задаче о гамильтоновом пути требуется выяснить, есть ли в данном графе гамильтонов путь (или цикл), и, в случае положительного ответа, найти его явно. Эта задача — важная и неожиданно сложная с точки зрения сложности вычислений: в известных алгоритмах с ростом числа вершин в графе количество требуемых операций растет экспоненциально. Из-за этого такие алгоритмы на практике неэффективны: фактически для произвольного графа с сотней-другой вершин уже невозможно получить ответ на этот вопрос даже на самом мощном суперкомпьютере. По сути, эти алгоритмы — хоть и оптимизированный, но перебор всех возможных путей.
При этом, если кто-нибудь предоставит вам сколь угодно большой и сложный граф, а также путь в нем, то проверить, является ли этот конкретный путь гамильтоновым, вы сможете довольно просто. Это (вместе с тем, что пока неизвестен быстрый алгоритм решения) означает, что с точки зрения теории алгоритмов задача о гамильтоновом пути попадает в класс сложности NP. Более того, она является NP-полной задачей: к ней относительно просто — за полиномиальное время — можно свести любую другую задачу из этого класса. Раз уж зашла речь об классах сложности, то нельзя не упомянуть одну из так называемых задач тысячелетия — проблему равенства классов P и NP. К классу P относятся задачи, для которых известны алгоритмы, в которых количество операций растет как какой-то определенный многочлен от размера входных данных. Даже если степень многочлена большая, с точки зрения теории алгоритмов такая задача считается простой. Если придумать полиномиальный алгоритм для любой NP-полной задачи (в том числе и для поиска гамильтонова пути), то эта проблема автоматически будет решена.
При этом с «теоретической» точки зрения про гамильтоновы пути известно, грубо говоря, всё, поскольку теорема Бонди — Хватала (Bondy–Chvátal theorem) дает критерий того, что граф является гамильтоновым: для этого необходимо и достаточно, чтобы замыкание этого графа тоже было гамильтоновым графом. Замыкание графа G с n вершинами — это граф, который строится последовательным «пририсовыванием» ребер, соединяющих любую пару вершин, удовлетворяющую следующим двум свойствам: во-первых, эти вершины должны быть еще не соединены ребром, а во-вторых, сумма их степеней должна быть больше n. Проблема с этой теоремой в том, что она не помогает в алгоритмическом поиске гамильтонова цикла. И даже просто для ответа на вопрос о том, есть ли в графе такой цикл, она плохо годится, поскольку сводит проверку одного графа к проверке другого, в котором к тому же больше ребер. Исключение — те случаи, когда замыкание графа оказывается «хорошим»: про него относительно легко понять, что он гамильтонов. Пример «хорошего» в этом смысле графа — полный граф, в котором любые две вершины соединены ребрами (при \(n>2\) он точно гамильтонов).
Рис. 6. Леонард Эйлер. Портрет, выполненный Я. Э. Хандманном (1756 год). Рисунок с сайта ru.wikipedia.org
Кстати, с другим важным типом путей в графах — эйлеровыми путями, которые проходят по одному разу по всем ребрам, — все гораздо проще. Во-первых, есть простой критерий эйлеровости графа: связный граф эйлеров (то есть в нем есть эйлеров цикл) тогда и только тогда, когда в нем нет вершин нечетной степени. Во-вторых, есть алгоритмы, которые ищут такие пути за линейное время от размера графа (количества ребер). Понятие эйлерова пути появилось, когда Леонард Эйлер размышлял над задачей о семи кёнигсбергских мостах (это было в районе 1736 года).
Охватить весь спектр приложений эйлеровых и гамильтоновых графов в рамках нашей статьи невозможно, но можно посоветовать заинтересовавшимся читателям ознакомиться, например, со статьей Ф. Компо и П. Певзнера «Реконструкция генома: головоломка из миллиарда кусочков» («Квант», №3 за 2014 год). В ней подробно описано, какие математические идеи лежат в основе методов секвенирования ДНК и, в том числе, какую роль играют в этом эйлеровы и гамильтоновы графы.
Вернемся к приключениям шахматного коня на доске. Вспомним, что в решении задачи мы рассмотрели «коневой» граф шахматной доски 5×5 (он нарисован слева на рис. 3) и нашли в нем гамильтонов путь. По сути, этот путь показывает, как можно шахматным конем обойти всю доску, побывав в каждой клетке ровно один раз. Оказывается, этот вопрос — можно ли обойти конем данную доску (не обязательно квадратную)? — известен не одну сотню лет. Распространенное название — задача о ходе коня (Knight’s tour).
Легко видеть (на примере нашей задачи), что это частный случай поиска гамильтонова пути. Благодаря специфике «коневого» графа он решается относительно просто. Одно из первых исследований этого вопроса, кстати, выполнил Эйлер: в статье Solution d’une question curieuse qui ne paroît soumise à aucune analyse (1759 год) он предложил способ строить нужные обходы коня для доски 8×8.
С тех пор, разумеется, этот вопрос изучен вдоль и поперек. Например, известно, что всего для обычной шахматной доски существует 13 267 364 410 532 замкнутых обходов. Придуманы разные алгоритмы построения нужного пути. Самый, пожалуй, простой формулируется буквально одной фразой: нужно начать из любой клетки и каждым ходом ходить в ту клетку, с которой потом можно попасть на минимальное число еще не пройденных клеток (если таких клеток несколько, то можно выбрать любую). Этот способ называется правилом Варнсдорфа, он был предложен еще в XIX веке. Уточнение, написанное в скобках, делать приходится, потому что описанные в нем ситуации вполне вероятны и нужно хоть как-то выбирать из равнозначных вариантов. При внимательном исследовании этого способа (уже при помощи компьютеров) оказалось, что иногда совсем произвольный выбор следующей клетки для хода коня может впоследствии завести его в тупик. Однако это происходит довольно редко. Подробнее об этом рассказано в книге Е. Гика «Шахматы и математика».
Наконец, приведем еще пару задач, в которых рассмотренные выше идеи помогают найти решение без перебора.
1. Можно ли выписать целые числа от 0 до 9 в таком порядке, чтобы сумма любых двух соседних чисел делилась либо на 5, либо на 12? (Использовать каждое число можно только один раз.)
Идея решения
Построим граф, в котором вершины соответствуют данным числам. Соединим две вершины ребром, если сумма соответствующих чисел делится либо на 5, либо 12. После этого остается найти в таком графе гамильтонов путь.
2. Мышь грызет кусок сыра в форме куба 3×3×3, разбитый на единичные кубики. Когда она съедает один кубик целиком, то приступает к соседнему по грани кубику. Может ли она таким образом съесть всё, кроме центрального кубика?
Идея решения
Идея в том, чтобы раскрасить единичные кубики в шахматном порядке. Тогда в любом «пути» мышки по кубикам их цвета будут чередоваться. Значит, число «белых» кубиков не может отличаться от числа «черных» больше чем на 1.
3. Картинная галерея имеет форму правильного треугольника, который разбит на 36 одинаковых треугольных залов (залы — тоже правильные треугольники). Между любыми двумя соседними залами есть дверь. Какое наибольшее число залов может обойти, если не заходить в один и тот же зал дважды?
Подробный разбор этих задач, другие примеры и более строгое обсуждение их математической сути можно найти в статье П. Кожевникова «Длинные пути в графах» («Квант», №1 за 2018 год).