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

Теорема 2 (Обобщенная теорема Эйлера о многогранниках). Количество граней плоского графа равно его цикломатическому числу + 1.

В первоначальной формулировке теорема Эйлера о многогранниках звучала так: ``Для любого выпуклового многогранника количество вершин минус количество рёбер плюс количество граней равно 2.''

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

Двойственные графы

Определение 19 (Двойственный граф). Граф, вершинами которого являются грани графа G, изображенного на поверхности, рёбрами – рёбра графа G, гранями – вершины графа G, отношение инцидентности – отношением ограниченности графа G, а отношение ограниченности – отношением инцидентности графа G, называется двойственным графом к графу G.

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

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

Эйлеровы пути,гамильтоновы пути.

Эйлеровы пути

Эйлеровым путем в графе называется произвольный путь, проходящий через каждое ребро графа в точности один раз, т.е. путь v1, ..., vm+1, такой что каждое ребро e E появляется в последовательности v1, ..., vm+1 в точности один раз как e = {vi, vi+1} для некоторого i.

Если v1 = vm+1, то такой путь называется эйлеровым циклом. Задача существования эйлерова пути в заданном графе была решена Эйлером в 1736 году, и представленное им необходимое и достаточное условие существования такого пути считается первой в истории теоремой теории графов.

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

Доказательство. Доказательство достаточности условия теоремы будет следствием анализа алгоритма нахождения эйлерова пути, который будет описан ниже. Необходимость условия очевидна, так как если вершина v, отличная от вершины v1 и vm+1, появляется в эйлеровом пути k раз, то это означает, что степень этой вершины в графе составляет 2k. Отсюда следует, что вершины нечетной степени, если они существуют, являются концами эйлерова пути. Здесь следует отметить, что не существует графов с одной только вершиной нечетной степени. Действительно, обозначая степень вершины v через d(v), имеем

ибо в указанной сумме каждое ребро {u, v} считается дважды: один раз в d(u) и один раз в d(v). Отсюда следует, что число вершин всегда четно.

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

Предположим, что u и v - единственные вершины нечетной степени связного графа G =  V, E, и образуем граф G* добавлением дополнительной вершины t и ребер {u, t} и {v, t} (или просто {u, v}, если {u, v}E ). Тогда G* - связный граф без вершин нечетной степени, а эйлеровы пути в G будут в очевидном взаимно однозначном соответствии с эйлеровыми циклами в G*. В силу этого дальше мы будем заниматься только эйлеровыми циклами.

Пример гамильтонова пути в графе и графа, в котором такого пути не существует, показан на рис. (а), (б) соответственно.

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

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

Нахождение кратчайших путей в графе

Начальные понятия

Будем рассматривать ориентированные графы G = V, E, дугам которых приписаны веса. Это означает, что каждой дуге u, v E поставлено в соответствие некоторое вещественное число a (u, v), называемое весом данной дуги.

Полагаем, кроме того, a (u, v) = ╔ , если u -a v.

Если последовательность вершин v0, v1,..., vp определяет путь в G, то его длина определяется как сумма

(Отметим, что если в произвольном графе мы примем вес каждой дуги равным единице, то мы получим обычное определение длины пути как числа дуг; длина пути равна 0 при p= 0).

Нас будет интересовать нахождение кратчайшего пути между фиксированными вершинами s, t V. Длину такого кратчайшего пути мы будем обозначать d (s, t) и называть расстоянием от s до t (расстояние, определенное таким образом, может быть отрицательным). Если не существует ни одного пути из s в t, то полагаем d (s, t) = ╔ . Если каждый контур нашего графа имеет положительную длину, то кратчайший путь будет всегда элементарным путем, т.е. в последовательности v1,..., vp не будет повторов.

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

Можно дать много практических интерпретаций задачи о кратчайших путях. Например, вершины могут соответствовать городам, а каждая дуга - некоторому пути, длина которого представлена весом дуги. Мы ищем затем кратчайшие пути между городами. Вес дуги также может соответствовать стоимости (или времени) передачи информации между вершинами. В таком случае мы ищем самый дешевый (или самый скорый) путь передачи информации. Еще одну ситуацию получаем, когда вес дуги u, v равен вероятности p(u, v) безаварийной работы канала передачи информации. Если предположить, что аварии каналов не зависят друг от друга, то вероятность исправности пути передачи информации равна произведению вероятностей составляющих его дуг. Задачу нахождения наиболее надежного пути легко можно свести к задаче о кратчайшем пути, заменяя веса p(u, v) на a (u, v) = - log p(u, v).

Сначала рассмотрим алгоритмы нахождения расстояния между вершинами, а не самих путей. Однако, зная расстояние, мы можем при условии положительной длины всех контуров легко определить кратчайшие пути. Для этого достаточно отметить, что для произвольных s, t  V (s ╧ t) существует вершина v, такая что

d (s, t) = d (s, v) + a (v, t).

Действительно, таким свойством обладает предпоследняя вершина произвольного кратчайшего пути из s в t.

Далее мы можем найти вершину u, для которой d (s, v) = d (s, u) + a (u, v), и т.д.

Из положительности длины всех контуров легко следует, что созданная таким образом последовательность t, v, u, ... не сожержит повторений и оканчивается вершиной s.

Очевидно, что она определяет (при обращении очередности) кратчайший путь из s в t.

Кратчайшие пути от фиксированной вершины

Большинство известных алгоритмов нахождения расстояния между двумя фиксированными вершинами s и t опирается на действия, которые в общих чертах можно представить следующим образом: при данной матрице весов дуг A[u, v], u, v  V, вычисляются некоторые верхние ограничения D[v] на расстояния от s до всех вершин v  V. Каждый раз, когда мы устанавливаем, что

D[u] + A[u, v] < D[v],

оценку D[v] улучшаем: D[v] = D[u] + A[u, v].

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

Легко можно показать, что значение каждой из переменных D[v] равно тогда d (s, v) - расстоянию от s до v.

Заметим, что для того чтобы определить расстояние от s до t, мы вычисляем здесь расстояния от s до всех вершин графа.

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

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

Пути в бесконтурном графе

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

Лемма. В произвольном бесконтурном графе вершины можно перенумеровать так, что каждая дуга будет иметь вид vi, vj, где i < j.

Пример такой нумерации приведен на рисунке.

Кратчайшие пути между всеми парами вершин, транзитивное замыкание отношения

Очевидно, что задачу определения расстояния между всеми парами вершин можно решить, используя n раз (поочередно для каждой вершины) один из ранее изложенных методов нахождения расстояний от фиксированной вершины. Таким образом, мы получаем алгоритм со сложностью O(n4) (при использовании метода Форда - Беллмана) или O(n3) для бесконтурных графов или неотрицательных весов. Однако оказывается, что в общем случае n-кратное использование метода Форда - Беллмана не является наилучшим методом. Рассмотрим два более эффективных метода.

Для этого рассмотрим ориентированный граф G =  V, E, где V = {v1, ..., vn}, и предположим, что A = [aij] есть матрица весов (aij = a(vi, vj)). Обозначив через dij(m) длину кратчайшего пути из vi  в vj, содержащего не более m дуг, получаем следующие очевидные уравнения:

(1)

dij(m+1) = min{dik(m) + akj : 1<k<n}. (2)

Отметим, что последнее уравнение обнаруживает некоторое сходство с определением произведения двух квадратных матриц. Если операцию min трактовать как «сумму» , операцию «+» - как «произведение» , то матрица [dij(m+1)] является «произведением» матриц [dij(m)] и A = [aij]. Обозначим такое «произведение» двух матриц A и B через A*B и отметим, что для этой операции единичным элементом служит матрица

.

Из уравнений (1) и (2) теперь легко следует, что [dij(0) = U] и

dij(m) = ((...((A*A)*A)...)*A) (m 1). (3)

Возможен один из следующих случаев:

(1) dij(n-1) = dij(n) и в результате dij(m) = dij(n-1) для каждого m   n. Тогда очевидно dij(n-1) = d(vi, vj).

(2) dij(n-1) ╧ dij(n) . Это означает, что существует контур отрицательной длины.

Произведение A*B двух матриц размерности n ╢ n можно вычислить за время O(n3) (n сложений и n - 1 сравнений на каждый из n2 элементов произведения A*B). Следовательно, матрицу [dij(n-1)] и тем самым расстояние между всеми парами вершин можно вычислить за время O(n4).

Виды графов.

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

ГРАФЫ И ОРИЕНТИРОВАННЫЕ ГРАФЫ (АНАЛОГИИ И ОТЛИЧИЯ)