что такое графы и как их понимать

Теория Графов. Часть 1 Введение и классификация графов

«Графы являются одним из объединяющих понятий информатики – абстрактное представление, которое описывает организацию транспортных систем, взаимодействие между людьми и телекоммуникационные сети. То, что с помощью одного формального представления можно смоделировать так много различных структур, является источником огромной силы для образованного программиста». Стивен С. Скиена

Введение

Сначала под землей города Москвы ничего не было. Потом была построена первая станция метро, а затем и вторая и третья. Образовалось множество станций метро. На карту было занесено множество точек. Позже между станциями стали прокладывать пути линии. И соединилась станция метро А со станцией метро Б. Все остальные станции также стали соединятся друг с другом и на карте появилось множество линий. В итоге мы имеем Московский метрополитен очень красивый, я там был проверял.

Схема Московского метро

Посмотрите какая красота. У нас имеется множество точек (которые называются вершинами или узлами), а также множество линий (называемые рёбрами или дугами). Обозначим множество вершин буквой V от английского vertex−вершина и множество рёбер обозначим E от английского edge−ребро. Граф в формулах именуют буквой G. Все вершины обязательно должны быть идентифицированы.

Отмечу, что число вершин обозначается буквой n:

Число рёбер обозначается буквой m:

Таким образом граф задается и обозначается парой V,E:

Также определение графа рассказывается в этой статье на Хабре (https://habr.com/ru/post/65367/)

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

Разберем определение графа подробней. Может ли в G быть пустым множество E? Да без проблем! Такой граф будет называться нулевым, а вершины в нем будут называться изолированными.

Нулевой граф

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

Множество E задается парой неупорядоченных вершин множества V.

Пример: Пусть множество V = <1,2,3,4,5>. Тогда множество E =

Граф будет выглядеть следующим образом:

Висячей вершиной называется вершина которая соединена только с одной соседней вершиной. В нашем случаи висячей вершиной будет вершина 5, так как она соединена только с вершиной 1.

Степень записывают, как:

Максимальная степень, то есть какое количество степеней вообще присутствуют в графе обозначаются, как:

Формула суммы степеней для G = V,E выглядит так:

То есть сумма степеней всех вершин v графа равна удвоенному количеству его рёбер E. Считаем количество степеней в нашем примере. От этого никуда не денешься. Я насчитал 12. А теперь считаем, сколько у нас рёбер. Их 6! Умножаем на 2 и получаем 12. Совпадение? Не думаю!

А давайте представим наш граф в другом виде, но с сохранением данных пар. G теперь имеет следующий вид:

Заметьте я не изменил пары между собой. Вершина 4 также соединяется с вершиной 3, а у вершины 1 степень также осталась 4. Так почему граф имеет совершенно другой вид и законно ли это?

Классификации графов

Первым признаком классификации является отсутствие или наличие ориентации у ребер.

Ребро является неориентированным если у него нет понятия начала или конца. То есть оба его конца равноправны. Такой граф называется неориентированным, обыкновенным или неографом.

Неориентированный граф

Ориентированное ребро обозначается стрелкой. И указывает ориентацию от вершины к вершине. То есть данный граф имеет начало и конец. И называется он ориентированным или орграфом.

Ориентированный граф

Также существует граф со смешанными ребрами. Это когда в графе присутствуют, как ориентированные рёбра, так и неориентированные.

Смешанный граф

Вторым признаком является отсутствие или наличие кратных ребер.

Мультиграф

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

Заключение

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

Источник

Зачем студентам теория графов

Ранее я уже писал про приложения теории графов: тут и тут.

В этой статье хочу помочь коллеге в теории графов – он пожаловался в комментарии к своей статье, что:

Здесь я попытался в максимально доступной форме объяснить, как же это делать. И в первую очередь я делаю это для студентов, которые изучают данную тему и могут не понимать, зачем вообще графы нужны. Учась, я лично убедился, что для многих эта тема была «проходной» и они не извлекли из нее никакой ценной информации, а также так и не поняли, как работать с матрицами.

ИМХО для IT-студентов нужно сразу сказать, что списки (стеки, очереди) и бинарные деревья это графы. И всякие схемы, типа схемы метро, автодорог, принципиальные в электронике можно рассматривать как графы. Приложения теории графов — это фундаментальные свойства всяких подобных схем.

Для студентов историков м.б. будет полезно узнать, что фамильные деревья — это графы. И проч. др. специальности. Где только нет графов, пусть на уровне тривиального списка. Возвращаясь к IT: строка символов — граф, и число — последовательность байт — граф, и файл — граф, не говоря о БД.

Дисклеймер. Далее хочу высказать свое сугубо личное мнение, никого ни в чем, не пытаясь убедить или переубедить. Исключительно в порядке обсуждения. Т.о. я адресуюсь к читателям, уже знакомым с теорией графов. Нижеследующее — всего лишь мои предположения. Иногда я опираюсь на факты и на авторитеты (Харари, Зыков, Вирт, Адельсон –Вельский и, как ни странно, А. Дюма), но это не повод тотально засадить всех студентов за зубрежку теории графов в полном объеме.

Вернемся к историкам. Предположим, что ими собрано достаточно документов о том, что у Хуана и Хуаниты, после того, как они сочетались законным браком, было пять детей. Но Хуанита изменяла Хуану и двоих родила внебрачно. А Хуан не остался в долгу и трижды изменил Хуаните – еще двое детей. Однако вопрос: от кого из любовников родила Хуанита?: От Филиппа или от кардинала Ришелье? А может от кого-то из четырех мушкетеров – он была общительной женщиной. Такой вопрос и про Хуана: он был знаком и пользовался расположением королевы Франции, но уделял внимание и ее дамам. (А. Дюма на многих сотнях страниц описывает подобные истории).

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

Где черные ребра – документально подтвержденные факты, а красные – предположения.
А можно так:

Где красные ребра имеют надпись: «+любовница 1 или + любовница 2 или + любовница 3», т.е. предположения.
Синие и зеленые ребра имеют надпись: «+Хуанита», но синие — документально подтвержденные факты, а зеленые – предположения.

Путь — это результат обхода некоторых вершин графа по правилу: переходить можно только на вершну инцидентную (т.е. связанную ребром) текущей вершине. При этом нельзя возвращаться по уже пройденному ребру.

Цикл – это путь начало, которого и конец, которого в одной и той же вершине.

Это цикл:

И это цикл:

Дерево – это граф без циклов.
Пример:

Линейный список – дерево без ветвей. Т.е. только предыдущий элемент списка всегда инцидентен следующему и никакой другой.

Здесь буквы и пробел – вершины графа, а дефис “-” обозначает ребро.

Г.М. Адельсон-Вельский доказал, что время поиска по дереву зависит от высоты этого дерева. (Н.Вирт в своей знаменитой книге “Алгоритмы + структуры данных = программы” ссылается на эту работу.) Из доказательства Адельсона-Вельского следует, что наихудший случай для дерева – вырождение в линейный список, и, следовательно, превращение списка в достаточно развесистое дерево ускорит поиск.

Для иллюстрации возьмем рекурсивное определение Вирта бинарного дерева.

Рекурсивная процедура сортировки будет такая:

Функция поиска в дереве:

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

Для гуманитариев может и не нужно вникать в приведенный код. Им важно понять, что список:

Аня
Ваня
Иван Васильевич
и т.д.

не всегда оптимальное решение. Не смогут сами — попросят помочь.

Я (с коллегами) продемонстрировал быстрый поиск при размерности ок.100 лимонов химических соединений (не все реально полученные – некоторые гипотетические). Тут мы встречаемся с важной задачей теории графов – задачей установления изоморфизма двух графов.

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

Пример не похожих рисунков:

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

И этот кунеан на другом рисунке:

Математически в общем случае задача изоморфизма сводится к поиску матрицы перестановки такой, чтобы
A₁= TA₂P,
где A₁ – матрица смежности первого графа;
A₂ – матрица смежности второго графа;
P — матрица перестановки;
T – обратная ( = транспонированная, для данного случая) матрица перестановки.

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

Нужно отметить, что для некоторых типов графов задача изоморфизма решается тривиально, для других легко, но для многих требует перебора со сложностью в экспоненту. Тривиально для полных графов – это графы, у которых каждая вершина связана со всеми остальными (инцидентна всем остальным). Понятно, что для любых n вершин существует только один полный граф. Поэтому проверка на изоморфизм сводится к проверке равенства числа вершин первого графа = числу вершин второго. Аналогично для безреберного графа (где только вершины).

Легко задача изоморфизма решается для случая, когда у всех вершин разные степени. Т.к. степени уникальны, то вычисление матрицы перестановки не требуется – простая перенумерация. Каждому номеру вершины второго графа присваиваете номер вершины первого той же степени и проверяете совпадение ребер.

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

Полные инварианты это, которые, если равны, то графы изоморфны, а если не равны, то не изоморфны. Один из полных инвариантов описан у Зыкова. Матрицу смежности можно развернуть в вектор – нужно просто добавлять в вектор строку за строкой из матрицы. Этот вектор можно рассмотреть, как двоичное число. Можно перебрав все матрицы найти минимальное и максимальное числа. Далее если такие минимальные (или максимальные) числа для двух графов совпадают, то, очевидно, что их матрицы смежности после перестановки будут равны и графы будут изоморфны. К настоящему времени не известен ни один полный инвариант, который можно вычислить без перебора.

Отметим, что изоморфизм деревьев определяется (без полного перебора) с полиномиальной сложностью. А проблема изоморфизма графов остается по-прежнему открытой.

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

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

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

Источник

Просто о графах. Попытка популяризации

«Всякие звания (дворянина, купца, мещанина, крестьянина и пр., титулы — княжеские, графские и пр.) и наименование гражданских чинов (тайные, статские и проч. советники) уничтожаются. »

Как-то же я обходился без этого раньше.

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

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

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

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

Граф может оказаться выразителем сущности некоторой идеи и сократить вашу дорогу к конечной цели (если вы сейчас подумали о грустном, то я не имел это ввиду).
Часто бывает, что мы пользуемся не осознано, интуитивно, некоторыми приемами решения возникающих перед нами задач, которые – суть пользовательские шаблоны, подсказанные предыдущим опытом, а между тем, эти приемы, отлитые в идею, возведенные в парадигму, обращенные в концепцию могут стать мощнейшим инструментом, указывающим нам как направление, так и способ решения целого класса объединенных общим признаком проблем.

Теория графов к настоящему времени содержит достаточно много эффективных инструментов для решения столь же широкого круга проблем. Однако, средства и идеи, сегодня относящиеся к области дискретной математики, именуемой теорией графов, пребывают по сей момент в некотором эклектичном единстве как бы не без насильственного понуждения. Круг вопросов, решаемых теорией графов, и разнообразие привлекаемых для этого моделей и механизмов их решения столь обширны, что попытки популяризовать теорию графов в целом должны опираться на немалую дерзость. Академическое и глубокое изложение специфических нюансов теории графов не будет целью настоящей статьи. У нас есть намерение говорить лишь о том, чему мы нашли полезное (или относительно полезное) и нескучное применение.

И между прочим, «откуда есть пошло» теория графов?

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

Из письма Леонарда Эйлера к своему другу Карлу Готлибу Элеру, 03 [14] апреля 1736 г. [1]

Рис. 1. Кёнигсберг на гравюре 17 века.

Считается, что теория графов начала оформляться как самостоятельная математическая дисциплина после показательного решения Эйлером «задачи о семи мостах«,– задачи чисто логистической,– применение теории графов к решению «задачи с четырьмя цветными кубиками«, на мой взгляд, требовало значительно большей изобретательности и большой искушенности в предмете, достигаемыми лишь постоянными упражнениями в практическом применении теории графов, хотя, к моменту решения последней из упомянутых задач от цитируемой переписки минуло более двух веков, и предмет новой дисциплины, лишь туманно виденной Эйлером, успел приобрести очертания вполне конкретные и накопить некоторый опыт практического применения усилиями выдающихся ученых, развивавших идеи Эйлера.

[Рис. 1 может дать некоторое представление о «задаче», упоминаемой в процитированной фразе.] Частью городской коммуникации и архитектурного ансамбля города Кёнигсберга в 1736 году являлись 7 мостов (эти старые мосты не сохранились) через реку Прегель. Трудно сказать, насколько широко была распространена загадка о том, можно ли пройти по всем семи мостам, не пройдя дважды ни по одному из них, и серьезно ли городские службы думали над утверждением такового маршрута для гостей города и горожан, но эта загадка сумела привлечь внимание Леонарда Эйлера, – правда, оставалась довольно длительное время единственным известным примером применения метода, предложенного великим математиком. Более ста лет работа Эйлера не вызывала особого интереса у ученого сообщества. Термин «граф» ввёл венгерский математик Дениш Кёниг только в 1936 году.

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

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

Из письма Леонарда Эйлера к Джиованни Джакобо Маринони, 13 [24] марта 1736 г. [2]

(Судя по письмам Леонарда Эйлера, великий ученый не без удовольствия решал и другие головоломные задачи..)

Задача о семи мостах

Карлу Готлибу Элеру, 03 [14] апреля 1736

Я рассмотрел произвольно взятую фигуру разветвления реки, а также мосты а, b, с, d, e, f, как это указано на рисунке, и установил, что возможен переход, который я представляю следующим образом. Области, отделенные друг от друга водой, я называю буквами А, В, С, и когда предполагается переход через мосты из одной области в другую, [а именно] переход из А в В через мост или а или b, — наиболее удобно назвать [буквами] АВ, из которых первая буква А будет обозначать область, из которой переходят. Итак, АВСАСАВ будет определять переход, совершаемый через все мосты по одному разу; число этих букв должно быть на единицу больше, чем число мостов; это должно иметь место при любом возможном переходе описанным способом, в чем каждому легче убедиться самому, чем доказывать. Теперь я рассматриваю, сколько раз в ряде букв А, В, С, А, С, А, В должны встретиться буквы ABC, о чем нужно судить по числу мостов, ведущих в каждую из областей. Так, к области А ведут пять мостов: а, b, с, d, e, и сколько раз буква А встречается в середине того ряда, столько раз встречаются два из этих мостов, ибо с одной стороны нужно перейти в область А, с другой стороны — выйти оттуда. Если А встречается или в начале, или в конце того ряда, тогда единственный переход моста соответствует А. Отсюда следует, что, если число мостов, ведущих в область А, будет нечетным, тогда переход через все мосты не может совершиться иначе, чем таким образом, чтобы он или начинался в области А, или заканчивался в области А. А если число мостов, ведущих к А, будет четным, тогда переход может быть совершен и без этого условия, чтобы начинаться или заканчиваться в А, но если он начинается в А, то должен будет там же и закончиться. Отсюда вытекает, что в ряде АВСАСАВ любая буква, за исключением первой и последней, обозначает переход, ведущий через два моста в область, обозначенную этой буквой.

Следовательно, надо держаться следующего правила: если на каком-либо рисунке число мостов, ведущих в некоторую область, будет нечетным, тогда желаемый переход через все мосты одновременно не может быть осуществлен иначе, как если переход или начинается, или заканчивается в этой области. А если число мостов четное, отсюда не может возникнуть никакого затруднения, так как ни начало, ни конец перехода при этом не фиксируются. Отсюда следует такое общее правило: если будет больше чем две области, к которым ведет нечетное количество мостов, тогда желательный переход вообще не может быть совершен. Ибо представляется совершенно невозможным, чтобы переход и начинался, и заканчивался в какой-нибудь одной из этих областей. А если будут только две области такого рода (так как не могут быть даны одна область этого рода или нечетное число областей), тогда может быть совершен переход через все мосты, но с таким условием, чтобы начало перехода было в одной, а конец в другой из этих областей. Когда в предложенной фигуре А и В есть области, к которым ведет нечетное число мостов, а число мостов, ведущих к С, является четным, то я считаю, что переход или построение мостов может иметь место, если переход начинается или из А, или из В, а если же кто-нибудь пожелает начать переход из С, то он никогда не сможет достигнуть цели. В расположении кенигсбергских мостов я имею четыре области А, В, С, D, взаимно отделенные друг от друга водой, к каждой из которых ведет нечетное число мостов.

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

Рис. 2. Граф Кёнигсбергских мостов.
Рис. 3. Головоломка «Конверт».

Следовательно, ты можешь убедиться, славнейший муж, что это решение по своему характеру, по-видимому, имеет мало отношения к математике, и мне непонятно, почему следует скорее от математика ожидать этого решения, нежели от какого-нибудь другого человека, ибо это решение подкрепляется одним только рассуждением и нет необходимости привлекать для нахождения этого решения какие-либо законы, свойственные математике. Итак, я не знаю, каким образом получается, что вопросы, имеющие совсем мало отношения к математике, скорее разрешаются математиками, чем другими [учеными]. Между тем ты, славнейший муж, определяешь место этого вопроса в геометрии положения, и что касается этой новой науки, то, признаюсь, мне неизвестно, какого рода относящиеся сюда задачи желательны были Лейбницу и Вольфу. Итак, я прошу тебя, если ты считаешь, что я способен нечто создать в этой новой науке, чтобы ты соблаговолил мне прислать несколько определенных, относящихся к ней задач, для того, чтобы я мог лучше уяснить себе, что именно представляется желательным. Между тем, поскольку мне известно, что Ты также можешь составить суждение о математических науках на основании одной только задачи, которую следует предложить и решить, начало чему по Твоей просьбе предложил преславный Кюн, я хотел бы, чтобы он представил нам такого рода задачи, которые он считает более трудными, [сделав это] как для прогресса науки, так и для упражнения наших сил.

Едва ли приведенные выше рассуждения Леонарда Эйлера вызвали у вас благоговейный трепет, какой, например, совершенно извинителен для человека, сколько-нибудь приобщенного к математике, восхищенно перебирающего следствия эффектной формулы Эйлера для комплексных чисел.

Следствие Формулы, связывающее пространства иррациональных и мнимых чисел:

Поскольку из Формулы Эйлера следует, что , нетрудно видеть, что

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

Однако же, уж очень эта трёхсотлетней давности «задача о Кенигсбергских мостах» (Рис. 2) напоминает вам «конвертик», который в начальных классах вы успешно рисовали в «один проход» (Рис. 3), с каждым новым открытым вами способом нарисовать этот «конверт» умножая свое торжество над соревнующимися с вами в этом занятии одноклассниками.

Сколько сегодня найдете маршрутов? Полагаю, что внимательно читавшие выше письма Эйлера не ошибутся в выборе начальных точек для построения своих маршрутов (в первом классе у вас не было такой подсказки?), и предсказать, где их маршруты завершатся, тоже не составит труда. Заодно, достройте восьмой мост в «городе мыслителей» и наполните желанным смыслом пешие прогулки его жителей.

А мостов могло быть и больше.

В задачнике Генри Э.Дьюдени «520 головоломок» (я располагаю изданием 1975 года, Издательство «Мир», Москва [3] ) есть немало задач, которые могут быть решены прямо по инструкциям Эйлера. Взглянем на одну из таких задач, которой в указанном издании присвоен номер 408.

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

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

Если вы решите повторить эти вычисления, не забудьте, что нечетный узел «С», с которого я начинаю движение, имеет степень 3. Этой же программой можно посчитать «конверт» и сравнить результат с маршрутами, найденными «вручную».

Итого, маршрутов насчитывается 67344 вариантов. Несколько многовато, но настоящая дружба должна быть способна вынести и такое количество визитов, осталось найти «настоящую» обувь, т.к. это испытание и для неё.

Пути и деревья

Графические схемы, конечно же, не исчерпываются замкнутыми маршрутами, и наш путь ведет нас к деревьям…

С 1978 года в мире, лежащем за пределами ваших компьютеров, то там, то сям, и никогда не здесь, происходят нешумные или даже почти конспиративные встречи незнакомых со мной (я так полагаю) людей, зовущиеся International Puzzle Party. Получить приглашение на это мероприятие можно только от члена этого закрытого клуба. Где и когда произойдет следующая встреча, никогда не известно за пределами клуба. Если верить лаконичному анонсу официального сайта IPP, то опаснее рукопожатий коллекционеров головоломок на самих «пати» ничего не происходит. Однако, постфактум тайного собрания, прочим смертным случается увидеть каталог диковинных головоломок, тщательно проинспектированных искушенным в головоломных задачах комитетом этого элитарного форума. Одна из таких головоломок, представленная на IPP 37, проходившем в августе 2017 года в Париже (вы тоже почувствовали влечение к коллекционированию головоломок?), была предложена участником «форума нешарнирных головоломок» (я несведущ в его международных перемещениях) в качестве разминки для мозгов охочим до такого досуга коллегам.

Мне эта головоломка показалась несколько напоминающей задачу Дьюдени, обремененную, однако, несколькими нюансами.

Разработчиком (создателем, творцом, демиургом) этого образца неординарной мысли, шедевра изощренной человеческой изобретательности отмечен Donghoon Pee – творец, видимо, скромный и незаслуженно малоизвестный здесь на Хабре,– последнюю несправедливость мы сейчас исправим, хотя, конечно, загубим интригу… Мне и самому жалко лишать читателей Хабра возможности самостоятельно поразмыслить над головоломкой 2&1 автора Donghoon Pee – могу лишь посоветовать тем, кто страстно желает решить головоломку самостоятельно, закрыть ладошками рисунки и часть относящегося к головоломке текста ниже.

У Donghoon Pee (Донгун Пи – наиболее вероятное прочтение, но, чтобы не рисковать, буду пользоваться латинским написанием) есть свой канал на youtube.com, страница в фейсбуке, проживает он в городе Сеуле и является профессиональным создателем (язык не поворачивается сказать «дизайнером», хотя сам он именно так зовет свой род занятий) головоломок. И его работы не раз удостаивались внимания клуба IPP. Будем надеяться, доходы этого безусловно достойного человека не понесут ущерба от этой публикации.

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

Задача с четырьмя цветными кубиками

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

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

Имея инструкции для второго набора – т.е. для второй пары граней пирамиды, мы можем окончательно собрать комбинацию, являющуюся решением головоломки. Таким образом, выделив из мультиграфа (совокупности графов кубиков) два подграфа, указывающих на различные наборы цветов, – а для этого достаточно, чтобы одно и тоже ребро (поскольку именно ребро указывает на связь) не использовалось одновременно в каждом из графов,– мы получим легко читаемое решение головоломки: нам достаточно, например, согласно первой инструкции расположить кубики в соответствии «верх-низ» и привести их в соответствии со второй инструкцией, поворачивая вправо-влево. [Напомню, что «петля» так же является узлом 2-ой степени]. Из всех представленных на рисунке подграфов, только два образуют пару с несовпадающими ребрами. Это так называемое «единственное решение» «правильной» головоломки.

Не лишнее, вероятно, подробно рассмотреть пример развертки мультиграфа для красивой сборки, имеющей в 24-х положениях на каждой из своих сторон все 4-е цвета («неправильная» головоломка, на предыдущей публикации предыдущей публикации она представлена на Рис. 6): три подграфа (на левом рисунке, это три крайних левых подграфа) могут складываться в три пары с несовпадающими ребрами – сборка с «тремя решениями» по терминологии, распространенной в англоязычной среде.

Если мне в некотором, условно говоря, «потоке кубических сущностей» понадобится «выловить симметричные сборки», я постараюсь избежать банального перебора. Например, из кубиков, развертки которых приведены на Рис.2 той же публикации можно быстро сложить 16 наборов с «тремя решениями».

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

Обратное моделирование

Можно ли от желаемой графической модели перейти к конкретной реализации чего бы то ни было? – Едва ли существует однозначный ответ, но в большинстве случаев я бы советовал не пытаться осуществить подобные переходы, если только искомая вами модель не ограничивается полностью описываемыми в рамках графического прототипа особенностями. Описывая объект из реального мира, вы пренебрегаете частью его свойств перед одной сущностной особенностью, в угоду выбранной вами модели.

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

Графы решений,— те два пути обхода узлов, которые необходимо выделить из мультиграфа,– будут подобны, хотя сам исходный мультиграф может делиться различным образом, т.к. нумерация граней все-таки вносит особенности в общую топологию графа. Графическая модель, которую мы используем для нахождения решения головоломки, подобной Instant Insanity, характеризует наборы кубиков только с точки зрения оптимизации поиска решения этой головоломки. Эта модель построена на основе анализа топологической структуры набора кубиков для решения только одной узкой задачи – задачи взаимного расположения кубиков. Отдельный мультиграф, как и граф отдельного кубика, не указывает на уникальность объекта, да и не должен – мы же сами искали нечто общее в явлении, а не в объекте. Портретный образ не предстает из лаконичной характеристики «характер – твердый, нордический».

Рис. 4. 204 графа «головоломки с четырьмя цветными кубиками».

Изоморфизм

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

Возьмем развертку головоломки Instant Insanity на сайте Роберта Штегманна (R.Stegmann – он то, наверное, «рукопожатый» всем клубом IPP!) — я буду придерживаться следующего порядка обхода граней кубика: нижняя грань→лицевая→верхняя→задняя→левая→правая.

Самая распространенная из разверток с отмеченного сайта (автором собрано и несколько клонов, но мы ориентируемся на «классический» вариант головоломки) будет в выбранном порядке обхода граней записана следующим образом: RWGGWB, RBBWGG, RGWWRB, GWRBRR.
Надеюсь, что никому не удалось забыть, что при записи графа мы принимаем во внимание лишь пары цветов противоположных граней, и поэтому строчная запись графической конфигурации выбранных кубиков выглядит не иначе, чем: RG|WG|WB, RB|BW|GG, RW|GW|RB, GR|WB|RR. Как видим, мультиграф на первом рисунке полностью соответствует этому набору (ну лишь за исключением, что у меня желтый цвет вместо классического белого).

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

Вместо заключения

Очень надеюсь, что чтение не было скучным. Возможно, кому-то оказалось отчасти полезным. И практически уверен, что количество нарисованных конвертиков к завтрашнему дню несколько возрастет, и кто-то наконец найдет в себе силы и мотивацию отвлечь наследника от его гаджета какой-нибудь занимательной и умной задачей. Эйлер вот не пренебрегал…

1.↑ Леонард Эйлер. Письма к ученым, Издательство АН СССР, 1963, стр.339
2.↑ Леонард Эйлер. Письма к ученым, Издательство АН СССР, 1963, стр.153
3.↑ Генри Э. Дьюдени. 520 головоломок. Составитель и редактор американского издания М. Гарднер, Издательство МИР, Москва, 1975

Развертки кубов переставлены в порядке 1342. Соответствующий разверткам мультиграф размещен третьим среди графов задачи.
Правильный ответ: «третий».

Источник