Уроки 27 - 28
§17. Графы
Содержание урока
Ориентированный граф
Ориентированный граф
Наверное, вы заметили, что при изображении деревьев, которые описывают иерархию (подчинение), мы ставили стрелки от верхних уровней к нижним. Это означает, что для каждого ребра указывается направление, и двигаться можно только по стрелкам, но не наоборот.
Ориентированный граф (орграф) — это граф, в котором каждое ребро имеет направление.
Орграф может служить, например, моделью системы дорог с односторонним движением. Матрица смежности и весовая матрица для орграфа уже не обязательно будут симметричными.
На схеме на рис. 3.30 всего две дороги с двусторонним движением, по остальным можно ехать только в одну сторону.
Рис. 3.30
Рёбра в орграфе называют дугами. Дуга, в отличие от ребра, имеет начало и конец.
Нарисуйте граф по весовой матрице, показанной на рис. 3.31. С помощью дерева перебора найдите все возможные пути из вершины А в вершину Е, не проходящие дважды через одну и ту же вершину, и стоимости проезда по каждому из этих путей. Определите оптимальный путь из вершины А в вершину Е.
Рис. 3.31
Следующая страница 
Количество путей
Cкачать материалы урока
