K-связность

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

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

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

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

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

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

Реберной связностью графа называется [math] \lambda(G) = \max \{ l | G [/math] реберно [math] l [/math] - связен [math] \} [/math]

Теорема:

[math] \varkappa (G) \leqslant \lambda (G) \leqslant \sigma (G) [/math] , где [math] \sigma(G) [/math] - минимальная степень вершин графа [math] G [/math]

Доказательство:

[math]\triangleright[/math]

smth

[math]\triangleleft[/math]

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

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

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

Говорят, что вершины [math]u[/math] и [math]v[/math] [math]k[/math]-разделимы, если минимальная мощность множества, разделяющего [math]u[/math] и [math]v[/math] равна [math]k[/math]

Многие утверждения для связных графов можно обобщить для случая [math]k[/math]-связности, однако аналог тривиального утверждения часто оказывается содержательным. Простейший пример - Теорема Менгера, утверждение которой для [math]k=1[/math] тривиально.