Мыслим #6 Задачи на основе теории графов

Закон Микша
Если у верёвки есть один конец, значит, у неё должен быть и другой.

Теория графов и связанные с ними алгоритмы - богатейшая тема для развития нестандартного мышления и обнаружения аналогий.

Снарк. Так именуют это граф с внутренним кодом J5

Только вот требует уже имеющихся знаний, поэтому не годится для начинающих. Из-за этого пришлось ограничиться очень небольшим набором задач. Буду крайне благодарен если предложите что-то простое и наглядное.

Инерция мышления 1

Известный архитектор любил возиться с детьми, придумывая им задачки на основе реальных примеров. Вот какой вопрос он задал детям: «Можете ли вы пройти через каждую дверь на этом плане только по одному разу, не повторяя собственный маршрут? Вы можете начинать путь в любой комнате и выходить из здания».

План комнат и проходов между ними

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

На самом деле эту задачу можно попробовать решить, преобразовав план здания в граф, в котором роль вершин играют комнаты, а двери — рёбра графа соединяющие соответствующе вершины (например, как на рисунке внизу).

Граф, соответствующий верхнему плану

Тем самым исходная задача переходит в одну из задач об обходе графа, при котором по каждому ребру можно пройти только один раз. Такой путь называют Эйлеровым, а если потребовать совпадение исходной и конечной точки — то Эйлеровым циклом. Эта задача была решена Леонардом Эйлеров ещё в 1736 г. Если назвать степенью вершины количество присоединённых к ней рёбер (число после дефиса на рисунке справа) то для существования такого обхода в графе не должно быть более двух вершин нечётной степени. Для нашего графа это условие соблюдается. Причём вершина(ы) с нечётной степенью будут началом/концом нашего пути. В условиях задачи это комнаты, которые мы пронумеровали как первую и вторую.

Решение в "классическом" виде

Инерция мышления 2

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

Cхема коридоров

Превратим схему коридоров в граф, заменив каждый коридор двумя рёбрами (см. рисунок).

"Прочтение" схемы в виде графа

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

Инерция мышления 3

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

Если абстрагироваться от геометрических форм, то изображение представляет собой набор вершин и рёбер, не более! А задача «прочертить» линию только по одному разу, без возвратов — обычное построение эйлерова пути.

Решение задачи

Если теперь посчитать степени смежности для всех вершин, то только два внизу будут иметь нечётную степень, фактически определяя собой начальную или конечную точки обхода, например как показано на рисунке слева.

Портим сетку

Какое наибольшее количество разрезов можно сделать в волейбольной сетке (5×10) так, чтобы она не распалась?

Волейбольную сетку естественным образом можно представить как связный граф, который имеет 11 * 6 = 66 вершин и 10 * 6 + 11 * 5 = 115 рёбер. Легко видеть, что удаление любого ребра связного графа, принадлежащего какому-нибудь циклу, не делает граф несвязным. Поэтому нам нужно удалять ребра из циклов до тех пор, пока циклы будут, т.е. пока не получится дерево. Так как в дереве любые две вершины соединены единственной цепью, то удаление любого ребра дерева делает граф несвязным. Поэтому удалять ребра дерева нельзя. Дерево с 66 вершинами имеет 65 ребер. Поэтому из графа можно удалить 115 - 65 = 50 рёбер.

Обратим внимание, что задача не говорит какие «верёвки» можно разрезать, а какие нет. Речь идёт о максимальном количестве «разрезов».

Знакомые туристов

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

Построим граф знакомств. Если утверждение Петра верно, то каждая из пятнадцати вершин графа имеет соединена в точности с 5-ю рёбрами. В произведении 15 * 5 = 75 общего количества рёбер в графе каждое ребро учитывается дважды, так как оно соединяет две вершины (знакомства в условиях задачи считаются взаимными). Поэтому в графе должно быть чётное количество рёбер, а не нечётное. То есть утверждение Петра неверно.

Тем не менее рассказанное Петром возможно, если воспринимать отношения как сугубо направленные в стиле «слышал о таком-то». Тогда граф становится ориентированным, и названые пять человек определяют количество связей исходящих из каждой вершины. Количество входящих может быть произвольным, даже нулём для «полного новичка» или 14-ю для кого-то типа руководителя группы.