Способ нахождения метрики графа

Справка по ИДЗ «Графы»

Скелет графа общего вида. В случае, когда при исследовании графа L=(X.U;P) общего вида требуется не полная информация о нём, а лишь знание того, какие пары его различных вершин смежны и какие нет, прибегают к носителю такой информации – скелету графа L, который обозначим как . Граф относится к классу обыкновенных графов с множеством вершин тем же, что и в графе L, и новым множеством рёбер , определённым следующим образом:

1) если в графе L есть петли, то они удаляются;

2) если в графе L есть дуги, то производится дезориентация дуг;

3) если в графе L есть кратные рёбра, то они заменяются одним эквивалентным ребром-звеном;

4) оставшиеся рёбра образуют множество рёбер .

Таким образом, множество рёбер состоит из рёбер, полученных из множества U после выполнения описанных выше процедур 1, 2, 3.

Определение числа маршрутов длины «L» на графе

Маршрутом m_i,j в графе G=(X,U) называется конечная последовательность вершин и рёбер вида –

m_0,l =( x₀,u₁,x₁,u₂,x₂,...,x_l–1,u_k, x_l ),

где x₀, x_l – соответственно начальная и конечная вершины маршрута m_0,l .

Очевидно, в конечном графе G=(X,U) можно выделить только конечное число маршрутов. Длина маршрута m_i,j равна числу рёбер, которые в него входят.

Часто требуется знать, сколько маршрутов заданной длины в графе G связывает вершину x_i с вершиной x_j .

Для определения маршрутов длины q в графе G=(X,U) его матрицу смежности R возводят в степень, равную q. Тогда для каждого значения степени q=1,2,…,k значение элемента (r_i,j)^q матрицы R^q определяет количество маршрутов m_i,j длиной, равной значению степени q.

Рисунок 3

ПРИМЕР. Для графа G= (X,U) , представленного на рисунке 3, определить количество маршрутов длины, равной 2.

Матрица смежности R графа G имеет вид:

R=

Возведем матрицу R в квадрат:

R²=

Значение каждого элемента r_i,j матрицы R² равно числу маршрутов длины 2, ведущих из вершины x_i в вершину x_j.

Например, r_3,2=2 означает, что в графе два маршрута длины 2, которые ведут из вершины x₃ в вершину x₂ . Запишем их:

m_3,2=x_3,3,x₁,1,x₂; m_3,2 =x₃,4,x₄,2,x₂.

Задание 4.

Для графа, представленного на рисунке 1 выполнить следующее:

4.1. Привести примеры подграфов 3-х вершинных, 4-х вершинных, 1-вершинных.

4.2. Привести пример суграфа данного графа.

4.3. Выполнить унарные операции для вершин, помеченных *.

Задание 5.

Для графа G=(X,U) ( рисунок 1) выполнить следующее:

5.1. Построить матрицу метрики (отклонений).

5.2. Вычислить радиус и диаметр.

5.3. Определить периферийные точки.

Способ нахождения метрики графа

Для нахождения метрики = графа L = (X,U) достаточно знать его матрицу смежности R={ r_i,j} над булевой алгеброй B = ( 0,1 ), т.е. элементы матрицы r_i,j = 1, если вершины x_i и x_j – смежны и r_i,j = 0, в противном случае, все действия над элементами матрицы R производятся по правилам логической алгебры:

1 + 1 = 1; 0 + 0 = 0; 1 + 0 = 1; 0 * 0 = 0; 1 * 0 = 0.

Сопоставляя уже известные нам способы для установления существования маршрутов в графе длины q = m, можно утверждать, что при возведении в степень матрицы S = R + E, где Е – единичная матрица той же размерности, что и размерность матрицы R, на некотором шаге возведения в степень получим:

S = S^k+1, т.е. устойчивую матрицу S в степени «k».

Значения степеней p матрицы S^p: p= {k, k–1, k–2, ... , 1} равны длинам простых кратчайших цепей, связывающих вершины x_i и x_j.

Таким образом, последовательно возводя в степень p = {1, 2, 3,…, k} матрицу S до получения устойчивой матрицы S^k, можно определить расстояния между всеми вершинами графа L=(X,U), построив матрицу метрики графа L.