Разрезание (разбиение) графа

Пусть задан сложный граф:

Совокупность частей B(G) называют разбиением графа G(X,U), если для любого G_iÎ B(G) G_i¹Æ iÎI (определяет число разбиений), т.е. для любого G_i G_jÎ B(G) [G_i∩G_j¹Æ, т.е. Х_i∩Х_j=Æ и U_i∩U_j=U_ij или U_i∩U_j=Æ]. Иначе совокупность B(G)={G₁, G₂,..., G_n}, где n – мощность │I│, является разрезанием графа G, если любая часть из этой совокупности непустая и если для любых двух частей из B(G) пересечение множества вершин пусто, а пересечение рёбер может быть непустым, а также, если пересечение всех частей в точности равно графу G.

25. Алгоритмы разбиения графа. Последовательный алгоритм.

Разбиение графа на подграфы (англ. Graph partition) (иногда в литературе также употребляется термин разрезание графа[1]) — представление исходного графа в виде множества подмножеств вершин по определенным правилам. Обычно по условию задачи требуется, чтобы , то есть все вершины исходного графа должны быть распределены по подмножествам, причем . Обычно также дополнительно вводится требование ортогональности разбиения: , то есть одна и та же вершина не может входить в состав различных подмножеств. Иногда из множества возможных разбиений требуется выбрать одно, удовлетворяющее ограничениям и являющееся оптимальным (либо субоптимальным) по обозначенному критерию, либо доказать, что искомое разбиение не существует (ограничения противоречивы). Задача разбиения графа относится к классу NP-полных, верхняя оценка числа разбиений определяется числом Белла, однако при этом обычно не все возможные разбиения являются корректными (не нарушают ограничений), то есть оценка является завышенной. При значениях числа вершин графа более 15—20 получение оптимальных разбиений как правило невозможно за приемлемое время (иногда для этого используется метод ветвей и границ), поэтому на практике ограничиваются субоптимальными решениями, полученными с использованием эвристических алгоритмов.

Последовательный алгоритм разрезания графа.

Пусть задан граф G(X,U) и требуется разрезать его на l кусков {G₁, G₂,..., G_l}, с числом вершин n₁,n₂,..., n_l.

Работу начинают с формирования первого куска: в графе G определяется вершина х_i с наименьшей локальной степе­нью - min _i, если таких вер­шин несколько, то предпочтение отдаётся той вершине, которая имеет большее число кратных рёбер. С этой вер­шиныначинается построение. Для этого в граф G₁ первоначально включается x_i и все вершины смеж­ные с ней. Обозначим это множество через Г_xi. Если мощность Г_xi равна заданной мощности n₁, то кусок сформирован. Если это число больше, чем n₁ , то удаляются лишние вершины, связанные с оставшимися вер­шинами меньшим числом рёбер. В случае, когда мощность Г_xi меньше n₁ , то добавляется вершина по формуле:

minx_i)=x_j)- a_j, где

a_j- число рёбер соединяющих вершины х_j со всеми, не выбранными вершинами. Строим множество вершин Г_xj смежных с х_j и процесс выборки вершин повторяется. Образованный подграф G₁ исключается из исходного графа и получаем граф, который подлежит дальнейшему разрезанию.

26. Итерационный алгоритм разбиения графа на части.

Итерационный алгоритм разрезания графа.

Пусть задан граф G(X,U) и подмножество вершин Q≤X. Требуется найти такое разбиение графа В(G) на l одинаковых частей {G₁, G₂,..., G _l }, чтобы суммарное число соединяющих рёбер было минимальным.

Перед началом работы распределяются вершины из множества Q, мощностью равной q. Формирование начинается с вершины х _ε , где εÎ{1,2,.., q}, т.е. х _ε оприорно считаем входящим в множество вершин Х₁ÎG(Х₁,U₁). Составление частей разбиения будем вести по уровням. Вершина х _ε – первый уровень. Для определения вершины следующего уровня, т.е. второй вершины, которую необходимо поместить в граф G₁, формируется образ Г_{x ε} , т.е. строим подмножество смежных рёбер.

Введём понятие относительного веса:

x_i)=x_j)- a_jк ,

где x_j)- локальная степень вершины;

a_jк- число рёбер, соединяющих к-тую вершину из подмножества Х₁ с рассматриваемой вершиной.

Из подмножества Г_{x ε} выбирается вершина с минимальной x_i).

Выбранная вершина является вершиной второго уровня, т.е. на втором уровне будет  х _ε,x_j). Далее формируется множество Г_{х ε} ∩ Г_хj и для каждой вершины из этого множества рассчитывают x_i). Далее выбирается минимальное значение x_i) и алгоритм повторяется до тех пор, пока мощность множества Х₁ не станет равна заданной. Полученная часть удаляется из графа G. Формирование следующих частей ведётся аналогично.

27. Раскраска графа.

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