K-связность

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

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

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

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

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

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

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

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

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

[math]\kappa(G) \le \lambda(G) \le \delta(G)[/math], где [math]\lambda(G)[/math] - минимальная степень вершины