Связность графов

Пусть – граф с вершинами () и ребрами ().

Определение 1.6. Маршрутом (путем) длины из вершины в вершину (или между и ) называется последовательность такая, что .

Таким образом, путь длины имеет ребер. По причине избыточности обозначений в этом определении путь для графа в общем случае будет обозначаться как .

Если все ребра различны, то путь называется цепью. Если все вершины различны (а значит, и ребра), то путь называется простой цепью. Замкнутая цепь называется циклом. Замкнутая простая цепь называется простым циклом. Граф без циклов называется ациклическим.

Аналогично, как и для графа, для орграфа вводятся понятия ориентированный путь, ориентированный цикл.

Пример 1.3. Дан неориентированный граф.

,

Определение 1.7. Граф называется связным, если имеется цепь между любыми двумя его различными вершинами.

Для заданного ориентированного графа можно построить неориентированный граф такой, что каждая ориентированная дуга (исключая петли) станет неориентированным ребром графа . В таком случае граф называется соотнесенным графом орграфа .

Определение 1.8. Орграф называется связным, если его соотнесенный граф является связным. Орграф называется сильно связным, если для любой пары вершин существует ориентированный путь из в .