Карты метро и нейронные сети. Теория графов
Шрифт:
Эта задача имеет решение; более того, оно не является единственным. Эту головоломку, как и многие другие шахматные задачи, можно решить с помощью теории графов. Каждая клетка доски соответствует вершине графа, ход коня — ребру, соединяющему две вершины графа. Следовательно, задача сводится к нахождению гамильтонова цикла в этом графе.
Маршрут коня по шахматной доске.
Математики не стали ограничиваться стандартной доской размером 8 x 8 клеток и рассмотрели возможность обхода досок размерами 5 x 5, 6 x 6, 3 x 10 клеток и других. Эти задачи представляют собой задачи на поиск гамильтоновых цепей в графах, число вершин которых равняется n x m. Например, для доски 6 x 6 клеток
Интересной читателю будет и задача о поиске маршрута шахматной ладьи из одного угла доски в диагонально противоположный, проходящего через все клетки. Можно рассмотреть доску размерами 7 x 7 клеток или общий случай — n x n клеток.
Простая игра в шахматы может подарить вам огромное множество интересных задач.
Льюис Кэрролл и эйлеровы графы
Чарльз Лютвидж Доджсон (1832–1898), известный под псевдонимом Льюис Кэрролл, был не только автором «Алисы в стране чудес», но и любителем занимательных математических задач. Он любил придумывать остроумные головоломки, которые мог решить даже ребенок. Некоторые из его задач сегодня изучаются в теории графов, хотя в его эпоху к теории графов относили лишь задачи, где нужно было нарисовать заданную фигуру, не отрывая карандаша от бумаги. Самой известной из подобных задач Кэрролла является задача о трех квадратах, показанных на рисунке. Сможете ли вы обойти этот граф, не отрывая карандаша от бумаги и не проводя ни одну линию дважды?
Томас О’Бейрн придумал удивительный метод решения подобных задач, который заключается в том, что нужно раскрасить смежные области чередующимися цветами (см. рисунок) и тем самым «разделить» области, чтобы найти искомый путь. Маршрут обхода становится очевидным, и можно легко провести карандашом нужный путь на исходном графе.
Задача о четырех окружностях
Спустя много лет после Кэрролла О’Бейрн придумал похожую задачу, заменив три квадрата четырьмя пересекающимися окружностями, которые образуют красивую симметричную фигуру.
Читателю предлагается найти способ обхода всех дуг четырех окружностей, пройдя по каждой ровно один раз. Очевидно, что раскраска окружностей по описанному выше алгоритму поможет вам решить эту задачу. Если вам не удалось найти решение, загляните в конец этой главы, где приводится ответ к задаче (стр. 122).
Магические звезды
Магические звезды — удивительная игра из области занимательной комбинаторики, в которой смешались графы и числа.
На рисунке изображена пятиугольная звезда — символ школы пифагорейцев. Десять ее вершин обозначены кругами. Можно ли расположить в вершинах звезды числа от 1 до 10 так, чтобы сумма чисел во всех рядах из четырех вершин была одинаковой? Эта сумма чисел называется магической константой. Попробуйте решить задачу, прежде чем продолжить чтение. Чему равна магическая константа для пятиугольной звезды?
Не получается? Не беспокойтесь. Вам не удается найти решение, потому что его не существует. Обратите внимание, что сумма чисел от 1 до 10 равна 55. Так как каждое число находится в двух линиях звезды, общая сумма чисел на всех линиях будет в два раза больше, чем 55, то есть 110. Следовательно, магическая константа должна равняться 110/5, то есть 22. Остается распределить числа так, чтобы их сумма в каждом ряду равнялась 22.
Иан Ричардс заметил: каждая из линий, в одной из вершин которой находится число 1, должна содержать, помимо единицы, еще три числа, которые в сумме дают 21. Следовательно, сумма чисел на двух этих линиях равна 42, поэтому 10 должно находиться в одном ряду с 1 (шесть чисел, среди которых нет 10, в сумме могут давать максимум 4 + 5 + 6 + 7 + 8 + 9 = 39). Пусть А — линия, на которой находятся 1 и 10, В — другая линия с вершиной 1, С — другая линия с вершиной 10. Тогда числа на линии А можно расположить четырьмя возможными способами. Если на одной из линий будут располагаться 1, 10, 4, 7, то поместить числа на В и С будет невозможно. Следовательно, остаются три случая:
Магическая гексаграмма
Рассмотрим магическую гексаграмму. Гексаграмма — это знаменитая и легендарная Звезда Давида и Печать Соломона, образуемая наложением двух равносторонних треугольников друг на друга.
Как видно на рисунке, эта фигура имеет 12 вершин, расположенных в шесть рядов по четыре вершины, поэтому в этой задаче нужно присвоить вершинам числа от 1 до 12. Так как сумма чисел от 1 до 12 равна 78, магическая константа будет равна 78·2/6, то есть 26. Сосредоточьтесь, приготовьте карандаш и найдите одно из нескольких десятков решений этой задачи. В конце главы (стр. 122) приведено одно из возможных решений.
Если вам понравилось решать задачи с магическими звездами, попробуйте найти одно из множества возможных решений для семиконечной или восьмиконечной звезды.
Более простой альтернативой этой задаче, для которой существует строгий алгоритм решения, являются магические окружности — несколько окружностей, в точках пересечения которых нужно расположить числа так, чтобы сумма чисел на каждой окружности была одинаковой, например 20. На следующем рисунке изображены три окружности, точки пересечения которых обозначены буквами а, b, с, d, р, q. Можно записать соотношения, которые должны выполняться для чисел, соответствующих этим вершинам.
Получим систему уравнений:
a + b + c + d = 20,
с + d + р + q = 20,
а + Ь + р + q = 20.
Сложив все три уравнения, получим:
2а + 2Ь + 2с + 2d + 2р + 2q = 60,
или, что аналогично,
a + b + c + d + q = 30.
Вычтем из последнего равенства все три исходных равенства и получим:
a + b = c + d = p + q = 10.
Следовательно, существует множество различных вариантов, например:
а = 1, Ь = 9, с = 2, d = 8, р = 3, q = 7.