Главная > Теория графов. Алгоритмический подход
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
След.
Макеты страниц

Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

3. Петли, ориентированные циклы и циклы

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

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

Так, например, в графе, приведенном на рис. 1.3, последовательности дуг

являются замкнутыми путями.

Пути (1.7) и (1.9) являются замкнутыми простыми орцепями (контурами, или простыми орциклами), поскольку в них одна и та же вершина используется только один раз (за исключением начальной и конечной вершин, которые совпадают), а путь (1.8) не является контуром, так как вершина используется в нем дважды. Контур, проходящий через все вершины графа, имеет особое значение и называется гамильтоновым контуром. Конечно, не все графы обладают гамильтоновыми контурами. Так, например, контур (1.9) является гамильтоновым контуром графа, приведенного на рис. 1.3, а граф на рис. 1.2 не имеет гамильтоновых контуров, поскольку не существует такой дуги, для которой была бы конечной вершиной.

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

На рис. 1.3 маршруты

и

являются замкнутыми маршрутами.

1
Оглавление
email@scask.ru