Теория графов

Теория графов — раздел дискретной математики, изучающий свойства графов. Теория графов имеет широкие практические приложения. Многие проблемы, возникающие в таких весьма различных областях знания, как психология, химия, электротехника, планирование перевозок, управление, торговля и образование, могут быть сформулированы как задачи теории графов. Ввиду этого теория графов интересна не только сама по себе, но также и тем, что представляет общую основу, на которой результаты, полученные в различных областях знания, могут быть собраны, классифицированы, обобщены и распространены.
Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.
Теория графов содержит большое количество нерешённых проблем и пока не доказанных гипотез.
Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Город Кенигсберг (нынешний Калининград), раполагавшийся тогда в Восточной Пруссии, был построен в месте слияния двух рек на их берегах и на двух островах (схема представлена на рисунке 1).

Рисунок 1 – Схема расположения Кенигсбергских мостов

В городе было семь мостов, которые соединяли острова между собой и с береговыми частями города. Мог ли любой житель Кенигсберга, выйдя из дома, пройти по всем семи мостам города в точности по одному разу и вернуться домой? Обобщенный вариант данной задачи, называют задачей почтальона. Эта задача имеет решение и в данном случае ответ на этот вопрос: “нет не мог”.
К 50-м годам нашего века в теории графов сложились два существенно различных направления: алгебраическое и оптимизационное. Последнее получило широкое развитие благодаря появлению электронных вычислительных машин (ЭВМ) и в связи с разработкой методов линейного программирования.
Разбермся теперь, что из себя представляет граф и дадим ему строгое определение.

Рисунок 2 – Граф

Граф состоит из двух типов элементов: вершин и дуг, соединяющих между собой эти вершины. При изображении графов чаще всего используется следующая система обозначений: каждой вершине сопоставляется точка на плоскости, и если между вершинами существует ребро, то соответствующие точки соединяются отрезком (стрелкой). Для графа представленого на рисунке 2: A, B, C, D, E – вершины; a, b, с, d, e, f, g – дуги графа.

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

Далее введем основные определения, используемые в теории графов.

Граф, в котором направления дуг не задаются, называется неориентированным. Неориентировалные дуги называются ребрами. Например в графе представленом на рисунке 2 дуги a, b, d, g – неориентированые (они обозначены отрезками); дуги c, e, f – ориентированые (обозначены стрелочками).

Сеть — граф, каждой дуге которого поставлены в соответствие одно или несколько чисел. Если каждой дуге графа, изображонного на рисунке 2, приписать конкретные значения расстояний, то исходный граф превратится в сеть.

Дуга, начальная и конечная вершина которой совпадают, называется петлей. На рисунке 2 дуга h является петлей.

Дуга и вершина инцидентны друг-другу, если вершина является для этой дуги концевой или начальной точкой. На рисунке 2 дуга с и вершина A инцидентны друг другу.

Если две дуги инцидентны одной и той же вершине то говорят что эти дуги инцидентны друг-другу. На рисунке 2 дуги a и с инцидентны друг-другу так как каждая из них инцидентна вершине A.

Будем называть две вершины соседними, если есть дуга, их соединяющая. На рисунке 2 вершины A и B соседние, поскольку существует дуга a, которая соединяет эти вершины.
Рассмотрим произвольную последовательность вершин х₁, х₂,…, х_n, х_n+1, Цепью называется любая последовательность дуг a₁, a₂, …, a_n, такая, что концевыми точками дуги a_i являются вершины х_i и х_i+1 т. е. a_i = (х_i, х_i+1) или a_i = (х_i+1, х_i) для i = 1, 2, …, n. Вершина х₁ называется начальной вершиной цепи Вершина х_n+1 называется конечной вершиной цепи. Будем говорить, что цепь соединяет начальную вершину с конечной. Длина цепи совпадает с числом входящих в нее дуг. На рисунке 2 последовательность дуг e, g, i, с образует цепь длины 4, которая соединяет вершину B с вершиной A.
Цепь, для которой а = (х_i, х_i+1) при всех i = 1, 2, …, n, представляет собой путь. длина пути, его начальная и конечная вершины могут быть определены точно так же, как для цепи. Напрямер, на рисунке 2 дуги a, c, i, g образуют путь длины 4, соединяющий вершину B с вершиной C.
Циклом называется цепь, у которой начальная и конечная вершины совпадают. Контуром называется путь, у которого начальная и конечная вершины совпадают. Длина цикла или контура определяется так же, как длина соответствующей цепи. Например, на рисунке 2 дуги a, e, g, i, с образуют цикл длины 5, а дуги a, c, i, g, e — контур длины 5.
Цепь, путь, цикл или контур называются простыми, если ни одна вершина не инцидентна более чем двум входящим в нее дугам (т. е. если цепь, путь, цикл или контур не содержат внутри себя циклов).

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