Графа Связность

- одна из топологических характеристик графа. Граф наз. Связным, если для любых его вершин и н 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. А. А. Сапоженко..