Пусть дан граф G - связный.
• Определение №1: ( Число вершинной связности )
Минимальное число в-н, удаление которых из графа приводит к несвязному или одновершинному графу наз-ся числом вершинной связности.
Обозначается: K(G)
• Определение №2: ( Число реберной связности )
Минимальное число ребер графа, удаление которых приводит к несвязному графу наз-ся числом реберной связности графа.
Обозначается: "лямбда"(G)
*** К-связные графы ***
• Определение №3:
Граф G наз-ся k-связным, если K(G) <= k.
Т.О. граф связный без циклов, отличный от k1 явл. 1-связный граф, а цикл - 2-связный граф.
*** Соотношение между "хи"(G), "лямбда"(G) и "дельта"(G) ***
• Теорема №1:
Для любого связного графа верны нер-ва:
K(G) <= "лямбда"(G) <= "дельта"(G)