Презентация - Задание ОГЭ по информатике 4 анализ моделей объектов кратчайший путь в графе

Задание ОГЭ по информатике №4 Анализ моделей объектов: кратчайший путь в графе
Учитель информатики Бабкова Галина Владимировна, МАОУ СОШ №20 имени Милевского Н.И.

Что нужно знать, чтобы построить дерево графа по таблице:
строки таблицы обозначены буквами и соответствуют вершинам графа; числа в строке показывают, с какими вершинами соединена данная; числа в строке обозначают длину пути к этим вершинам от той, которой соответствует строка; путь не может проходить через одну вершину дважды, то есть буква в цепочке повторяться не должна.

Определите длину кратчайшего пути между пунктами А и E.
А
В
С
D
E
1+7=8
E
E
1+2+3=6
1+2+4=7
Ответ: 6

Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C.
А
В
E
D
F
C
C
F
E
В
D
F
3+2+2+3=10
F
Ответ: 10
3+2+2+1+1=9

Определите длину кратчайшего пути между пунктами A и B, проходящего через пункт D.
А
F
В
E
D
B
D
E
C
5+6+8=19
В
C
В
C
E
5+6+3+4=18
5+2+3+8=18
В
В
5+2+3+3+4=17
Ответ: 17
5+6+3+1+4=19

Задачи для самостоятельного решения
Определите длину кратчайшего пути между пунктами А и E
Ответ: 5

№ 1186. Определите длину кратчайшего пути между пунктами A и D, проходящего через пункт F.
строим дерево; выделяем пункт F и конечные D (по-разному); для путей, содержащих F, проставляем длину ребер;
Ответ: 12

Источники
Задания взяты с сайта К.Полякова, частично изменены https://kpolyakov.spb.ru/school/oge/gen.php?action=viewAllEgeNo&egeId=204&cat127=on Использованы картинки с сайта https://abrakadabra.fun/25164-uchitel-na-prozrachnom-fone.html Рисунки и анимация автора Бабковой Г.В.