Связность

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

Применительно к сетям связи связность характеризуется наличием каналов связи между заданными узлами, их количеством и качественными характеристиками, способностью обеспечивать передачу заданных потоков сообщений с заданными требованиями к качеству связи в условиях различных воздействий противника на узлы и каналы связи.

Для исследования различных характеристик сети на графах вводится неструктурная информация в виде весовых коэффициентов, но и изучение только структурных свойств графов, характеризующих, их связность имеет существенное значение.

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

Напомним, что граф называется связным, если из любой вершины v_i в любую другую вершину v_j существует путь(маршрут).

При этом некоторые вершины и ребра могут быть особенными.

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

Ребро с аналогичным свойством называется мостом.

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

Блок графа- это его максимальный неразделимый подграф.

Полносвязный блок называют кликой.

Рис.23. Граф и его блоки. а) граф G, б,в,г,д)- блоки графа G₁,G₂,G₃, G₄. v₁ иv₂ – точки сочленения, в) –мост G₂ (ребро <v₁ v₂>). г) и д) – клики G₃ иG₄

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

Реберной связностью λ(G) называют минимальное число ребер, удаление которых приводит к несвязному или тривиальному графу. Другими словами, λ(G)- это число ребер в разрезе с минимальным числом ребер. Для ее определения достаточно рассмотреть базисное множество разрезов.

Смешанная связность σ(G)- минимальное число вершин и ребер, удаление которых приводит к несвязному графу.

Для характеристики смешанной связности σ (G) используют понятие пары связности, под которой понимают упорядоченную пару(a,b), таких целых неотрицательных чисел, что найдется множество, содержащее а вершин и b ребер, удаление которых делает граф несвязным, и не найдется множества с а-1 вершинами и в ребрами или а вершинами и b-1 ребрами, обладающего этим же свойством. Так, пары (æ,0) и (0, λ)являются парами связностей. Эта функция называется функцией связности графа G.

Вершинная связность важна при оценке живучести в условиях воздействия оружия противника на узлы связи, реберная – при оценке помехозащишености сети, смешанная при воздействии средств РЭБ (помех и оружия) на сети (системы) связи.

Важное значение при изучении связности имеет степень вершин d(v_i) и минимальная степень вершин графа δ(G).

Доказано, что для любого графа выполняются:

æ(G) ≤ λ(G) ≤ δ (G)

кроме того, показано, что ограничения накладываемые на λ, δ и æ нельзя улучшить.

Если же граф G имеет n вершин и δ (G) ≥ [n / 2],то λ(G) = δ(G) и наибольшая связность графа равна [2m / n], если m ≥ n-1.

Рис.24. Граф, для которого æ(G) = 2{v₁ и v₂ или v₇ и v₈},

λ(G) = 3 { <v₁v₇>,<v₂v₇>,<v₂v₈>}, σ (G)= 2 {v₂ и <v₁,v₇>} или {v₇ и <v₂,v₈>}.

С точки зрения воздействия противника это означает, что для нарушения связности сети необходимо:

-уничтожить узлы v₁ и v₃;

-уничтожить узлы v₇ и v₈;

-подавить каналы или уничтожить линии связи, соответствующие на модели ребрам <v₁v₇>, <v₂v₇>, <v₂v₈>;

-уничтожить узел v₂ и подавить <v₁v₇>;

-уничтожить узел v₇ и подавить <v₂v₈>.

Пары связности графа: (0,3); (1,1); (2,0)функция связности показана на рис.25.

σ(æ)
				æ

Рис.25. Функция связности F(æ) графа G