Примеры решения задач

Пример 1. Для графа G = (X, U), изображённого на рис. 16.30, записать матрицу расстояний и список расстояний.

Рис. 16.30. Граф G

Решение: запишем матрицу расстояний для заданного графа.

Матрица расстояний будет иметь вид:

.

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

D = {<1,2,1>;<1,3,1>;<1,4,2>;<2,3,2>;<2,4,1>;<3,4,1>}.

Пример 2. Для графа G = (X,U), заданного на рис. 16.31, построить его отображение в координатную решётку и матрицу геометрии. Подсчитать суммарную длину рёбер L(G)графа, отображённого в координатную решётку.

Рис. 16.31. Граф G

Решение: после отображения в координатную решётку графа G получим граф G _r, показанный на рис. 16.32.

Рис. 16.32. Отображение графа G в координатную решетку

Теперь для полученного графа G _r запишем матрицу геометрии. Как уже говорилось ранее, матрица геометрии получается путём перемножения матрицы расстояний D и матрицы смежности:

.

В результате перемножения матриц мы получили матрицу геометрии Dg. Сумма элементов данной матрицы равна 24. Следовательно, суммарная длина рёбер L(G)графа G _r равна 12.

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1. Что такое метрика графа?

2. Как определяется расстояние между двумя вершинами графа?

3. Каким образом формируется матрица расстояний?

4. В чем состоит отличие между матрицей расстояний и матрицей геометрии?

5. Каким образом определяется диаметр графа?

6. Каким образом граф отображается в координатную решетку?

7. Как построить список расстояний?

8. Как определяется радиус графа?

9. Что такое число протяженности?

10. Каким образом определяется расстояние между узлами решетки?