+Схема дослідження відношень В общем случае обозначим G через произвольный граф с вершинами n, ребрами m и компонентами k. Применяя описанную выше процедуру к каждой компоненте , получим в результате граф, называемый остовным лесом. Число удаленных в этой процедуре ребер называется циклическим рангом или циклическим числом графа и обозначается через m - n + k. Мы видим, что и является неотрицательным целым числом. Таким образом, циклический ранг дает меру связности графа: циклический ранг дерева равен нулю, а циклический ранг циклического графа равен единице. Удобно также определить коциклический ранг или ранг разреза графа как число ребер в его остовном лесе. Коциклический ранг обозначается через и равен n - k Лема про рукопотискання : число вершин з непарною валентністю має бути парним. Имеется простой алгоритм (так называемый алгоритм Флери) для нахождения эйлерова цикла (конечно, если этот цикл существует), который состоит в следующем: начинаем с любой вершины и "стираем” пройденные ребра. При этом по мосту (перешейку) проходим только, если нет других возможностей.
| 