2018-02-14
335
Граф - множество вершин и ребер. G = {{X}, {U}}. Uij = (Xi, Xj). Ребро Uij инцидентно вершинам Xi и Xj, верно и обратное - вершины Xi и Xj инцидентны ребру Uij. Две вершины называются смежными, если существует ребро, инцидентное данным вершинам. Два ребра называются смежными, если существует вершина, инцидентная этим двум ребрам. Если существует несколько ребер, инцидентных некоторым двум вершинам, то такие ребра называются кратными, а сам граф - мультиграфом. Наибольшую кратность называют мультичислом. Ребро вида (Xi, Xi) называют петлей. Ориентированное ребро - дуга.
Матрица смежности R = ||rij||nxn (n - число вершин в графе), где элемент матрицы - кратность соответствующего ребра. Матрица - симметричная.
Локальная степень вершины - количество ребер, инцидентных данной вершине.
Задача: разрезать граф G = {X[n], {U}} на l кусков (G1[n1],..., Gl[nl]): n1 +... + nl = n.
Критерий: минимизация числа связей между кусками.
Идея: в каждый кусок нужно помещать вершины с наибольшим числом связей между собой.
Алгоритм:
1. Строим матрицу смежности. Подсчитываем локальную степень каждой вершины.
2. Находим вершину (строку в матрице) с максимальной локальной степенью и в этой строке отыскиваем максимальный элемент (ребро), не являющийся петлей. Две вершины, инцидентные данному (кратному) ребру, помещаются в текущий кусок.
3. Поэлементно складываем строки, соответствующие двум выбранным вершинам. Ребра внутри куска удаляются. В полученной строке находим максимальный элемент, и повторяем процедуру сложения с еще одной вершиной. Процесс повторяется, пока не будет достигнуто ограничение на количество вершин в одном куске.
4. Из матрицы вычеркиваются строки и столбцы, соответствующие вершинам, уже помещенным в кусок. Заполняем новый кусок - переходим к п. 1. Если размерность матрицы не превышает ограничение на размер куска, то оставшиеся вершины помещаются в кусок без повторения процесса - и на этом алгоритм заканчивается.
