K-связность

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

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

Числом вершинной связности [math]\kappa(G)[/math] называется наименьшее число вершин, которое надо удалить, чтобы граф потерял связность.

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

Числом реберной связности [math]\lambda(G)[/math] называется наименьшее число ребер, которое надо удалить, чтобы граф потерял связность.

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

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

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

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

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

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

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