7. Укладка графа. Плоские и планарные графы.

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

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

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

            Пример плоского графа приведен на рис. слева. Изоморфный ему полный граф К₄ (на рис. справа), укладываемый на плоскости, имеет два пересекающихся ребра, поэтому граф К₄  не является плоским  он только планарный.

II. Задача о кратчайшей цепи

1. Постановка задачи

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

Формулировка задачи имеет следующий вид:

задана сеть - G  {N, A}; для всех дуг из A определена обобщенная стоимость c_ij прохождения единицы потока по дуге, которая в реальных задачах в зависимости от выбранного критерия оптимальности может быть либо временем выполнения каких-либо процессов в моделируемом объекте, либо расстоянием, либо величиной, имеющей денежное выражение и связанной со стоимостью. Для фиктивных дуг, задающих только последовательность узлов, c_ij  0, для пары узлов i и j, не соединенных дугой, c_ij  .

Интенсивности истока и стока: d_s  1, d_r  -1; для остальных узлов сети

d  0.

Требуется найти цепь [s, ..., r] с оптимальной (минимальной или максимальной) суммарной обобщенной стоимостью c_sr всех входящих в нее дуг.

Эта задача может быть представлена, как задача дискретного программирования:

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

2. Алгоритм решения (алгоритм Дейкстры)

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

Начальное заполнение:

Источнику присвоить постоянную пометку 0. Остальным узлам i присвоить временные пометки, численно равные элементам csi матрицы обобщенной стоимости дуг из источника в узел i. Для узлов, не являющихся конечными для дуг, идущих из источника, временные пометки равны . Ls  0; Ii  csi, i N, i s.

Начальное заполнение производится один раз перед итеративной процедурой, которая состоит не более чем из n-1 итерации (где n - число узлов сети) и продолжается до тех пор, пока сток не будет помечен постоянной пометкой. Каждая итерация выполняется по одному и тому же алгоритму и состоит из двух шагов.

Итерация:		Шаг 1:		Для всех узлов i с временными пометками Ii вычислить их новое значение Ii как наименьшее из старого значения пометки и суммы полученной на предыдущей итерации постоянной пометки Lj с обобщенной стоимостью дуги [ji]. Ii ’  min {Ii; Lj  сji}; j: Lj  {Li} (3)
		Шаг 2:		Узлу, временная пометка которого является наименьшей из всех еще существующих временных пометок, присвоить постоянную пометку, численно равную этой временной. Lj  Ij; j: Ij  {Ii} (4) Если помеченным оказывается сток (j  r), прямой ход алгоритма Дейкстры закончен.

Величина постоянной пометки стока равна обобщенной стоимости неизвестной пока еще оптимальной цепи. Сама цепь определяется во второй части алгоритма Дейкстры и состоит из дуг, для каждой из которых разность между значениями постоянных пометок ее концевых узлов, равна длине (обобщенной стоимости) этой дуги. Иными словами, условие, при выполнении которого узлы i и j принадлежат кратчайшей цепи [s, ..., i, j, ..., r] может быть записано следующим образом:

L_j - L_i - c_ij  0. (5)

Это соотношение можно использовать рекурсивно, двигаясь от узла r к узлу s.

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

Начальное заполнение:

Рассматриваются только узлы, имеющие постоянные по метки. Сток включается в оптимальную цепь.

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

Итерация:		Шаг 1:		Для всех узлов i с постоянными пометками Li вычислить величину i  Lj - Li - cij, где Lj - постоянная пометка узла j, последним включенного в оптимальную цепь.
		Шаг 2:		Включить в оптимальную цепь узел, удовлетворяющий условию (5): i ’  0. Если это исток (i’ s), обратный ход алгоритма Дейкстры закончен.

Совершенно аналогичным методом может быть решена задача о цепи максимальной длины, однако при этом в прямом ходе алгоритма Дейкстры в выражениях (3) и (4) необходимо min {...} заменить на max {...} (от тех же выражений) и в начальном заполнении прямого хода алгоритма Дейкстры вместо необходимо ввести - .

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