k-связность

Материал из Викиконспекты
Перейти к: навигация, поиск

k-cвязность — одна из топологических характеристик графа.

Определение:
Граф называется вершинно k-связным, если удаление любых (k  -  1) вершин оставляет граф связным.


Вершинной связностью графа называется \varkappa (G) = \max  \{ k \mid G вершинно k-связен \}, при этом для полного графа полагаем \varkappa (K_n) = n - 1.


Определение:
Граф называется реберно l-связным, если удаление любых (l - 1) ребер оставляет граф связным.


Реберной связностью графа называется \lambda(G) = \max \{ l \mid G реберно l-связен \}, для тривиального графа считаем \lambda (K_1) = 0.


[править] k-связность и непересекающиеся пути между вершинами

Рассмотрим граф G и вершины u и v.

Пусть S — множество вершин/ребер/вершин и ребер.

S разделяет u и v, если u и v принадлежат разным компонентам связности графа G \setminus S, который получается удалением элементов множества S из G.

Из теоремы теоремы Менгера для вершинной k-связности имеем, что наименьшее число вершин, разделяющих две несмежные вершины u и v, равно наибольшему числу простых путей, не имеющих общих вершин, соединяющих u и v.

Отсюда непосредственно следует:

Утверждение:
Граф G является вершинно k-связным \Leftrightarrow любая пара его вершин соединена по крайней мере k вершинно непересекающимися путями.

Подобная теорема справедлива и для реберной связности. То есть из теоремы Менгера для реберной k-связности следует:

Утверждение:
Граф  G является реберно l-связным \Leftrightarrow любая пара его вершин соединена по крайней мере l-реберно непересекающимися путями.

[править] См. также

[править] Источники информации

  • Харари Ф. Теория графов.[1] — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
  • Форд Л., Фалкерсон Д., Потоки в сетях, пер. с англ., М., 1966
Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты