Теория графов началась как малоизвестная область математики, но со временем превратилась в невероятно полезный инструмент для понимания современного мира. По сути, это упрощенный метод работы с абстрактными объектами и связями между ними. Эта область исследований обычно включается в более широкую область комбинаторики, но имеет много уникальных аспектов, которые делают ее полезной. По мере того, как мир становится все более связанным, а данные становятся более доступными, теория графов становится необходимой структурой для их осмысления.
В этой статье я расскажу об интересной истории теории графов и локальной проблеме, которая привела к ее развитию. Я объясню некоторые основные концепции теории графов и затем рассмотрю несколько крутых современных приложений! Теория графов — это мощный инструмент для понимания окружающего нас мира!
Графы и мосты
Истоки теории графов можно проследить до легендарного математика Леонарда Эйлера в начале 1700-х годов. Он уже был знаменитым математиком в то время, когда мэр Кёнигсберга попросил его решить интересную задачу, созданную местными жителями для развлечения. Согласно фольклору, жители Кёнигсберга были очарованы необычным расположением мостов в их городе (показаны красным цветом выше). Они придумали себе задачу попытаться пройти по каждому из мостов, не переходя через один и тот же мост более одного раза. Нельзя также обмануть, переплыв реки!
Эйлер жил недалеко от Кёнигсберга в городе Санкт-Петербург и был приглашен для решения этой задачи. Сначала Эйлер посчитал проблему тривиальной, но затем его заинтриговало, что ни одна из знакомых ему областей математики, таких как геометрия, алгебра или теория чисел, не имела инструментов для ее решения. Он понял, что хотя эта проблема по своей сути математическая, математика, необходимая для ее решения, еще не существует.
Эйлер начал работать и изобрел новые математические концепции, которые послужили основой для теории графов. Он смог использовать эти концепции, чтобы доказать, что задача невыполнима! Нет способа пройти по каждому мосту только один раз при данном расположении мостов. Я проведу вас через доказательство, которое он использовал, но сначала мне нужно изложить основы теории графов, использованные Эйлером.
Основы
В теории графов есть два основных объекта, которые нужно знать: узлы и ребра. Узел — это просто пространство, обычно визуализируемое кругом. В приведенном выше примере узлы пронумерованы 1, 2, 3,… Вы либо находитесь в узле, либо нет, не имеет смысла спрашивать "где" что-то находится внутри узла. Хотя в этом примере узел представляет землю, он может представлять любой объект. Единственное важное — мы не рассматриваем ничего внутри узла.
Пример графа выше также показывает некоторые линии, соединяющие каждый узел. Как вы могли догадаться, эти линии представляют ребра. Каждое ребро может соединять только два узла друг с другом. Также возможно иметь несколько ребер между одним и тем же набором узлов, как мы увидим позже.
Иногда вы можете услышать другие названия этих объектов. Узлы также могут называться вершинами или точками, а ребра могут называться линиями или связями.
Каждый граф определяется двумя множествами: одно содержит каждый узел, а другое — каждое ребро. Ребро может быть математически определено как пара узлов. Например, приведенный выше граф определяется следующим образом. G = {N, E}, где N = {1, 2, 3, 4, 5, 6} и E = { {1, 2}, {1, 5}, {2, 5}, {2, 3}, {3, 4}, {4, 5}, {4, 6} }. Первое множество перечисляет имена каждого узла, а второе множество перечисляет пары, каждая из которых представляет ребро между указанными в паре узлами. Как и в множестве, порядок элементов не имеет значения, как и порядок внутри пары узлов.
Прежде чем мы перейдем к доказательству Эйлера, необходимо определить еще одну концепцию. Каждый узел в графе имеет степень, обозначаемую знаком абсолютного значения. Степень показывает, сколько ребер соединено с данным узлом. Опять же, используя приведенный выше пример, я могу видеть, что |5| = 3 и |6| = 1. Обратите внимание, что значение в чертах представляет имя узла, а результат — это фактическое число. В следующем примере я буду использовать буквы для обозначения узлов!
Эйлеру пришлось изобрести все эти концепции, чтобы доказать, что проблема Кёнигсбергских мостов невыполнима! Обозначения в его оригинальной статье были гораздо менее формализованы, но идеи остались теми же. Теперь, когда у нас есть основы, давайте посмотрим, как это было доказано.
Доказательство
Эйлер начал с максимального упрощения задачи. Я отмечу, что язык, используемый Эйлером в его статье, отличается от того, что я описываю здесь, потому что теория графов еще не была формализована. Структура доказательства, которую я представляю здесь, аналогична использованной им, но я не столь строг, как он. На рисунке ниже показан набросок из его статьи, описывающий его решение. Каждый из земельных участков получил буквенные обозначения: A, B, C и D. Эйлер понял, что перемещение внутри каждого участка не имеет значения, важны только переходы по мостам.
Теперь мы можем превратить это в граф! Я сделал диаграмму графа, описывающего эту задачу ниже.
Вы можете видеть, что узлы представляют участки земли, а ребра представляют мосты между ними. Прозрение Эйлера заключалось в рассмотрении каждой "встречи" с земельным участком. Для каждой встречи нужно использовать один мост, чтобы войти на участок, и другой, чтобы покинуть его. Единственным исключением является начальная и конечная точки. Это накладывает интересные ограничения на расположение мостов, позволяющее создать путь, который мы ищем.
Это означает, что каждая встреча использует два моста, за исключением первой и последней. Помните, что в этой задаче каждый мост можно пересечь только один раз, и мы должны пересечь каждый мост. Можете ли вы теперь увидеть, почему это невозможно? Подумайте о порядке каждого узла в приведенном выше графе. У нас |A| = 5, |B| = 3, |C| = 3, |D| = 3. У всех нечетное количество мостов! Для того чтобы существовал путь, использующий каждый мост только один раз, все узлы, кроме двух, должны иметь четный порядок. Два узла с нечетным порядком будут начальной и конечной точками. Также возможно, чтобы каждый узел имел четный порядок, если ваши начальный и конечный узлы совпадают.
Из-за истории, связанной с этим, этот метод перемещения по графу называется путём Эйлера. Если возможно начать и закончить в одном и том же узле, это называется циклом Эйлера. Я представил только краткую версию доказательства, но у меня есть ссылка ниже, если вы хотите более подробное объяснение.
Теперь я собираюсь немного изменить приведенный выше граф.
Я просто удалил ребро между B и D. Теперь в этом графе |A| = 5, |B| = 2, |C| = 3, |D| = 2. У нас есть конфигурация, требуемая Эйлером для создания пути, проходящего по каждому мосту только один раз. Наш путь должен начинаться в A или C и заканчиваться в A или C. На самом деле существует несколько возможных путей, но один из примеров: A -> B -> A -> C -> A -> D -> C. Всякий раз, когда соединение между двумя узлами выполняется несколько раз, можно предположить, что мы пересекаем ребро между ними, которое еще не использовалось. Попробуйте найти другой путь Эйлера в этой измененной конфигурации! Возможно ли начать и закончить в одном и том же узле для этого графа (цикл Эйлера)?
Эйлер также потратил время на создание новых компоновок. См. еще один набросок из его статьи ниже. В этой конфигурации возможно пересечь каждый мост только один раз? Мой совет — превратить его в граф и затем проверить порядок каждого узла.
В следующем столетии теория графов стремительно набирала популярность, так как математики взяли эти идеи и развили их. Многие знаменитые доказательства в математике являются результатом концепций, найденных в теории графов. Сейчас я расскажу о недавней горячей теме в теории графов под названием сети малого мира, а затем расскажу о знаменитом доказательстве в теории графов под названием теорема четырех красок.
Малые миры
Название "малые миры" относится к очень особому типу графа, который был обнаружен в природе. Впервые он был описан Дунканом Уоттсом и Стивеном Строгатом в 1990-х годах. Эти графы огромны и содержат множество узлов. В среднем, большинство узлов не связаны друг с другом ребром. Однако, из-за природы графа малого мира, большинство узлов разделены всего несколькими ребрами. Более точно, граф малого мира — это граф, где среднее расстояние между узлами масштабируется логарифмом от количества узлов.
Сети малого мира встречаются в веб-ссылках, пищевых цепочках, нейронах мозга и сетях избирателей. Важной особенностью этих графов является наличие специализированных "узлов-хабов", которые являются важными узлами, имеющими много соединений. Понимание их динамики и изучение того, как они создаются в природе, является активной областью исследований. В своей статье Уоттс и Строгат предлагают модель Уоттса-Строгата в качестве потенциального метода для случайной генерации этих графов. Однако она не является совершенной и требует дальнейших исследований.
Теорема четырех красок
Вот вам интересное приложение теории графов. В 1970-х годах было доказано, что любую карту можно раскрасить всего в четыре цвета таким образом, чтобы один и тот же цвет не касался самого себя. Вы можете увидеть на изображении выше сложный массив форм. И все же с помощью всего четырех цветов можно создать изображение, где каждый цвет никогда не соприкасается с собой. Это очень неинтуитивный результат, который был впервые предложен в 1850-х годах Фрэнсисом Гатри, который создавал карты Англии и заметил, что ему всегда требовалось только четыре цвета для разных регионов.
Вы, наверное, догадались, что изображение моделируется графом. Математики использовали разные типы узлов для обозначения цвета каждой формы. Оказывается, существует конечное количество способов, которыми соседние формы могут быть представлены графом, точно 1834. Это было огромное количество конфигураций для проверки, и математики, работавшие над проектом, использовали для этого компьютер. Это было первое доказательство, проведенное с обширной помощью компьютера!