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

По этой ссылке вы найдёте полный курс лекций по математике:

связный граф. Через d(u, v) обозначим длину кратчайшей цепи, связывающей вершины и и v. Покажем, что d(u, v) обладает свойствами метрики. Симметричность. Свойство очевидно. Неравенство тр еуго.ъника. Метрические характеристики графа Действительно, объединив кратчайшие цепи из и в w и из w в v, получим маршрут из и в v длиной , длина кратчайшей цепи из и в v будет не более этой величины. Невырожденность. Непосредственно вытекает из определения d(u, v).

Таким образом, на множестве вершин связного графа введена структура метрического пространства. d(«, v) будем называть расстоянием между вершинами и и V.

Эксцентриситетом вершины и называется наибольшее из расстояний от и до других вершин графа: Минимальный эксцентриситет вершин графа называют радиусом графа: а максимальный эксцентриситет — диаметром: . Другими словами, диаметр графа — это наибольшее из расстояний между двумя вершинами графа. Если эксцентриситет вершины совпадает с радиусом графа, то вершину называют центральной. Центральные вершины графа составляют ею центр.

Возможно вам будут полезны данные страницы:

Вершина называется периферийной, если ее эксцентриситет равен диаметру графа. Несколько примеров. В полном графе расстояние между любыми двумя (разными) вершинами равно 1, поэтому В полном графе каждая вершина является и периферийной, и центральной. Последнее свойство имеет место и для циклического графа С„, для которого радиус также совпадает с диаметром: обозначение целой части). Метрические характеристики графа.

единице, а диаметр — двум, одна вершина является центральной, а остальные — периферийные. Установим соотношения между радиусом и диаметром графа. Теорема 3. Для произвольного графа G справедливы неравенства: м Первое неравенство следует непосредственно из определений: Метрические характеристики графа Чтобы доказать второе неравенство, положим: . Применяя неравенство треугольника, получим: . Теорема доказана.