В теорії графів кажуть що граф G з множиною вершин V G k вершинно зв язний або k зв язний якщо граф залишається зв язним

В теорії графів кажуть, що граф G з множиною вершин V(G) k-вершинно-зв'язний (або k-зв'язний), якщо граф залишається зв'язним після видалення менше ніж k вершин з графу. Інакше кажучи, граф k-зв'язний, якщо k — це розмір найменшої множини вершин, після видалення якої граф перестає бути зв'язним.

Тотожне визначення для графів з двома і більше вершинами таке, граф є k-зв'язним, якщо будь-які дві його вершини можуть бути сполучені через k незалежних шляхів; дивись теорему Менгера.

Хоча визначення в літературі тотожні для більшості графів вони несумісні, коли мова йде про повні графи K_n, він альтернативно вважається n-зв'язним, (n-1)-зв'язним або навіть нескінченно зв'язним.

1-вершинно-зв'язний граф називається зв'язним, а 2-вершинно-зв'язний граф називають двозв'язним.

Вершинна зв'язність або просто зв'язність, це найбільше k для якого граф є k-вершинно-зв'язним.

1-кістяк будь-якого k-вимірного опуклого політопа утворює k-вершинно-зв'язний граф.

Див. також

Примітки

Schrijver, Combinatorial Optimization, Springer

Посилання

Balinski, M. L. (1961), On the graph structure of convex polyhedra in n-space, Pacific Journal of Mathematics, 11 (2): 431—434, архів оригіналу за 11 вересня 2012, процитовано 19 березня 2011.
Diestel, Reinhard (2005), (вид. 3rd), Berlin, New York: Springer-Verlag, ISBN , архів оригіналу за 28 липня 2011, процитовано 19 березня 2011.

[Schrijver-1] Schrijver, Combinatorial Optimization, Springer