35

4.3. АЛГОРИТМ ПОСТРОЕНИЯ МАТРИЦЫ МЕТРИКИ ГРАФА

Введём обозначения, которые будут использоваться в алгоритме построения матрицы метрики (матрицы отклонений):

Граф L=( X,U );

R - матрица смежности заданного графа L; E – единичная матрица;

М - матрица метрики;

Матрица смежности R графа L c элементами логического типа:

ì 1, если вершины xi, xj – смежны;

ri,j = í

î0, в противном случае

S ¾ матрица S = R + E.

4.3.1. Описание алгоритма

Значения элементов mi,j матрицы M определяются за несколько итераций по результатам последовательного возведения матрицы S=(E+R) в степень p = 1,k до получения устойчивой матрицы Sk , где k - степень устойчивой матрицы Sk. Матрица Sk называется устойчивой, если

Sk = Sk +1 .

Шаг 1. Задаём матрицу метрики M = (mi,j)n ×n . Размерность матрицы М равна размерности матрицы R. Все элементы mi,j матрицы М не определены.

Шаг 2. Начальное значение степени k матрицы S равно «1»: - k=1. " mi,i присваиваем значение « 0 », на основании 1 – ой аксиомы

Фрише.

36

Шаг 3. Всем элементам mi,j , значения которых не определены, присвоить значение степени k, если соответствующие им элементы матрицы Sk ¹ 0. (Значения элементов mi,j определяются только один раз).

Шаг 4. Проверяем, в матрице M имеются элементы mi,j , значения которых ещё не определены?

Если такие элементы имеются, то переходим к шагу 4; в противном случае – к шагу 7.

Шаг 5. Повышаем степень k матрицы R: k = k+1.

Шаг 6. Проверяем, является ли матрица Rk-1 устойчивой. Если матрица Rk-1 - неустойчивая, то переходим к шагу 3. Иначе – переходим к шагу 7.

Шаг 7. Всем элементам mi,j матрицы M, значения которых остались неопределенными, присваиваем значение ¥ (бесконечность).

Шаг 8. Матрица метрики М=(mi,j) построена. Конец алгоритма.

Примечание: Элементам mi,j значения присваиваются только один раз. Следовательно, если значение элемента mi,j уже определёно, то оно больше не меняется.

Радиус графа определяется по матрице метрики следующим способом: в каждой строке матрицы М выделяется значение максимального элемента.

Наименьшее из выделенных значений и есть величина радиуса графа.

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

37

Вопросы и упражнения для самопроверки

1. В каких случаях при построении матрицы метрики М в ней останутся неопределённые элементы после достижения устойчивой матрицы смежности графа: ¾ Rk = Rk+1 ?

2. Возможна ли ситуация, когда Rk = Rk+1 при k = 1 ?

3. Для графа, заданного матрицей смежности (рисунок 4.2), определить его радиус и диаметр.

Рисунок 4.2

4. Для графа, заданного матрицей смежности (рисунок 4.3), выполнить следующее:

4.1.Построить метрику графа.

4.2.Вычислить радиус, диаметр данного графа.

4.3.Найти все периферийные и центральные вершины графа.

38

Рисунок 4.3