k-вершинно-зв'язний граф
В теорії графів кажуть, що граф G з множиною вершин V(G) k-вершинно-зв'язний (або k-зв'язний), якщо граф залишається зв'язним по видаленню менше ніж k вершин з графа. Інакше кажучі, граф k-зв'язний, якщо k це розмір найменшої множини вершин такої, по видаленні якої граф перестає бути зв'язним.[1]
Тотожне визначення для графів з двома і більше вершинами таке, граф є k-зв'язним, якщо будь-які дві його вершини можуть бути сполучені через k незалежних шляхів; дивись теорему Менґера.
Хоча визначення в літературі тотожні для більшості графів вони несумісні, коли мова йде про повні графи Kn, він альтернативно вважається n-зв'язним, (n-1)-зв'язним або навіть нескінченно зв'язним[1].
1-вершинно-зв'язний граф називається зв'язним, а 2-вершинно-зв'язний граф називають двузв'язним.
Вершинна-зв'язність або просто зв'язність, це найбільше k для якого граф є k-вершинно-зв'язним.
1-кістяк будь-якого k-вимірного опуклого політопа утворює k-вершинно-зв'язний граф.
Див. також [ред.]
Примітки [ред.]
Посилання [ред.]
- Balinski, M. L. (1961), «On the graph structure of convex polyhedra in n-space», Pacific Journal of Mathematics 11 (2): 431–434, http://www.projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1103037323.
- Diestel, Reinhard (2005), Graph Theory (3rd вид.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4, http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/.
