Математическая энциклопедия - графа связность
Связанные словари
Графа связность
одна из топологических характеристик графа. Граф наз. связным, если для любых его вершин и н 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
Вопрос-ответ:
Похожие слова
Самые популярные термины
1 | 557 | |
2 | 483 | |
3 | 480 | |
4 | 472 | |
5 | 454 | |
6 | 440 | |
7 | 437 | |
8 | 433 | |
9 | 424 | |
10 | 423 | |
11 | 422 | |
12 | 413 | |
13 | 406 | |
14 | 375 | |
15 | 375 | |
16 | 372 | |
17 | 365 | |
18 | 364 | |
19 | 364 | |
20 | 362 |