Алгоритм построения системы независимых циклов графа

1. Строится произвольный остов графа. В исходном графе отмечаются рёбра, не включенные в остов.

2. Выбирается очередное отмеченное ребро и строится цикл, содержащий это ребро и рёбра остова. Рассмотренное ребро отмечается и, если есть ещё не отмеченные рёбра, то выполняется пункт 2, иначе - пункт 3.

3. По формуле Эйлера (3.2) производится проверка числа построенных циклов.

Пример 3.12.

Рис 3.12

1)(X 2, X 4)(X 4, X 5)(X 5, X 1)(X 1, X 3);

2)(X 3, X 5)(X 5, X 1)(X 1, X 2)(X 2, X 3);

3)(X 3, X 4)(X 4, X 5)(X 5, X 1)(X 1, X 2)(X 2, X 3).