Связность в неориентированных графах

Связный неориентированный граф G – любая пара вершин соединена маршрутом (либо простой цепью) в G.

Компонента связности или компонента графа G – максимальный связный подграф графа G.

Две вершины и называются связанными в графе G, если в графе G существует маршрут между этими двумя вершинами. Вершина считается связанной сама с собой.

Связный граф состоит из одной компоненты связности.

Число вершинной связности χ (G) – наименьшее число вершин, удаление которых приводит к несвязному или одновершинному графу.

Например:

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

Например:

Считается, что .

Точка сочленения (разделяющая вершина) – вершина v графа G, удаление которой увеличивает количество компонент связности графа G.

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

Неразделимый граф – граф без точек сочленения.

Блок – максимальный неразделимый подграф графа G.