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

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

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

Определите длину кратчайшего пути между пунктами А и E.

А

В

E

E

E

D

С

1

2

7

2

3

4

1+2+3=6

1+2+4=7

1+7=8

Ответ: 6

Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C.

А

В

E

3

1

C

E

2

2

D

F

1

3

F

1

D

1

F

3

F

1

3+2+2+3=10

3+2+2+1+1=9

Ответ: 10

C

В

3

2

Определите длину кратчайшего пути между пунктами A и B, проходящего через пункт D.

А

В

B

C

E

D

F

2

5

2

6

8

3

5+6+8=19

5+6+3+1+4=19

Ответ: 17

E

3

В

4

E

1

C

1

В

D

3

В

8

C

3

В

4

4

5+2+3+8=18

5+2+3+3+4=17

5+6+3+4=18

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

2

2

3

3

А

В

С

D

E

7

3

4

1

С

D

5

С

D

2

D

2

В

D

В

С

E

E

E

E

E

В

С

2

2

5

2

Ответ: 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
• Рисунки и анимация автора Бабковой Г.В.