Простой путь
Простой путь — это путь в графе, в котором каждая вершина встречается не более одного раза. Такое ограничение помогает рассматривать движение между вершинами без возвратов и повторного посещения уже пройденных точек.
Путь задаётся последовательностью вершин, соединённых рёбрами. Например, последовательность \(A, B, C, D\) является простым путём, если существуют рёбра \(AB\), \(BC\) и \(CD\), а вершины \(A\), \(B\), \(C\), \(D\) различны. Понятие цепи в графе близко к простому пути: цепь также не использует одно ребро повторно, но в некоторых определениях вершины цепи могут повторяться. Поэтому при решении задач важно смотреть на точное условие.
Если простой путь содержит \(k+1\) вершин, то его длина \(L\) равна числу пройденных рёбер, то есть \(k\). В ориентированном графе при переходе также нужно соблюдать направление каждой дуги.
В графе есть рёбра \(AB\), \(BC\), \(CD\), \(DA\) и \(AC\). Последовательность \(A\to B\to C\to D\) — простой путь: вершины не повторяются. Последовательность \(A\to B\to C\to A\) простым путём не является, потому что вершина \(A\) встречается дважды. Она образует замкнутый маршрут и связана с понятием цикла в графе.
Простой путь не обязан проходить через все вершины графа. Путь, проходящий по одному разу через каждую вершину графа, называется гамильтоновым; это более специальное понятие, которое рассматривается на странице гамильтонов путь.
Какая последовательность является простым путём, если рёбра между соседними вершинами существуют?
Главное
- Простой путь — путь, в котором вершины не повторяются.
- Если в пути \(k+1\) вершин, его длина равна \(k\) рёбрам.
- Простой путь не обязательно проходит через все вершины графа.