Презентация на тему Формальные описания реальных объектов и процессов ОГЭ 2021. Задание № 4

(рисунок слева), в котором 5 вершин (A, B, C,

D и E). Он описывается таблицей (весовая матрица). В ней, например, число 4 на пересечении строки В и столбца С означает, что:
во-первых, есть ребро, соединяющее В и С;
во-вторых, вес этого ребра равен 4;
пустая клетка на пересечении строки А и столбца В означает, что ребра из А в В нет;
граф по заданной таблице может быть нарисован по-разному. Например, той же таблице соответствует граф, показанный на рисунке справа от нее.
В приведенном примере матрица симметрична относительно главной диагонали. Это может означать, например, что стоимости перевозки из В в С и обратно равны (это не всегда так)

Е построены дороги, протяжённость которых (в километрах) приведена в

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

представим в виде графа.
Определяем длину пути между пунктами

А и Е.
Выбрать кратчайший путь.

пунктами
A, B, C, D, Е и указаны протяжённости

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

друг от друга города А – В.
Проверяем это.
АСВ=17+1=18
АDB=8+11=19
AEDB=3+6+11=20
AEDCB=3+6+9+1=19
АDСB=8+9+1=18

кратчайшее расстояние = 18

В таблице указана протяжённость дорог между пунктами, через которые

он может пройти. Укажите длину самого короткого участка кратчайшего пути от Ивана-Царевича до Марьи Царевны (от точки И до точки М). Передвигаться можно только по дорогам, указанным в таблице

 

представим в виде графа.
Определяем длину пути между пунктами

И и М.
Выбрать кратчайший путь.
Укажите длину самого короткого участка кратчайшего пути

1

2

1

3

А

В

И

1

Б

М

Г

ИГМ=6+1=7

километрах) приведена в таблице.
Определите длину кратчайшего пути между

пунктами A и C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

представим в виде графа.
Определяем длину пути между пунктами

А и С.
Выбрать кратчайший путь.

ADВС=3+1+2=6

Е построены дороги, протяжённость которых (в километрах) приведена в

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

и выберем самый короткий.
 
Из пункта A можно попасть в

пункты B, С.
Из пункта B можно попасть в пункты C, E.
Из пункта C можно попасть в пункт D.
Из пункта D можно попасть в пункт E.
 

A—B—C—D—E: длина маршрута 17 км.
A—B—E: длина маршрута 11 км.
A—C—D—E: длина маршрута 12 км.
A—C—B—E: длина маршрута 10 км.

Самый короткий путь: A—C—B—E. Длина маршрута 10 км.

Ответ: 10

в пункт С за 6 часов. Из представленных таблиц

выберите такую, согласно которой машинист сможет доехать из пункта А в пункт С за это время. В ячейках таблицы указано время (в часах), которое занимает дорога из одного пункта в другой. Передвигаться можно только по дорогам, указанным в таблицах.

пункт С за 6 часов. Прямой дороги за это

время нет

Рассмотрим варианты через город А-В-С (сложим время в пути).

Ответ: II