Глава 27. Вершинная и реберная связность

ТЕОРЕМА Граф связен тогда и только тогда, когда его нельзя представить в виде объединения двух графов.

Мостом Называется ребро, удаление которого увеличивает число компонент связ­ности.

Вершинной связностью Графа G (обозначается C(G)) называется наименьшее чи­сло вершин, удаление которых приводит к несвязному или тривиальному графу.

Граф G Называется K-связным, Если C (G) = K.

Реберной связностью Графа G (обозначается l(G)) называется наименьшее число ребер, удаление которых приводит к несвязному или тривиальному графу.

ТЕОРЕМА C(G) £ l(G) £ d(G).

< Предыдущая		Следующая >