Жёсткость графа

Жёсткость графа — мера связности графа: граф G t-жёсток при некотором вещественном t, если для любого целого k > 1 нельзя разбить граф G на k различных компонент связности путём удаления менее чем tk вершин. Например, граф 1-жёсток, если число компонент, образующихся при удалении вершин, всегда не превосходит числа удалённых вершин. Жёсткость графа — это максимальное t, для которого он t-жёсток. Число является конечным числом для всех конечных графов, за исключением полных графов, которые, по соглашению, имеют бесконечную жёсткость.

Жёсткость была введена Вацлавом Шваталом в 1973 году; впоследствии понятию было посвящено много обширных исследований других специалистов по теории графов, так, обзор 2006 года, целиком посвящённый жёсткости, насчитывает 99 теорем и 162 страницы.

Источник: Википедия

а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я