K-связность

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

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

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

Вершинной связностью графа называется [math] \varkappa (G) = \max \{ k | 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 | G [/math] реберно [math] l [/math] - связен [math] \} [/math]

При [math] n = 1, \lambda (K_1) = 0 [/math] .

Если граф [math]G [/math] имеет [math]n [/math] вершин и [math] \sigma (G) \ge \left [ \frac{n}{2} \right ] \quad [/math], то [math] \lambda (G) = \sigma (G) [/math], где [math] \sigma(G) [/math] - минимальная степень вершин графа [math] G [/math]

Рассмотрим граф [math] G [/math] .

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

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

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

Справедливы следующие утверждения:

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

Тогда:

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

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

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

• [math]\lambda(G) = k[/math] [math]\Leftrightarrow[/math]  для всех пар вершин [math] u [/math] и [math] v [/math] существует [math]k[/math] реберно непересекающихся путей из [math] u [/math] в [math] v [/math]. (См.Теорема Менгера для реберной [math]k - [/math] связности)

Тогда:

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

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

Смотри также

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

Литература

• Харари Ф. Теория графов.[1] — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)

• Форд Л., Фалкерсон Д., Потоки в сетях, пер. с англ., М., 1966