Вершинно k-зв’язковий граф

язковий

У теорії графів кажуть, що графGk-вершинно-зв'язень(абоk-зв'язень), якщо він має більше ніжkвершин і після видалення менш ніжkбудь-яких вершин граф залишається зв'язковим.

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

Альтернативно граф, відмінний від повного, маєзв'язністьk, якщоkє розміром найменшого підмножини вершин, при видаленні якого граф стає незв'язним [1] . Повні графи виключено з розгляду, оскільки їх не можна зробити незв'язними шляхом видалення вершин. Повний граф зnвершинами має зв'язністьn− 1, як випливає з першого визначення.

Еквівалентне визначення — якщо для будь-якої пари вершин графа можна знайти неперетинних шляхів, що з'єднують ці вершини, див. теорему Менгера (Diestel 2005, С. 55). Це визначення має той самий відповідь: − 1 для зв'язності повного графаKn[1] .

1-зв'язковий граф називається також зв'язковим, 2-зв'язковий граф називається двозв'язним, 3-зв'язковий граф називається, відповідно,тризв'язковим.

1-скелет (англ.) українська. будь-якогоk-мірного опуклого багатогранника утворюєk-вершинно-зв'язковий граф (Теорема Балінського, Balinski, 1961). Частково зворотна теорема Штейніца стверджує, що будь-який 3-вершинно-зв'язковий планарний граф утворює скелет опуклого багатогранника.