- Путь (теория графов)
-
Путь (Цепь) в графе
— последовательность вершин
при
, таких, что две любые последовательные вершины соединены хотя бы одной дугой из
.
Число
рёбер в пути называется его длиной. Каждая из пар двух последовательных вершин называется его звеном.
Иногда различают понятие пути и цепи, называя термином "путь" ориентированную цепь в орграфе, в которой у каждого из звеньев дуга идёт от вершины с меньшим номером к вершине с бо́льшим.
Примечания
См. также
Ссылки
Категория:- Теория графов
Wikimedia Foundation. 2010.