![]() |
ГРАФА СВЯЗНОСТЬГРАФА СВЯЗНОСТЬ - одна из топологических характеристик графа. Граф наз. связным, если для любых его вершин u и v существует цепь, соединяющая эти вершины. Числом вершинной связности графа G [обозначение א(G)] наз. наименьшее число вершин, удаление к-рых (вместе с инцидентными им ребрами) приводит к несвязному графу или к графу, состоящему из одной изолированной вершины. Числом реберной связности [обозначение λ(G)] наз. наименьшее число ребер графа G, удаление к-рых приводит к несвязному графу. Граф G наз. k-связным, если א(G) ≥ k, и k-реберно связным, если λ(G) ≥ k. Максимальный по включению k-связный подграф графа G наз. его k-связной компонентой; 1-связная компонента наз. компонентой связности. При исследовании коммуникационных и логических сетей числа связности соответствующих графов можно интерпретировать как степень надежности этих сетей. В теории графов изучаются способы установления Г. с, условия, при к-рых граф является k-связным или k-реберно связным, соотношения между различными видами связности, зависимость чисел связности от других параметров графа и т. п. Так, если δ(G) - минимальная степень вершин графа G, то справедливы следующие неравенства: א(G) ≤ λ(G) ≤ δ(G). Для любых целых а, b, с (0 < а ≤ b ≤ с) существует граф G, у к-рого א(G) = a, λ(G) = b, δ(G) = c. Если граф G имеет n вершин и δ(G) ≥ [n/2], то λ(G) = δ(G). Говорят, что множество S вершин, ребер или вершин и ребер разделяет вершины u и v, если u и v принадлежат разным компонентам связности графа G-S, полученного из G удалением элементов множества S. Справедливы следующие утверждения. Наименьшее число вершин, разделяющих две несмежные вершины u и v, равно наибольшему числу простых цепей, не имеющих общих вершин, соединяющих u и v. Граф G является k-связным тогда и только тогда, когда любая пара его вершин соединена по крайней мере к вершинно непересекающимися цепями. Аналогичные теоремы справедливы и для реберной связности. Граф k-реберно связен тогда и только тогда, когда любая пара его вершин соединена по крайней мере к реберно непересекающимися цепями. Множество ребер, удаление к-рых приводит к несвязному графу, наз. разрезом. В каждом графе наибольшее число реберно непересекающихся разрезов, разделяющих вершины u и v, равно наименьшему числу ребер простой цепи, соединяющей u и v, т. е. расстоянию d(u, v) между u и v. Лит.: [1] Xарари Ф., Теория графов, пер. с англ., М., 1973; [2] Форд Л., Фалкерсон Д., Потоки в сетях, пер. с англ., М., 1966. А. А. Сапоженко. Источники:
|
![]()
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
|||
![]() |
|||||
© MATHEMLIB.RU, 2001-2021
При копировании материалов проекта обязательно ставить ссылку на страницу источник: http://mathemlib.ru/ 'Математическая библиотека' |