K-связность

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

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

Граф называется [math]k[/math]-связным, если [math]\kappa(G) \ge k[/math]

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

Граф называется [math]k[/math]-реберно связным, если [math]\lambda(G) \ge k[/math]

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

Множество [math]S[/math] вершин, ребер или вершин и ребер разделяет [math]u[/math] и [math]v[/math], если [math]u[/math] и [math]v[/math] принадлежат различным компонентам графа [math]G-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] тривиально.