Также однозначно определяет структуру графа.




Весьма важным видом графа является связный граф, не имеющий циклов, он называется деревом. В дереве любые две вершины связаны единственным путем.

Рассмотрим связный граф , пусть и - две его вершины. Длина кратчайшего - маршрута называется расстоянием между вершинами и обозначается через . Очевидно, что расстояние между вершинами является простой цепью и . Для любой вершины величина

(1.13.6)

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

. (1.13.7)

Минимальный из эксцентриситетов вершин графа называется его радиусом и обозначается через :

. (1.13.8)

Вершина называется периферийной, если ее эксцентриситет равен диаметру графа, т. е. . Простая цепь, расстояние между концами которой равно , называется диаметральной цепью.

 
 

Вершина называется центральной, если . Множество всех центральных вершин графа называется его центром. Центром может быть единственная вершина графа или несколько вершин (см. рис. 1.15). Здесь , ,

. Таким образом, . Периферийные вершины и , диаметральные цепи: и , центральная вершина .






Дата добавления: 2016-06-05; просмотров: 1130; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2022 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.022 сек.