Пример.

Решение.

Пример.

Решение.

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

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

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

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

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

Найти число максимальных путей графа с матрицей смежности А порядка 4: .

Граф состоит из 4-х вершин и 4-х дуг: (х₁, х₂), (х₂, х₃), (х₃, х₄). Путь х₁ u₁ х₂ u₂ х₃ u₃ x₄, длина которого равна 3, является максимальной, следовательно, число максимальных путей равно 1.

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

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

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

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

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

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

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

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

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

Определение 46. Полным ориентированным графом называется граф, каждая пара вершин которого соединена в плоскости одним ориентированным ребром.

Теорема 9.Всякий полный ориентированный граф с n вершинами имеет простой ориентированный путь, проходящий через все вершины графа.

Иногда встречаются графы, часть ребер которых ориентирована, а другая – нет. Такие графы называют смешанными. Смешанный граф можно превратить в ориентированный мультграф, если каждое его неориентированное ребро заменить двумя ориентированными и противоположно направленными: (а,b) и (b,а). Примером смешанного графа является сеть городских улиц, если на некоторых улицах установлено одностороннее движение, а на других – двустороннее.