- ГРАФА СВЯЗНОСТЬ
- одна из топологических характеристик графа. Граф наз. связным, если для любых его вершин и н vсуществует цепь, соединяющая эти вершины. Числом вершинной связности графа G [обозначение
] наз. наименьшее число вершин, удаление к-рых (вместе с инцидентными им ребрами) приводит к несвязному графу или к графу, состоящему из одной изолированной вершины. Числом реберной связности [обозначение 
] наз. наименьшее число ребер графа G, удаление к-рых приводит к несвязному графу. Граф G наз. k-связным, если 
и k-pеберно связным, если 
. Максимальный по включению k-связный подграф графа G наз. его k-cвязной компонентой; 1-связная компонента иаз. компонентой связности. При исследовании коммуникационных и логических сетей числа связности соответствующих графов можно интерпретировать как степень надежности этих сетей.
В теории графов изучаются способы установления Г. с., условия, при к-рых граф является k-связным или k-реберно связным, соотношения между различными видами связности, зависимость чисел связности от других параметров графа и т. п. Так, если
- минимальная степень вершин графа G, то справедливы следующие неравенства:
Для любых целых
существует граф G, у к-рого 
Если граф G имеет пвершин и 
, то 
. Говорят, что множество Sвершин, ребер или вершин п ребер разделяет вершины и и v, если ии vпринадлежат разным компонентам связности графа G-S, полученного из G удалением элементов множества S. Справедливы следующие утверждения.
Наименьшее число вершин, разделяющих две несмежные вершины ии v, равно наибольшему числу простых цепей, не имеющих общих вершин, соединяющих ии v. Граф G является k-связным тогда и только тогда, когда любая пара его вершин соединена по крайней мере kвершинно непересекающимися цепями. Аналогичные теоремы справедливы и для реберной связности. Граф k-реберно связен тогда и только тогда, когда любая пара его вершин соединена по крайней мере kреберно непересекающимися цепями. Множество ребер, удаление к-рых приводит к несвязному графу, наз. разрезом. В каждом графе наибольшее число реберно непересекающихся разрезов, разделяющих вершины ии v, равно наименьшему числу ребер простой цепи, соединяющей
т. е. расстоянию 
между ии v.
Лит.:[1] Xарари Ф., Теория графов, пер. с англ., М., 1973; [2] Форд Л., Фалкерсон Д., Потоки в сетях, пер. с англ., М., 1966. А. А. Сапоженко.
Математическая энциклопедия. — М.: Советская энциклопедия. И. М. Виноградов. 1977—1985.
