Връхна k-свързана графа

В теорията на графите се казва, че графGеk-върхово свързан(илиk-свързан), ако има повече отkвърха и след премахване на по-малко отkот всички върхове, графикът остава свързан.

Връхната свързаностили простосвързаносттана графа е най-голямотоk, за което графът еk-върхово свързан.

Като алтернатива, непълна графа имасвързваемостkакоkе размерът на най-малкото подмножество от върхове, така че графът да стане несвързан, когато бъде премахнат [1] . Пълните графи се изключват от разглеждане, защото не могат да бъдат разединени чрез премахване на върхове. Пълен граф сnвърха има връзкаn− 1, както следва от първата дефиниция.

Еквивалентна дефиниция е, ако за всяка двойка върхове на графика е възможно да се намерятkнепресичащи се пътеки, свързващи тези върхове, вижте теоремата на Menger (Diestel 2005, стр. 55). Тази дефиниция има същия отговор:n− 1 за свързаността на пълния графKn[1] .

1-свързаният граф се нарича още свързан, 2-свързаният граф се нарича двойносвързан граф, 3-свързаният граф се нарича съответнотрисвързан.

1-скелет (английски) български. всекиk-мерен изпъкнал политоп образуваk-връх-свързан график (теорема на Balinsky, Balinski, 1961). Частично обратната теорема на Щайниц гласи, че всяка равнинна графа, свързана с 3 върха, образува скелета на изпъкнал полиедър.

---