НОВОСТИ    БИБЛИОТЕКА    ЭНЦИКЛОПЕДИЯ    БИОГРАФИИ    КАРТА САЙТА    ССЫЛКИ    О ПРОЕКТЕ  

ГРАФА СВЯЗНОСТЬ

ГРАФА СВЯЗНОСТЬ - одна из топологических характеристик графа. Граф наз. связным, если для любых его вершин 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.

А. А. Сапоженко.


Источники:

  1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.











© MATHEMLIB.RU, 2001-2021
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'Математическая библиотека'
Рейтинг@Mail.ru