Итерационные алгоритмы разрезания графа на куски

Лекция 7

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

Вспомним, что матрица смежности для графа G(X,E), имеющего n вершин – это матрица R=||r_ij||_n*n, элементы которой соответствуют числу ребер, соединяющих вершину x_i с вершиной x_j.

Т.к. матрица смежности полностью описывает граф, то разрезание графа G на lкусков G₁, G₂, … , G_l эквивалентно разбиению матрицы смежности R графа G на l клеток (подматриц). Например, граф задан матрицей смежности R.Граф разрезан на 2 куска - G₁={е₁,е₂,е₃}иG₂={е₄,е₅,е₆,е₇}.

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

За критерий оптимальности можно брать минимум числа ребер между кусками (см. формулу(3.2) лекции 3)

(7.1)

либо максимум числа ребер внутри кусков

	(7.2)
или DG → max	(7.3)

(Согласно материалу лекции 3 множество U_ij определяет подмножество ребер U_ij ≤ U, попадающих в разрез между кусками G_i и G_j графа G,а множество U_ii определяет подмножество ребер, т.е. кол-во связей внутри куска G_i),

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

Таким образом, в первом куске пусть будет множество Е_i вершин, а во втором ØЕ_i = Е \ Е_i.

Тогда множество ребер разобьем на три класса:

1) внутренние ребра, лежащие в куске;G_i;

2) внешние ребра, лежащие в куске ØG_i;

3) соединяющие ребра между кусками G_i иØG_i.

Число внутренних ребер куска G_i равно

(7.4)

Где Sr(e_i) - сумма локальных степеней вершин куска G_i, K_iØi - число соединительных ребер кусков G_i и ØG_i

Число внешних ребер, которые являются внутренними для куска ØG_i равно

(7.5)

Для каждой вершины e_k введем число связности вершины (разность кол-ва внешних и внутренних связей k-го элемента)

Где:

- r_k(G_i) -число ребер, соединяющих вершину e_k с вершинами куска G_i (k-й элемент, i-й кусок);

- r_k(ØG_i) -число ребер, соединяющих вершину e_k с вершинами куска ØG_i.

Обозначим:

- a_k - число связности для вершин e_kÎE_i;

- Øa_k - число связности для вершин e_kÎØE_i.

Поясним понятие связности на примере графа G, разбитого на 2 части G₁ и G₂, приведенного на рис. 7.1. Тогда числа связности для вершин G₁ определяется следующим образом:

a(x₁)=r₁(G₂)-r₁(G₁)=1-2=-1;

a(x₂)=r₂(G₂)-r₂(G₁)=2-2=0;

a(x₃)=r₃(G₂)-r₃(G₁)=3-2=1;

Числа связности для вершин G₂:

a(x₄)=r₄(G₁)-r₄(G₂)=1-3=-2

a(x₅)=r₅(G₁)-r₅(G₂)=2-2=0;

a(x₆)=r₆(G₁)-r₆(G₂)=0-2=-2;

a(x₇)=r₇(G₁)-r₇(G₂)=3-1=2;

Очевидно, что число связности может быть положительным, отрицательным или равным нулю. Физический смысл числа связности следующий. Например, a(x₁)=-1означает, что при перестановке вершины x₁изG₁вG₂число ребер в сечении увеличится на 1. Значение a(x₂)=0говорит о том, что перестановка вершины x₂ изG₁вG₂ оставит без изменения число соединительных ребер.

Рассмотрим теперь итерационный алгоритм с использованием матрицы смежности. Он основан на теореме:

Перестановка двух произвольных вершин e_kÎE_i и e_qÎØE_i приводит к уменьшению числа соединительных ребер между кусками в случаях:

A) если e_k и e_q не смежные, и выполняется:

Б) если e_k и e_q смежные, и выполняется:

В общем случае

Докажем утверждение А). Очевидно, что перестановка целесообразна, если DK_iØi=K_iØi-K^’_iØi>0 (например, было 5 внешних реберных соединений, стало 2), где K_iØiиK^’_iØi- числа внешнего реберного соединения до и после перестановки и

Тогда

Аналогично доказывается утверждение Б).

Теперь опишем суть алгоритма

1. Разрезание начинаем выделением в матрицеR двух произвольных подматриц Q и ØQ. Порядок подматрицы Qравен числу вершин первого выделяемого куска, а порядок ØQ - числу всех оставшихся вершин.

2. Перестановка элементов из одного куска в другой будет соответствовать перестановке строк и столбцов матрицы R.

3. Матрица смежности графа, приведенного на рис. 7.1, имеет вид:

Разрежем эту матрицу на 2 подматрицы по 3 и 4 элемента. Сумма всех элементов закрашенных подматриц, деленная на два, соответствует числу внутренних ребер кусков, а элементы, не принадлежащие главной диагонали, определяют соединяющие ребра между кусками. Тогда

	(7.13)
	(7.14)

Для каждой строки матрицы смежности подсчитываем a_k или Øa_q в зависимости от того, к какой подматрице принадлежит данная строка. Запишем эти числа справа матрицы.

4. Построим матрицу В =||b_kq||_ni*(n-ni),в которой строки определяются вершинами e_kÎE_i, а столбцы вершинами e_qÎØE_i. На пресечении k– ой строки и q – го столбца элемент

гдеr_kq - элемент матрицы R.

Элемент b_kq характеризует изменение числа соединительных ребер между кусками G_i и ØG_i при перестановке вершинe_kÎG_i и e_qÎØG_i.

Выбираем для перестановки пару с наибольшим положительным b_kq.

5. Осуществляется перестановка строк и столбцов k и q в матрице R и процесс снова повторяется пока в матрице Bвсе элементы не станут со знаком «-».

6. Исключается из графа Gкусок G₁, соответствующий подматрице Q₁ и процесс повторяется для матрицы ØQ₁ с выделением куска с n2 элементами и т. д.

Пример.

Задана матрица смежности R₀ графа G. Надо разрезать граф с рис. 7.1 на 3куска по 5, 3, 4 вершин

Согласно п.1 алгоритма выделяем в матрице R₀ две подматрицы, в одной из которых 5 строк, т.е. включаем в первый кусок элементы e₁, e₂, e₃, e₄, e₅ (т.к. разбиваем на куски по 5, 3, 4 вершин), в оставшейся части 7строк.

Согласно п.3 алгоритма для каждой строки матрицы смежности по формулам (7.13) и (7.14) подсчитываем a_k и Øa_k и записываем в столбец справа от матрицы смежности. Число соединительных ребер между G₁ и ØG₁ (число внешних связей) для этого разбиения K₁=14 (сумма элементов одной из невыделенных частей)

Согласно п.4 алгоритма по формуле (7.15) построим матрицу В. Для примера:

b₁₆= a₁+Øa₆-2r₁₆=4+1-2*0=5

b₄₁₁= a₄+Øa₁₁-2r₄₁₁=1-4-2*0=-3

Согласно п.4 алгоритма выбираем для перестановки пару с наибольшим положительным b₁₆=5, т.е. из B₀ выбираем для перестановки элементы e₁ и e₆.

Согласно п.5 алгоритма, в матрице R₀ переставляем строчки и столбцы, соответствующие e₁ и e_6, и смотрим, как изменится число внешних связей между кусками от этой перестановки.

Получается матрица R₁

Число соединительных ребер между G₁ и ØG₁ (число внешних связей) для этого разбиения K₂=9 (сумма элементов выделенной части).

Число соединительных ребер между G₁ и ØG₁снизилось с 14 до 9, т.е. перестановка элементов e₁ и e₆ дает уменьшение числа соединительных ребер. Переход к п.4.

Согласно п.4 по формуле (7.15) строим матрицу В₁:

Согласно п.4 алгоритма выбираем для перестановки пару с наибольшим положительным b₃₁₀=5, т.е. из B₁ выбираем для перестановки элементы e₃ и e₁₀.

В матрице R₁ переставляем строчки и столбцы, соответствующие e₃ и e₁₀.

Число соединительных ребер между G₁ и ØG₁ снизилось до 4.

Согласно п.5 алгоритма т.к. в R^’₂ все значения α_ки α_qотрицательные, то в В₂ не будет положительных элементов, и процесс выделения подграфа G₁закончен, 1-й кусок построен:

E₁={e₆,e₂,e₁₀,e₄,e₅}

Строим кусок E₂, содержащий 3 вершиныВключаем в него элементы e₁, e₇, e₈.Согласно п.6 алгоритма, исключив из R^’₂ кусок, соответствующий G1, получим:

Строим матрицу B^’’₀:

Выбираем max b₈₉=6. Из B^’’₀ выбираем для перестановки элементы e₈ и e₉. В матрице R^’’₀ переставляем строчки и столбцы, соответствующие e₈ и e₉:

Число соединительных ребер между G₂и ØG₂снизилось с 7 до 1, т.е. перестановка элементов e₈ и e₉ дает уменьшение числа соединительных ребер.

Т.к. все α_ки α_q отрицательные, то в В^’’₁ все члены будут со знаком «–» и перестановки не может быть. Тогда

E₂={e₁,e₇,e₉}, E₃={e₈,e₃,e₁₁,e₁₂}.

Число соединительных ребер между кусками =5.

Число внутренних ребер равно 9+5+7=21.

∆(G)=21/5=4,2.

Результат разбиения приведен на рис. 7.2.

Материал из лекции 3

Пусть граф G(E,U) разбит на l кусков G₁, G₂,…,G_l. Тогда множество ребер U графа G можно представить в виде:

(3.3)

где

где:

- U_i– подмножество всех ребер, инцидентных вершинам E_i куска G_i;

- U_i,i – подмножество ребер, соединяющих подмножество вершин E_i куска G_i между собой;

- U_i,j – подмножество ребер, соединяющих куски G_i и G_j.

Назовем коэффициентом разбиения ∆(G) графа Gотношение суммарного числа внутренних ребер (ребер подмножеств U_i,i )к суммарному числу соединяющих ребер U_i,j.

(3.5)

Коэффициент ∆(G) служит для оценки разбиения графа G на куски. Для графа на рис. 3.1 ∆(G)=5/12.

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

Оглавление

Лекция 7. 1

Итерационные алгоритмы разрезания графа на куски. 1