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

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

Здесь вы сможете узнать про основные метрические характеристики графов и, конечно, про то, как их вычислять.

К каждому пункту, для лучшего восприятия материала, прикреплено изображение с примером.

И так, рассмотрим следующий граф:

Смешанный граф

 

Кратчайшее расстояние

Обозначение: d(xi, xj)

Если граф не взвешенный, то для каждой вершины посчитать кол-во рёбер (дуг) в пути до всех остальных вершин.

Если граф взвешенный, то вместо кол-ва рёбер (дуг) считается сумма весов этих рёбер (дуг).

 

Если граф неориентированный, то путь от xi до xj равен пути от xj до xi и, следовательно, вычислять нужно только один из них.

Если граф ориентированный, то xi-xj и xj-xi — это разные пути и вычислять необходимо оба.

Если граф смешанный, то для рёбер вычисляется только один путь, а для дуг - оба.

 

Частные случаи:

Если вершины не связаны (нет соединения или дуга направлена в другую строну), то d = ∞ (бесконечность).

Для петлиd(xi = xj) = 0.

 

Диаметр графа

Обозначение: D(G)

Это максимальное из кратчайших расстояний, т.е. D(G) = max d(xi, xj)

 

Эксцентриситет

 Обозначение: r(x)

Это максимальное удаление от конкретной вершины. Т.е. эксцентриситет равен максимальному значению из всех кратчайших расстояний, содержащих x в качестве аргумента.

Внимание: в ориентированном графе нужно рассматривать расстояния и ОТ данной точки и ДО данной точки, т.е. и d(x, xj) и d(xi, x)

 

 Радиус графа

Обозначение: R(G)

За значение радиуса принимается минимальное значение эксцентриситета: R(G) = min r(x)

 

Центр графа

Обозначение: {X1, X2, ...}

Это те вершины, в которых эксцентриситет равен радиусу графа: r(x) = R(G)

TEXT.RU - 100.00%

Поделиться ссылкой:

Добавить комментарий

Зарегистрируйтесь или Войдите, чтобы оставить комментарий.

Системное сообщение