Материал: связные графы

Маршруты, цепи, циклы

Утверждение 1. Всякий маршрут,

объединяющий любые две вершины графа,

имеет простую цепь, соединяющую эти

вершины.

Утверждение 2. Всякий цикл в графе

содержит простой цикл.

Связные графы

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

Все вершины одного класса связаны между собой, вершины из разных классов между собой не связаны. Подграф, образованный всеми вершинами одного класса,

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

Связные графы

Теорема 1. Граф является связным тогда и только

тогда, когда его нельзя представить в виде

дизъюнктивного объединения двух графов.

В ориентированных графах существуют различные виды связности.

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

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