k-связность

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

Определение:

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

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

Определение:

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

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

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

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

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

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

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

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

Утверждение:

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

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

Утверждение:

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

См. также

• Теорема Менгера
• Теорема Менгера, альтернативное доказательство

Источники информации

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