Математическое моделирование на графах. Часть 1. Берцун В.Н. - 15 стр.

UptoLike

Составители:

Рубрика:

Глава 1. Основные понятия теории графов 15

несвязным, если хотя бы две его вершины не связаны. Например, на

рис. 1.16 представлен связный (1.16, а) и несвязный (1.16, б) граф.

аб

Связный граф Несвязный граф

Рис. 1.16

Назовем расстоянием d(u, v) длину кратчайшей простой цепи ме-

жду вершинами u и v в графе G, тогда d(u, u) = 0, ∀ u∈V. Если вер-

шина v недостижима из u, то полагаем d(u, v) = ∞. В связном графе G

расстояние обладает следующими свойствами (удовлетворяет ак-

сиомам метрики):

1) d(u, v) ≥ 0 и d(u, v) = 0 тогда и только тогда, когда u = v;

2) d(u, v) = d(v, u), ∀u, v∈V(G);

3) d(u, v) ≤ d(u, w) + d(

w, v), ∀ u, v, w∈V(G).

Эксцентриситет вершины u графа G есть величина

() max (,), ( ).eu d uv v V G=∈

Наибольшее расстояние между вершинами называется диамет-

ром графа (diam(G)), а минимальный из эксцентриситетов вершин

связного графа называется радиусом графа (rad(G)). Вершина u,

для которой достигается минимум e(u), называется центральной.

Множество всех центральных вершин образует центр графа.

Например, у простого цикла С

диаметр и радиус совпадают, а

каждая вершина является центральной. Для полных графов K

diam(G) = rad(G) = 1.