3485 РАЗБИЕНИЕ ДИСКРЕТНОГО КОНЕЧНОГО МНОЖЕСТВА ЭЛЕМЕНТОВ НА ОСНОВЕ КРАТЧАЙШЕГО ОСТОВНОГО ДЕРЕВА

Цель работы

 

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

 

Краткие теоретические сведения

 

1. Задача дискретной математики о разбиении множества

Первичные данные, сведенные в таблицу ”Объект-свойство”, часто бывают необозримыми, и непосредственно формирование отношений между объектами практически невозможно. Определение связей между объектами сильно облегчается, если исходное множество  всех объектов удается описать более кратким способом, чем перечисление всех объектов со всеми  их свойствами. Наиболее распространенный способ сокращения описания связан с разделением множества М объектов таблицы на небольшое число групп, связанных друг с другом каким-нибудь закономерным свойством. Обычно в качестве такого свойства используется ”похожесть”  объектов одной группы. Закономерности ”групповой похожести ”позволяют  намного сократить описание таблиц  ”Объект-свойство” при малой потере информации. Вместо перечисления всех объектов можно дать список “типичных” или “эталонных” представителей групп, указать номера (имена) объектов, входящих в состав каждой группы. При небольшом числе групп описание  данных становится обозримым и легко интерпретируемым.

В  работе такая группировка делается с помощью  построения кратчайшего остовного дерева. Алгоритмы  разбиения отличаются друг от друга процедурой группировки и критерием качества разбиения множества. Введем некоторые обозначения. Пусть данные таблицы Т, подлежащие разбиению, содержат М объектов (а1,а2,..,аM) ,имеющих N свойств(x1,x2,…,xN), и требуется выявить К классов(S1,S2,…,SK), 1<K<N-1. Различные варианты разбиения объектов на К классов будем сравнивать по некоторому критерию качества разбиения F. Если свойства объекта представить себе в виде координат метрического пространства, то каждый объект со своими значениями свойств будет отображаться в некоторую точку этого пространства. Два объекта с почти одинаковыми значениями свойств отобразятся в две близкие точки, а объекты с сильно отличающимися  свойствами будут представлены далекими друг от  друга точками. Если имеются сгустки точек, отделенные  промежутками от других сгустков, то их целесообразно выделить в отдельные структурные части множества - классы. В дальнейшем можно аппроксимировать сгустки каким-либо известным законом распределения. Можно  также указать границы класса, описав  их геометрические параметры (например, задав  систему уравнений разделяющих гиперплоскостей). По этим описаниям можно узнать, какому классу принадлежит любой объект как изучаемой конечной выборки, так и любого нового объекта из генеральной совокупности.

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

 

2. Графовое  представление  связей между  объектами

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

Связи могут быть «направленными», как, например, в генеалогическом дереве или  в сети дорог с односторонним движением. В соответствии с этим в теории графов выделяют два основных типа графов: ориентированные и неориентированные.

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

Матрицей смежности ориентированного помеченного графа с n вершинами называется матрица A=[aij], i,j=1,2…n, в которой:

aij m , если существует m ребер (xi, xj ),

0, если вершины xi , xj не связаны ребром (xi, xj).

Матрица смежности однозначно определяет структуру графа.

Граф называется взвешенным, если с каждым его ребром сопоставлено число. Простой взвешенный граф может быть представлен своей     матрицей весов W=[wij], где wij – вес ребра, соединяющего вершины             i, j =1,2..n. Веса несуществующих ребер полагают равными ¥. Матрица весов является простым обобщением матрицы смежности.

При описании графа списком его ребер каждое ребро представляется парой его вершин. Это представление можно реализовать двумя массивами r=(r1, r2,…, rn) и t=(t1, t2,…, tn), где n - количество вершин в графе. Ребро Li,j графа выходит из вершины ri и входит в вершину tj. Здесь L - характеристика ребра, например вес ребра.

Деревом называется неориентированный граф, не имеющий циклов и изолированных вершин. Минимальным (кратчайшим) остовным деревом называется остовное дерево с минимальным общим весом его ребер.

 

3.  Построение кратчайшего остовного дерева

3.1.    Алгоритм Прима в табличной форме

По заданному графу заполняется матрица весов W(N, N). Веса несуществующих ребер предполагаются сколь угодно большими. Образуется массив P(N) меток вершин графа (столбцов матрицы весов). Алгоритм решения задачи заключается в последовательном заполнении массива меток столбцов и состоит из следующих этапов.

Предварительный этап. Обнуляется массив P(N) меток столбцов таблицы. Произвольно выбранному столбцу присваивается значение метки, равной его номеру.

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

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

Структурограмма алгоритма решения задачи о минимальном остовном дереве графа методом Прима, заданного матрицей весов W(N, N), показана на рис.1.

 

3.2. Алгоритм Краскала определения минимального остовного дерева

Для использования алгоритма Краскала применяется список ребер графа. Метод состоит в последовательном подключении к остовному дереву ребер с минимальным весом и заключается в следующем.

Предварительный этап. Список ребер сортируется в порядке  возрастания весов. Ребро, имеющее минимальный вес (первое в упорядоченном списке), включается в искомый остов.

Этап, повторяющийся (N-1) раз (общий этап). Очередное ребро в списке включается в остов, если оно не образует цикл. Если ребро образует цикл с уже включенными в остов ребрами, то оно вычеркивается из списка и просматривается следующее по списку ребро.

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

 

 

 

 

 

I=1;N

 

P(I)=0

 

O(K)=K;Q=0

 

I=1;N-1

 

H=¥

 

L=1;N

 

 

P(L)¹0

Да


Нет

 

 

 

J=1;N

 

 

 

P(J)=0

Да


Нет

 

 

W(L,J)¹¥

Да

 

Нет

 

 

 

W(L,

Да

J)<H

Нет

 

 

 

H=W(L,J)

 

 

 

X=L;Y=J

 

Q=Q+H; P(Y)=X; W(Y, X)=¥

 

I=1;N

 

I¹K

Да

 

Нет

 

Вывод: «вершина», I, «связана с вершиной», P(I)

 

Вывод: «вес остова=», Q

 

Рис.1

 

3.3. Пример

Известна стоимость обеспечения связи между источником и потребителями информации (рис. 2).

 

 

 

 

Рис. 2

Нужно синтезировать топологию  сети, обеспечивающей минимальную стоимость. Требуется определить методами Краскала и Прима минимальное остовное дерево графа G(5, 10), представленного на рис. 2.

Метод Прима. Матрица весов, получаемая после предварительного этапа алгоритма, представлена в табл. 1, где в качестве начальной выбрана

вершина 3.

Таблица 1

_    _     3 _    _

1    2     3    4    5

1              5    10   8   9

2       5            3    7   1

3       10   3           2   6

4       8     7     2         4

5       9     1     6    4

 

Задачей общего этапа является помечивание всех столбцов таблицы. В 3-й строке находится минимальный элемент w34=2. 4-й столбец, содержащий минимальный элемент, помечается номером строки, где этот элемент находится. Элементу w43 присваивается сколь угодно большое значение. В непомеченных столбцах 3-й и 4-й строк находится минимальный элемент w32=3. 2-й столбец, его содержащий, помечается номером 3-й строки. Элементу w23 присваивается сколь угодно большое значение. После этого шага матрица имеет вид, представленный в табл. 2.

Таблица 2

_     3 3 3 _

1     2    3     4    5

1              5    10   8   9

2       5                  7   1

3       10   3           2   6

4       8     7                4

5       9     1     6    4

 

В непомеченных столбцах 2, 3 и 4-й строк находится минимальный элемент w25 =1. 5-й столбец помечается номером 2-й строки, где находится минимальный элемент. Элементу w52 присваивается сколь угодно большое значение. На очередном шаге общего этапа в непомеченных столбцах 2, 3, 4 и 5-й строк находится минимальный элемент w21=5. 1-й столбец помечается номером 2, элементу w12 присваивается сколь угодно большое значение. Матрица после этого шага имеет вид, представленный в табл. 3.

Таблица 3

2 3 3 3 2

1    2    3    4    5

1                10   8    9

2     5                 7   1

3    10   3           2   6

4    8     7                4

5    9           6    4

 

Все столбцы таблицы помечены, общий этап закончен.

На заключительном этапе выписывается последовательность вершин, ребра между которыми включаются в минимальное остовное дерево. Это ребра, соединяющие вершины 1-2, 2-3, 3-4, 2-5.

Вес остовного дерева равен 5+3+2+1=11. Полученное остовное дерево показано на рис. 3.

 

3

5

 

1

 

2

 

 

 

Рис. 3