ЦЕПЬ графа

— последовательность вида , где ребра все различны и ребро соединяет (в любом направлении) вершины и графа ). Вершина начальной, вершина конечной, а число длиной Ц. Ц. наз. простой, если все ее вершины различны. Ц., содержащая все ребра графа, наз. эйлеровой, а простая Ц., содержащая все вершины графа, — гамильтоновой. Если в Q каждое ребро дуга, идущая из в , то Ц. наз. ориентированной (допуская, наряду с дугами, также петли, получим путь). Если в Q разрешить повторения ребер, то получим маршрут. См. также Графов теория. Г. А. Донец, А. А. Зыков.