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

 

Длиной маршрута ( v₀,v₁, …, v_n) называется число ребер, содержащихся в маршруте, причем каждое ребро учитывается столько раз, сколько оно встречается в маршруте.

Пример:

Длина маршрута M=(v₀,v₁, …, v_n) равна n.

 

Любому ребру приписывается единичная длина, если граф не является взвешенным.

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

Достаточно задать матрицу весов:

, где

Обхватом графа Gназывается длина наименьшего простого цикла графа G, если таковой имеется; обозначается: g(G).

Окружением графа Gназывается длина наибольшего простого цикла графа G, если таковой имеется; обозначается: C(G).

Пример:

Расстоянием между двумя вершинами u и vграфа G называется длина кратчайшей простой цепи, соединяющей эти вершины; обозначается: d(u,v).

Если вершины u и vграфа G не связаны, расстояние считается равным бесконечности: d(u,v)=¥.

В связном графе расстояние является метрикой, т.е. удовлетворяет следующим аксиомам.

" u,v,w ÎV:

1) d(u,v)³0 (d(u,v)=0 <=> u=v);

2) d(u,v)=d(v,u);

3) d(u,v)+d(v,w)= d(u,w).

Кратчайшая простая цепь, соединяющая вершины u и v, называется геодезической и обозначается: s(u,v).

 

Алгоритм нахождения кратчайших маршрутов (волновой).

 

Пусть задан неориентированный граф G=(V,E). Необходимо найти расстояние от одной заданной вершины до другой, или от одной заданной ко всем остальным вершинам графа G.

Идея алгоритма:

– выбирается некоторая вершина графа G и определяются все “соседи” выбранной вершины (“соседями” называются вершины, смежные с данной);

– эти вершины помечаются;

– определяются “соседи соседей” и также помечаются и т. д.

Алгоритм заканчивает работу, если:

– все вершины помечены (граф связен);

– построены все геодезические, связывающие данную вершину со всеми остальными;

– найдены расстояния от данной вершины ко всем остальным.

Если не все вершины в результате работы алгоритма помечены, это означает что граф G не связен.

Пример:

 

v1	v2	v4	v6	v3	v5	v9	v10	v7	v8

Эксцентриситетом, или отклоненностью, вершины v графа G называется длина максимальной геодезической, исходящей из этой вершины; обозначается: .

Диаметром графа G называется максимальный среди всех эксцентриситетов вершин графа; обозначается: .

Периферией графа G называется множество вершин графа G, для которых эксцентриситет равен диаметру, т.е.: .

Радиусом графа G называется минимальный из эксцентриситетов вершин графа G; обозначается: r(G)=min e(u), uÎV.

Центром графа G называется множество вершин, для которых эксцентриситет равен радиусу графа. т.е.: e(v) = r(G).

 

Примеры:

Определим матрицу расстояний:

Матрица расстояний несвязного графа может состоять из нескольких матриц (для каждой компоненты) или иметь блочный вид.

 

Пример: найти e(v) в заданном графе

 

 

Используем волновой алгоритм.

 

Первая компонента связности графа G:

v	j	u		d(u,v)
a		a	a
		b	ab
		d	abd
		f	abf
		c	abdc
		e	abfe

 

Вторая компонента связности графа G:

v	j	u		d(u,v)
g		g	g
		h	gh

 

Построим матрицу расстояний:

 

 

d(G)=3; r(G)=2; периферия: {a,c,e,f}; центр: {b,d} - для первой компоненты связности.

d(G)=1; r(G)=1; периферия: {g,h}; центр: {g,h} - для первой компоненты связности.