§ 26. Понятие пути

В комбинаторике понятие пути играет существенную роль, и мы рассмотрим его, а также понятия, тесно связанные с ним.

Путем называется такая последовательность дуг, что конец каждой предыдущей дуги совпадает с началом следующей. Путь может быть конечным или бесконечным. Например,

— пути графа на рис. 90. Путь можно обозначить также последовательностью вершин, которые он содержит:

Простой путь. Путь называется простым, если никакая дуга не встречается в нем дважды, и составным в противном случае. Например, на рис. 90 - простой путь, а составной.

Элементарный путь. Путь называется элементарным, если в нем никакая вершина не встречается дважды, и неэлементарным в противном случае. Например, на рис. 90 - элементарный и простой путь, неэлементарный и простой, неэлементарный и составной.

Рис. 90.

Контур. Контур — это конечный пугь, у которого начальная вершина дуги совпадает с конечной вершиной дуги Контур можно обозначать как дугами, так и вершинами, которые он содержит. Примерами контуров графа на рис. 90 являются

Контур называется элементарным, если все вершины, через которые он проходит, различны (за исключением начальной и конечной, которые совпадают). На рис. 90 - элементарный контур.

Контур называется простым, если все его дуги различны. На рис. 90 простые контуры.

Длина пути. Длиной пути называют число его дуг и обозначают через Например (рис. 90),

Для удобства вводят понятие пути нулевой длины (изолированная вершина).

Замечание к понятию контура. Контуры, которые образованы одними и теми же дугами, взятыми в одинаковом порядке, и записи которых получаются одна из другой циклическим сдвигом, можно считать либо эквивалентными, либо неэквивалентными. Например, контуры (рис. 90)

можно считать либо эквивалентными, либо неэквивалентными. То же самое относится и к представлению с помощью вершин:

В случае надобности указывают начало контура.

При изучении подстановок (§ 16) мы представляли их с помощью графов, при этом циклы подстановок представлялись контурами. При изучении неориентированных графов используется термин «цикл». Понятий в математике больше, чем слов, которыми мы располагаем для их обозначения. Внимательный читатель избежит возможных недоразумений.

Рис. 91.

Гамильтонов путь. Элементарный путь, в котором число дуг на единицу меньше числа вершин графа, называется гамильтоновым путем. Иначе говоря, такой путь проходит через все вершины в точности по одному разу.

При записи с помощью вершин гамильтонов путь — перестановка вершин графа.

Например, путь (F, В, А, С, D, Е) на рис. 91 гамильтонов, а в графе на рис. 90 нет гамильтонова пути.

Аналогично гамильтонов контур — контур, проходящий через все вершины в точности по одному разу (исключая произвольно выбранное начало).

Задача перечисления гамильтоновых путей и контуров графа будет разбираться в главе IV.

УПРАЖНЕНИЯ

(см. скан)