Пример.

Решение.

Для матрицы инциденций пронумеруем пути: u₁– (х₁, х₁), u₂ – (х₂, х₃), u₃ – (х₃, х₄), u₄ – (х₄, х₃), u₅ – (х₄, х₄), u₆ – (х₃, х₅), u₇ – (х₅, х₄), u₈ – (х₆, х₇).

Матрица смежности графа имеет вид: Матрица инциденций графа имеет вид:

Определение 38. Маршрут – чередующаяся последовательность вершин и дуг (вершины могут повторяться).

Определение 39. Путем в ориентированном графе от А₁ до А_n называется последовательность ориентированных ребер ,…, , т.е. маршрут, такой, что конец каждого предыдущего орребра совпадает с началом следующего и ни одно орребро не встречается более одного раза.

Определение 40. Простым (элементарным) путем в ориентированном графе называется путь, в котором ни одна вершина не содержится более одного раза.

Определение 41. Цепь – последовательность вершин и ориентированных ребер, образующих путь. Всякий путь – цепь (обратное верно лишь для неориентированных графов, в которых понятие пути и цепи совпадают).

Определение 42. Замкнутый путь в ориентированном графе называется ориентированным циклом.

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

Определение 43.Эйлеровым путем в ориентированном графе называется путь, содержащий все его ориентированные дуги.

На рисунке А) изображен эйлеров орграф, так как имеется ориентированный цикл abcdeca, содержащий все его ориентированные дуги. Изменение ориентации в одной дуге, например (c,b) вместо (b,c), превращает этот орграф в неэйлеров (рис. В). В пункт b можно приехать по двум дорогам, но нельзя оттуда выехать.

Определение 44. Длиной пути в ориентированном графе называется число дуг в этом пути.

Замечание. Путь нулевой длины состоит из одной вершины. Путь может быть конечным и бесконечным.

Определение 45. Путь минимальной длины называют кратчайшим путем. Путь максимальной длины – максимальным путем.

Определение 46. Расстоянием от А до В в ориентированном графе называется длина наикратчайшего пути от А до В.

Замечание. Среди огромного числа задач теории графов отметим следующие три задачи, относящиеся к задачам о кратчайшем пути и имеющие важное прикладное значение. Задача 1. Найти в графе (X, G) путь, ведущий от вершины А к вершине В. Задача 2. Найти путь наименьшей длины, ведущий от А к В. Задача 3. Каждой дуге графа (X, G) отнесем число, которое назовем длиной дуги. Требуется найти путь, ведущий из данной вершины А в данную вершину В такой, что его полная длина была наименьшей.