Презентация - "Решение задач с использованием графов"

Структурная модель системы. Графы.
Лобанова Татьяна Юрьевна
АКШИ им. П.О.Сухого 2022 г.

Графы
Граф состоит из вершин, связанных линиями - рёбрами. Вершины графа изображаются кругами, овалами, точками, прямоугольниками и т. д.
Объекты представляются как вершины графа, а связи – как его рёбра.

Граф называется взвешенным, если его вершины или рёбра характеризуются некоторой дополнительной информацией - весами вершин или рёбер.
Взвешенный граф
D
E
A
80
70
60
90
50
C
B
90
Протяжённость дорог в километрах

Сеть и дерево
Цепь – путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза.
Дерево – это граф, в котором нет циклов.
Цикл - цепь, начальная и конечная вершины которой совпадают.
Сеть - граф с циклом.

1
2
2
2
2
2
1
1
1
1
2
1
1
2
Использование графов при решении задач
Сколько существует трёхзначных чисел, состоящих из цифр 1 и 2?

Использование графов при решении задач
Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице.

Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

Использование графов при решении задач
Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице.

Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

Использование графов при решении задач
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Использование графов при решении задач
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?