§ 47. Перечисление рассечений

Рассечением графа называют такую совокупность элементарных путей или элементарных контуров, что:

1) два пути рассечения не имеют общих вершин;

2) каждая вершина графа принадлежит одному из путей рассечения.

Например, на рис. 218 и 219 представлены рассечения графа на рис. 217.

Среди различных путей рассечения графа будем различать: элементарные контуры — их обозначаем символом а» элементарные пути ненулевой длины — их обозначаем символом (3; пути нулевой длины — их обозначаем символом

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

(кликните для просмотра скана)

Пример. Перечислим рассечения графа на рис. 217 (если они существуют), состоящие из элементарного контура длины 3 и элементарного пути длины 2. Нам, следовательно, нужно рассмотреть матрицы Контуры длины 3:

Возьмем, например, и, исключая строки и столбцы в получаем пути длины Но нам нужно выбросить, так как он содержит С. Итак, получаем рассечения:

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

УПРАЖНЕНИЯ

(см. скан)