по фото
Привет! Давай разберёмся с этим упражнением по графам вместе.
На картинке изображен ориентированный граф. Вершины графа обозначены буквами от A до I. Соединения между вершинами (они же рёбра графа) указывают направление от одной вершины к другой. Теперь мы можем ответить на вопросы.
- Задача: Сколько существует путей из вершины A в вершину E?
Путь — это последовательность вершин, при переходе по которым можно добраться от одной вершины графа к другой. Идём от A и смотрим все возможные варианты дойти до E. Сначала просто посчитаем их:
- A -> B -> E
- A -> C -> E
- A -> D -> B -> E
- A -> D -> C -> E
- A -> D -> E
- A -> F -> C -> E
- A -> F -> D -> B -> E
- A -> F -> D -> C -> E
- A -> F -> D -> E
Всего получается 9 путей.
- Задача: Как называется кратчайший путь из вершины A в вершину E?
Кратчайший путь — это такой путь, при котором число пройденных рёбер минимально. Ищем среди перечисленных путей самый короткий.
Здесь это путь A -> D -> E, который состоит из двух рёбер.
- Задача: Сколько существует путей, ведущих из вершины E в вершину A?
Чтобы ответить на этот вопрос, мы должны найти все возможные пути от E до A.
