ПУТЬ в теории графов
— цепь, все ребра которой ориентированы в направлении движения от начальной к конечной вершине цепи. П. изображается символом
где дуга инцидентна вершинам
П., в котором никакая вершина не встречается дважды, наз. элементарным. Если
и — некоторые вершины графа, для которых существует П.
то вершина х достижима из вершины
вершина
обратно достижима из вершины
Мн-во всех достижимых из
вершин обозначается символом
а обратно достижимых
Для любого мн-ва А вершин определяется достижимое мн-во
Аналогично определяется обратно достижимое мн-во
П., содержащий все дуги ориентированного графа, наз. эйлеровым. Г. А. Донец.
