Введение
Теория графов - раздел математики и информатики, нашедший широкое применение в современных прикладных задачах. В первую очередь, это задачи поиска маршрута на картах, но её применение не ограничивается навигационными приложениями. Графы возникают там, где между данными существуют какие-либо нелинейные связи. Например, это могут быть компьютеры, соединённые в сеть. Или же это могут быть задачи, которые надо выполнить в каком-то порядке, причём некоторые задачи надо выполнять строго после каких-то других. Существуют алгоритмы, позволяющие вычислить оптимальный порядок выполнения таких задач.
История возникновения теории графов. Леонард Эйлер и задача о Кёнигсберских мостах
Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.
Издавна среди жителей Кёнигсберга (теперь Калининграда) была распространена такая загадка: как пройти по всем мостам, не проходя ни по одному из них дважды? Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.
В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно).
Для того, чтобы решить эту задачу, Эйлер сделал специальные обозначения. Каждую часть суши (остров или берег реки) он обозначил кружком на бумаге, а затем соединил линиями те кружки, между которыми существуют мосты. Такие обозначения подчеркивают, что в этой задаче фактическое расположение, форма, длина и другие свойства объектов не представляют интереса, важны только связи между ними. Такая картинка на бумаге или на экране компьютера называется графом. Кружки - это его вершины, а линии - рёбра. Размышляя над этой и другими картинками из кружков и линий, Эйлер пришел к следующим выводам о графах:
- Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно всегда быть чётно. То есть, просто не может существовать графа, который имел бы нечётное число нечётных вершин.
- Если все вершины графа чётные, то его можно начертить не отрывая карандаша от бумаги, при этом начинать можно с любой вершины графа и завершить его в ней же.
- Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
(такой граф называют уникурсальным)
Доказательство. Вначале заметим, что если все вершины графа имеют степень не меньше двух, то в нем существует хотя бы один цикл.
Рассмотрим случай, когда все вершины четны. Применим «метод стирания». Выберем некоторую точку и начнем строить путь. Так как степени всех вершин четны, то они не меньше двух. Поэтому, войдя по некоторому ребру в данную точку, мы всегда можем выйти из нее по второму ребру. Будем отмечать пройденные вершины. Так как число вершин конечно, то на каком-то шаге мы перейдем в одну из уже отмеченных вершин и таким образом замкнем цикл. Теперь сотрем этот цикл (естественно, запомнив его где-то) и рассмотрим получившийся граф. Он может оказаться несвязным, но, тем не менее, все его вершины будут иметь четную степень. Применим к этому графу ту же процедуру, и будем это делать до тех пор, пока остается хотя бы один нетривиальный подграф. В результате мы получим несколько циклов, которые не имеют общих ребер, а все вместе образуют исходный граф. Нам остается только склеить эти циклы в один. Возьмем два цикла (…ВАС…) и (…НАМ…), имеющие общую вершину А, разрежем их в этой вершине и склеим по такому правилу: сначала выписываем вершины первого цикла, потом, дойдя до точки А, записываем все вершины второго цикла, а затем продолжаем выписывать оставшиеся вершины первого цикла. Очевидно, что в итоге у нас получится один цикл, который содержит все ребра исходного графа.
Предположим теперь, что в исходном графе ровно две нечетных вершины А и В. Соединим их дополнительных ребром АВ, и получим граф, все вершины которого четны. Построим для него эйлеров цикл по указанному выше алгоритму. Перепишем его так, чтобы вершина А была начальной, а ребро АВ - последним. Удалив из этого цикла ребро АВ получим цикл, начинающийся в А и заканчивающийся в В. Этот путь проходит через все ребра исходного графа.
Предположим теперь, что граф уникурсален. Докажем, что в нем не более двух нечетных вершин. Очевидно, что рисовать такой граф нужно, начиная с нечетной вершины. Причем завершить маршрут нужно в другой нечетной вершине. Если же имеется еще одна нечетная вершина, то она не может быть ни начальной, ни конечной. Поэтому, когда мы в нее заходим, то должны обязательно выйти. Каждый проход через вершину уменьшает число не пройденных ребер, связанных с этой вершиной, ровно на два. В итоге, на каком то шаге в нечетной вершине останется только одно не пройденное ребро, зайдя по которому в вершину мы уже не сможем из нее выйти. Теорема доказана полностью.
Граф кёнигсбергских мостов имел четыре нечётные вершины (т.е. все), следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
Определения теории графов
Граф - конечное множество вершин, природа которых не важна, и конечно множество рёбер, соединяющих между собой какие-либо вершины.
Графы могут быть ориентированными и неориентированными. Если в рамках задачи по рёбрам можно перемещаться в обоих направлениях, то граф называется неориентированным. Если же по каждому ребру можно пройти только в одну сторону, то граф ориентированный. В таком случае рёбра обычно обозначаются стрелками, а не просто линиями.
Пример ориентированного графа
Иногда бывает полезно связать с ребрами графа какие-то числа. Это могут быть длины дорог или плата за проезд, если граф моделирует карту какой-то местности. В таком случае граф называется взвешенным, а сами числа - весами.
Пример: граф с шестью вершинами и семью рёбрами
Граф, в котором каждая пара вершин соединена ребром, называется полным. Обозначение: Kn - граф, состоящий из n вершин и ребер, соединяющих всевозможные пары этих вершин. Такой граф можно представить как n-угольник, в котором проведены все диагонали.
Ниже приведены полные графы с числом вершин от 1 до 8 и количества их рёбер.
Степенью вершины называется число ребер, которым принадлежит вершина (число рёбер с концом в данной вершине).
Дополнением данного графа называется граф, состоящий из всех ребер и их концов, которые необходимо добавить к исходному графу, чтобы получить полный граф.
Граф, который можно представить на плоскости в таком виде, когда его ребра пересекаются только в вершинах, называется плоским.
Многоугольник плоского графа, не содержащий внутри себя никаких вершин или ребер графа, называют его гранью.
Понятия плоского графа и грани графа применяется при решении задач на «правильное» раскрашивание различных карт.
Путем от вершины A до вершины X называется последовательность ребер, ведущая от A к X, такая, что каждые два соседних ребра имеют общую вершину, и никакое ребро не встречается более одного раза.
Циклом называется путь, в котором совпадают начальная и конечная точка (т.е. можно «ходить по циклу» - «ходить по кругу»).
Простым циклом называется цикл, не проходящий ни через одну из вершин графа более одного раза.
Длиной пути, проложенного на цикле, называется число ребер этого пути.
Две вершины A и B в графе называются связными (несвязными), если в нем существует (не существует) путь, ведущий из A в B.
Граф называется связным, если каждые две его вершины связны; если же в графе найдется хотя бы одна пара несвязных вершин, то граф называется несвязным.
https://habr.com/ru/company/otus/blog/568026/
Специальным типом графов является дерево. В дереве выделяется особая вершина - корень, которая соединена рёбрами с другими вершинами - своими потомками, которые в свою очередь могут иметь своих потомков. Вершина, не имеющая потомков, называется листом. Наглядный пример дерева - иерархия файлов и папок в файловой системе компьютера или систематика живых организмов
Если не выделять особым образом корень, то дерево - это просто любой связный граф, не имеющий циклов.
Представление графов в памяти
Чтобы решать задачи, связанные с графами, нужно сначала научиться сохранять его в памяти, а ещё лучше - сохранять оптимально. Существует несколько способов сделать это, и для каждой конкретной задачи оптимальным будет свой способ.
Матрица смежности
Самый простой способ сохранить граф в памяти - матрица смежности. Нарисуем таблицу, которая чем-то напоминает таблицу умножения: в первой строчке и в первом столбце будут стоять номера (или любые названия) вершин, а на пересечении столбца и строки будем ставить, например, 1 если между этими вершинами есть ребро и 0 если нет. Кроме 1 и 0 можно ставить, например, вес ребра, а для обозначения отсутствия ребра - просто очень большое число. Какой именно вариант использовать, зависит от каждой конкретной задачи. Также задача определяет, что ставить на диагонали получившейся матрицы.
Граф и его матрица смежности.
Матрица смежности элементарно реализуется в большинстве языков программирования, достаточно лишь объявить двумерный массив.
Другие способы
Существуют и другие способы хранения графа в памяти, например, матрица инцидентости, которая удобна при использовании методов линейной алгебры в задачах на графах, или списки рёбер, но практическое применение в задачах обычно находят описанные выше два способа.
Основные задачи теории графов
Обходы графа
Часто требуется обойти все вершины графа в определённом порядке, например, для проверки его на связность или упорядочения задач при планировании (топологическая сортировка графа). Существует два стандартных метода обхода графа - обход в глубину и обход в ширину.
Обход в глубину (DFS)
Обход в глубину можно описать так: представьте, что вы в лабиринте. Идите всегда прямо, а на всех развилках выбирайте самый левый путь. Упёршись в тупик, возвращайтесь обратно до последней развилки и выбирайте следующий путь слева. Продолжайте, пока не обойдёте весь лабиринт.
Обход в ширину (BFS)
Обход в ширину можно наглядно представить себе так: в какой-то стартовой точке лабиринта разливается жидкость, и она начинает равномерно заполнять все его помещения, продвигаясь все дальше. При этом в каждый момент времени все точки края разливающейся воды находятся на одном расстоянии от начала.
Этот обход, как и обход DFS, можно применять для поиска путей в графах. Основное его отличие в том, что поиск не уходит сразу далеко от начала, а продвигается вглубь графа постепенно, неким «фронтом».
Его реализация немного сложнее, чем DFS. Для этого нам понадобится такая структура данных, как очередь. Очередь, как видно из названия, моделирует обычную очередь в магазине. Обычно это список, в которой можно класть элементы с одной стороны, а забирать - с другой. Обход в ширину хранит в очереди вершины, которые еще предстоит просмотреть.
Другие задачи
Другими классическими задачами теории графов являются, например, задача топологической сортировки и задача поиска наименьшего остовного дерева.
Проблема четырёх красок
Проблема четырёх красок - математическая задача, предложенная Гутри в 1852 году.
Выяснить, можно ли всякую расположенную на сфере карту раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета.
Иначе говоря, показать что хроматическое число плоского графа не превосходит 4.
О доказательстве
К.Аппель и В.Хакен доказали в 1976 г., что так можно раскрасить любую карту. Это была первая крупная математическая теорема, для доказательства которой был применён компьютер. Несмотря на последующие упрощения, доказательство практически невозможно проверить, не используя компьютер. Поэтому некоторые математики отнеслись к этому доказательству с недоверием, что объяснялось не только использованием компьютера, но и громоздкостью описания алгоритма первых доказательств (741 страница), впоследствии были предложены более компактные алгоритмы и скорректирован ряд ошибок. Проблема четырех красок является одним из известнейших прецедентов неклассического доказательства в современной математике.
Исторически планарные графы связаны с одной знаменитой задачей.
Задача о домиках и колодцах. В некоторой деревне есть три колодца. Трое жителей, живущие в трех стоящих рядом домиках перессорились, и решили так протоптать тропинки от своих домов к каждому из трех колодцев, чтобы они не пересекались. Удастся ли им выполнить свой план?
Решим эту задачу. Проведем тропинки так, как это показано на рисунке 8. Как видно, нам удалось провести только восемь тропинок, а девятая должна пересечься хотя бы с одной. Можно доказать (мы не будем приводить строгое доказательство), что эта задача не имеет решения. Дело в том, что по мере проведения тропинок из двух первых домиков, будет получаться некоторый замкнутый контур, внутри которого будет стоять один из колодцев, при этом третий домик будет находиться снаружи от этого контура. Для того чтобы соединить этот домик с колодцем, обязательно потребуется пересечь новой тропинкой одну из уже проложенных.
Задача о четырех красках. На политической карте мира нарисовано несколько государств. Карту нужно раскрасить так, что бы две страны, имеющие общую границу, были покрашены в разные цвета.
В классическом варианте предполагалось, что карту можно раскрасить четырьмя цветами. Покажем, как эта задача связана с графами. Обозначим каждую страну на карте точкой, вершины, отвечающие странам, имеющим общую границу, соединим ребрами. Теперь задачу о раскрашивании можно сформулировать так: раскрасить вершины планарного графа так, чтобы любые две смежные были покрашены в разные цвета. Эта задача может быть решена для графов с малым количеством вершин. Если же число вершин достаточно велико, то гипотеза четырех красок оказывается неверной. (Этот факт установлен с помощью мощных компьютеров.)
Вместе с тем, довольно простыми средствами была доказана теорема о пяти красках.
Теорема. Планарный граф можно раскрасить пятью красками так, что любые смежные вершины будут окрашены в разные цвета.
Еще одна интересная проблема: сколькими способами можно раскрасить граф, если имеется n красок.
Оказывается, что число способов раскрашивания является многочленом от n, коэффициенты этого многочлена можно вычислить с помощью специального алгоритма.
Укажем еще одно обобщение задачи о раскрасках. Известно, что граф без самопересечений располагается на некоторой поверхности (на сфере, на торе, на бутылке Клейна и т.п.), какое минимальное количество красок нужно для его раскрашивания?
Ответ на этот вопрос был получен в разделе математики, называющемся «топологией». Оказалось, что для всех замкнутых двумерных поверхностей (кроме сферы), данное число выражается через Эйлерову характеристику этой поверхности.