Партнерка на США и Канаду по недвижимости, выплаты в крипто

  • 30% recurring commission
  • Выплаты в USDT
  • Вывод каждую неделю
  • Комиссия до 5 лет за каждого referral

Вершину с наименьшим эксцентриситетом называют центральной, а вершину с наибольшим эксцентриситетом - периферийной. Множество всех центральных вершин называется центром графа. Сама величина наименьшего эксцентриситета называется радиусом графа и обозначается через rad(G), а величина наибольшего - диаметром и обозначается diam(G). Иначе говоря,

rad(G)=\min_{x\in

diam(G)=\max_{x\in

Наименьший диаметр имеет полный граф - его диаметр равен 1. Среди связных графов с вершинами наибольший диаметр, равный n-1, имеет цепь P_{n}.

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

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

\ecc(x)

Центр этого графа составляют вершины , , ; периферийные вершины - , и ; радиус его равен , а диаметр . Одна из диаметральных цепей порождается множеством вершин \{1, 3, 6, 7, 8, 9\}.


Рис. 2.3.

Маршруты и связность в орграфах

Для ориентированного графа можно определить два типа маршрутов. Неориентированный маршрут (или просто маршрут) - это чередующаяся последовательность x_{1},e_{1},x_{2},вершин и ребер графа, такая, что для каждого i=1,2\ldots k-1выполняется одно из двух: e_{i} =(x_{i},x_{i+1})или e_{i} =\quad \left(x_{i+1},x_{i} \right). Маршрут называется ориентированным (или ормаршрутом), если e_{i} =(x_{i},x_{i+1})для каждого . Таким образом, при движении вдоль маршрута в орграфе ребра могут проходиться как в направлении ориентации, так и в обратном направлении, а при движении вдоль ормаршрута - только в направлении ориентации. Это различие очевидным образом распространяется на пути и циклы, так что в орграфе можно рассматривать пути и орпути, циклы и орциклы. Будем говорить, что маршрут соединяет вершины x_{1}и x_{k}, а ормаршрут ведет из x_{1}в x_{k}.

Соответственно двум типам маршрутов определяются и два типа связности орграфов. Орграф называется связным (или слабо связным), если для каждой пары вершин в нем имеется соединяющий их маршрут; он называется сильно связным, если для каждой упорядоченной пары вершин (a,b) в нем имеется ормаршрут, ведущий из в . Максимальные по включению подмножества вершин орграфа, порождающие сильно связные подграфы, называются его областями сильной связности, а порождаемые ими подграфы - компонентами сильной связности. Очевидно, разные области сильной связности не могут иметь общих вершин, так что множество вершин каждого орграфа разбивается на области сильной связности. Областями сильной связности орграфа на рис. 2.4 являются множества \{1, 2, 5\}, \{3, 4, 6, 7, 8\}, \{9\}.


Рис. 2.4.

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6