Определение.
Ориентированным путем (ориентированным маршрутом) длины k из v0 в vk (или между v0 и vk) называется последовательность v0,e1,v1,e2,v2,e3,v3,…v(k-1),ek,vk такая, что eі = (v(і-1), vі).
Таким образом, ориентированный путь длины k имеет k ориентированных рёбер, при этом, конечно, обязательно учитывать направление ориентированных ребер, составляющих путь, т. е. начальная вершина последующего ориентированного ребра должна быть конечной вершиной предыдущего ориентированного ребра.
Определение. Если нет рёбер, предшествующих e1, то вершина v0 называется начальной; если нет рёбер, следующих после ek, то вершина vk называется конечной; вершины ориентированного пути, не являющиеся начальной или конечной, называются внутренними.
Замечание. Для сокращения записи ориентированный путь можно обозначать через v0, v1, v2, v3, …, vk или e1, e2, e3, …, ek (можно также опустить запятые).
Определение. Простым ориентированным путем из v0 в vk называется путь ориентированный, в котором нет повторяющихся вершин.
Пример 1. Рассмотрим ориентированный граф G1, который состоит из множества вершин V(G1), содержащего 6 элементов, и множества рёбер E(G1), содержащего 6 элементов: V(G1) = {a, b, c, d, e, f}, E(G1) = {(a, b), (a, c), (b, d), (c, d), (e, c), (f, d)}. Визуальное представление ориентированного графа G1:
Для ориентированного графа G1, показанного на рис. выше, определим несколько путей, в том числе простых. Например, из вершины a в вершину d имеются простые пути abd или acd длины 2.
Определение. Ориентированный путь, в котором каждое ребро используется не более одного раза, называется ориентированной цепью.
Простой ориентированной цепью называется ориентированная цепь, в которой нет повторяющихся вершин.
Пример 2. Для ориентированного графа G1, показанного на рис. выше, определим несколько цепей. Например, из вершины a в вершину d имеющиеся простые ориентированные пути abd и acd (см. пример 1) являются ориентированными цепями длины 2.
Определение. Ориентированная цепь называется циклической, если начальная и конечная вершины ориентированной цепи совпадают.
Определение. Циклическая ориентированная цепь, в которой каждое ребро используется не более одного раза, называется ориентированным циклом. Простым ориентированным циклом называется ориентированный цикл, в котором нет повторяющихся вершин, кроме вершины, которая является начальной и конечной вершиной.
Пример 3. Для ориентированного графа G1, показанного на рис. выше, поскольку он имеет вершину d, являющуюся стоком, цикла нет.
Определение. Неориентированный граф G, полученный из ориентированного графа путём удаления ориентации ребер при сохранении инцидентности, называется соотнесённым графом.
Определение. Ориентированный граф G называется связным, если его соотнесённый граф является связным неориентированным графом.
Определение. Ориентированный граф G называется сильно связным, если имеется ориентированный путь между любыми двумя его различными вершинами.
Например, ориентированный граф G1 является связным, но не является сильно связными, поскольку содержит сток (вершину d) и источники, т. е. в ориентированном графе G1 не между любыми двумя различными вершинами имеется ориентированный путь, например, нет ни единого пути в вершину a.
Теорема. Если в ориентированном графе G = G(V, E) существует путь из вершины vi в вершину vj, тогда существует простой путь из вершины vi в вершину vj.
Следствие. Граф G является сильно связным тогда и только тогда, когда между любыми двумя его вершинами существует простой путь.
Заметим, что необязательно, чтобы в ориентированном графе, который не является сильно связным, существовали стоки и источники, часто такой граф состоит из нескольких связных (сильно связных) подчастей. Теория относительно компонент связности ориентированных графов аналогична понятию для неориентированных графов (с учётом, конечно, наличия ориентации рёбер в орграфах), поэтому предлагаем ознакомиться с лекцией https://zen.yandex.ru/media/id/603a418d1684900aa2499416/6273d341fb19593ccbfd7165.
Упражнение. Для следующих ориентированных графов:
1) запишите простой ориентированный путь и если возможно, путь (маршрут) заданного ориентированного графа, не являющийся простым;
2) запишите, если возможно, примеры ориентированной цепи и ориентированного цикла заданного ориентированного графа, укажите, являются ли они простыми.
