Маршруты в орграфе

Задачи, связанные с маршрутами в орграфе, имеют большое практическое значение, что и дает стимул к развитию и совершенствованию методов их решения. Наиболее часто встает вопрос о минимальных и максимальных расстояниях, о числе маршрутов определенной длины.

Пример 13.1. Дан орграф (рис. 13.1). Сколько в нем маршрутов длиной 3?

Рис. 13.1

Решение. Используем алгебраический метод решения задачи на основании теоремы 12.4. Запишем матрицу смежности. Матрица смежности орграфа – несимметричная.

, .

Возведем эту матрицу в степень 3. Суммируя все элементы полученной матрицы, находим, что число маршрутов длиной 3 равно восьми. Три единицы, стоящие по диагонали, показывают, что сюда входит 3 помеченных контура. Очевидно, что это контуры: 1–4–3, 4–3–1, 3–1–4.