Урок "Графы" адаптирован под ЕГЭ

МОДЕЛИРОВАНИЕ НА ГРАФАХ

ИНФОРМАЦИОННОЕ МОДЕЛИРОВАНИЕ

ЕГЭ №1, 13

Кратчайший путь между вершинами графа

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

Путь между вершинами А и В графа считается кратчайшим , если:

• эти вершины соединены минимальным числом ребер (в случае, если граф не является взвешенным)
• сумма весов ребер, соединяющих эти вершины, минимальна (для взвешенного графа)

Построение дерева решений

Алгоритмы поиска кратчайшего пути

Алгоритм Дейкстры

Метод динамического программирования

Построение дерева решений

Задание 1. На рисунке представлена схема дорог, связывающих населённые пункты A , B , C , D , E , F . Вес ребра означает стоимость проезда между двумя населенными пунктами. Определить минимальную стоимость проезда из пункта E в пункт C .

5

4

E

B

B

10

5

E

E

A

A

D

B

10

9

6

4

2

9

D

D

С

6

A

2

C

C

C

16

C

F

14

13

11

Ответ: 11

Алгоритм построения дерева решений , как правило, используется для нахождения кратчайшего пути в ориентированном графе.

ЕГЭ №1

На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.

Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам A и G на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

ЕГЭ №1

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Е.

ЕГЭ №13

На рисунке3 представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, 3, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город М, проходящих через город Ж, но не проходящих через город К?

ЕГЭ №13

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