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

- одна из топологических характеристик графа. Граф наз. связным, если для любых его вершин и н vсуществует цепь, соединяющая эти вершины. Числом вершинной связности графа G [обозначение [img: http://localhost:8080/file/010429-57.jpg] ] наз. наименьшее число вершин, удаление к-рых (вместе с инцидентными им ребрами) приводит к несвязному графу или к графу, состоящему из одной изолированной вершины. Числом реберной связности [обозначение [img: http://localhost:8080/file/010429-58.jpg] ] наз. наименьшее число ребер графа G, удаление к-рых приводит к несвязному графу. Граф G наз. k-связным, если [img: http://localhost:8080/file/010429-59.jpg] и k-pеберно связным, если [img: http://localhost:8080/file/010429-60.jpg]. Максимальный по включению k-связный подграф графа G наз. его k-cвязной компонентой; 1-связная компонента иаз. компонентой связности. При исследовании коммуникационных и логических сетей числа связности соответствующих графов можно интерпретировать как степень надежности этих сетей. В теории графов изучаются способы установления Г. с., условия, при к-рых граф является k-связным или k-реберно связным, соотношения между различными видами связности, зависимость чисел связности от других параметров графа и т. п. Так, если [img: http://localhost:8080/file/010429-61.jpg] - минимальная степень вершин графа G, то справедливы следующие неравенства: [img: http://localhost:8080/file/010429-62.jpg] Для любых целых [img: http://localhost:8080/file/010429-63.jpg] существует граф G, у к-рого [img: http://localhost:8080/file/010429-64.jpg] Если граф G имеет пвершин и [img: http://localhost:8080/file/010429-65.jpg], то [img: http://localhost:8080/file/010429-66.jpg]. Говорят, что множество Sвершин, ребер или вершин п ребер разделяет вершины и и v, если ии vпринадлежат разным компонентам связности графа G-S, полученного из G удалением элементов множества S. Справедливы следующие утверждения. Наименьшее число вершин, разделяющих две несмежные вершины ии v, равно наибольшему числу простых цепей, не имеющих общих вершин, соединяющих ии v. Граф G является k-связным тогда и только тогда, когда любая пара его вершин соединена по крайней мере kвершинно непересекающимися цепями. Аналогичные теоремы справедливы и для реберной связности. Граф k-реберно связен тогда и только тогда, когда любая пара его вершин соединена по крайней мере kреберно непересекающимися цепями. Множество ребер, удаление к-рых приводит к несвязному графу, наз. разрезом. В каждом графе наибольшее число реберно непересекающихся разрезов, разделяющих вершины ии v, равно наименьшему числу ребер простой цепи, соединяющей [img: http://localhost:8080/file/010429-67.jpg] т. е. расстоянию [img: http://localhost:8080/file/010429-68.jpg] между ии v.