Метрические характеристики графа

Обозначим через d(a, b) длину (число ребер или дуг) кратчайшего маршрута между вершинами a и b.

Для d(a, b) справедливы следующие утверждения:

1) d(a, a) = 0,

2) d(a, b) ³ 0,

3) d(a, b) = 0 Þ a = b,

4) d(a, b) d(a, c) + d(c, b),

5) d(a, b) = d(b, a) – только для неорграфа расстояния симметричны.

Есть ли в графе маршруты длины k? Для того, чтобы это определить составим матрицу смежности графа А. Далее необходимо возвести А в степень k, используя бинарные операции, Ù,Ú:

А ¹ ~ А, А ² ~ А * А, А ³ ~ А ²* А, но не А * А ², А^k = А^{k –1} * А, но не А * А^{k –1}.

Анализ элементов позволяет оценить наличие маршрутов длины k между вершинами i и j:

если = 1, то маршруты длины k в графе имеются;

если = 0, то маршрутов длины k между вершинами i и j нет.

Сколько маршрутов длины k имеется в графе? Для ответа на этот вопрос необходимо составить матрицу смежности А. возвести А в степень k, используя правила обычного умножения матриц. Провести анализ элементов позволяет оценить количество маршрутов длины k: = число – количество маршрутов длины k.

Какие маршруты длины k имеются в графе? Для ответа на данный вопрос необходимо присвоить всем ребрам и дугам графа имена в виде букв с индексами или без них. Составить матрицу смежности графа А так, что если вершины i и j соединены ребром (дугой) с именем x, то элемент матрицы a_ij будет равен x. возвести матрицу смежности А в степень k, производя умножение и сложение по правилам:

1) Умножение – a & b = ab ba,

2) Сложение – a v b = b v a,

3) При этом c (a v b) = ca v cb ac v bc,

aa = 0 – так как ищем кратчайшие маршруты и повторение ребер (дуг) недопустимо, aab = 0, 0 b = 0.

анализ элементов позволяет определить маршруты длины k.

При решении таких задач для маршрутов – предельный показатель степени k = n – 1, так как ищем кратчайшие маршруты.

Для цикловзадачи решаются аналогично, только здесь:

– предельный показатель степени k = n,

– наличие циклов определяется по значениям элементов .

Если требуется определить кратчайшие маршруты или циклы с началом в заданной вершине, то в степень следует возводить строку матрицы смежности этой вершины.