§ 45. Перечисление последовательностей с повторением

Рассмотрим граф на рис. 210. Обозначим через свойство: через вершины путь проходит не более одного раза, а через вершины путь проходит не более двух раз;

Рис. 210.

Рис. 211.

через свойство: через вершины путь проходит в точности один раз, а через вершины путь проходит в точности два раза.

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

Так как для пути со свойством не выполняется условие 3) (см. начало § 41), то он не является -латинской последовательностью. Легко видеть, что пути со свойством являются -латинскими последовательностями. Перечислив их, мы можем отобрать из них пути со свойством

Соответствующие выкладки для отыскания путей со свойством 9 приведены на стр. 256 до включительно. Их следует продолжить до так как путь со свойством содержит не более восьми вершин. Это показывает, что для нахождения путей с заданным свойством не являющихся -латинскими последовательностями, следует подобрать (когда это возможно) свойство так, чтобы: а) пути со свойством были -латинскими последовательностями и б) среди путей со свойством содержались все пути со свойством а затем перечислить -латинские последовательности.

Можно поступить и иначе. Возьмем, например, граф (см. рис. 210) и заменим его графом в котором инцидентны тем же вершинам в соединены двумя противоположно ориентированными дугами (рис. 211). Достаточно теперь найти элементарные пути графа а затем положить

УПРАЖНЕНИЯ

(см. скан)