Размещено на http://www.allbest.ru/

Лекция

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

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

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

(7.1)

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

(7.2)

или G > 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)

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

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

(7.5)

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

_k= r_k (G_i) - r_k (G_i), если e_kE_i (7.6)

r_k (G_i) - r_k (G_i), если e_kE_i(7.7)

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

Обозначим: _k - число связности для вершин e_kE_i; _k - число связности для вершин e_kE_i.

Поясним понятие связности на примере графа G, разбитого на 2 части G₁ и G₂, приведенного на рис. 7.1

Тогда числа связности для вершин G₁ определяется следующим образом:

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

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

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

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

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

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

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

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

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

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

Перестановка двух произвольных вершин e_kE_i и e_qE_i приводит к уменьшению числа соединительных ребер между кусками в случаях:

A) если e_k и e_q не смежные, и выполняется: _k+_q> 0 (7.7)

Б) если e_k и e_q смежные, и выполняется: _k+ _q >2 (7.8)

В общем случае _k+ _q >2r_kq (7.9)

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

K_ii=r_k (G_i) + r_q (G_i) (7.10) K'_ii=r_k (G_i) + r_q (G_i) (7.11)

Тогда

K_ii=r_k (G_i) +r_q (G_i) - _k (G_i) - r_q (G_i) = _k+_q>0 (7.12)

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

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

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

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

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

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

(7.13)

(7.14)

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

4. Построим матрицу В =||b_kq||_{ni* (n-ni),} в которой строки определяются вершинами e_kE_i, а столбцы вершинами e_qE_i. На пресечении k - ой строки и q - го столбца элемент

b_kq= _k+_q-2r_kq (7.15)

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

Элемент b_kq характеризует изменение числа соединительных ребер между кусками G_i и G_i при перестановке вершин e_kG_i и e_qG_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) подсчитываем _k и _k и записываем в столбец справа от матрицы смежности. Число соединительных ребер между G₁ и G₁ (число внешних связей) для этого разбиения K₁=14 (сумма элементов одной из невыделенных частей)

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

b₁₆= ₁+₆-2r₁₆=4+1-2*0=5, b₄₁₁= ₄+₁₁-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₁=U_1,1U_1,2…U_1,l

U₂=U_2,1U_2,2…U_2,l

…… ………………….

U_i=U_i,1U_i,2… U_i,l

… …………………….

U₁=U_l,1 U_l,2…U_l,l (3.4)

где:

- 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).

Размещено на Allbest.ru