ОГЭ Задание №9 Информационные модели ГРАФЫ И МАТРИЦЫ

точками или геометрическими фигурами. Это вершины графа.
Связи между объектами

изображаются линиями. Это рёбра графа.
Необходимо определить расстояние различных путей, ведущих из одного города в другой.

1. На основании таблицы нужно построить граф всех возможных путей перемещения из начального пункта в конечный пункт.

2. Обозначить на схеме расстояние между пунктами.
3. Определить расстояние по каждому возможному пути.

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

вершины A индекс всегда равен 1 (в начало пути можно попасть единственным образом – никуда не двигаясь). Теперь сформулируем правило: индекс вершины равен сумме индексов его предков. Исходя из этого индекс Б равен 1 (предок у Б один – вершина A).
У вершины Д предками являются А и Б, значит индекс вершины Д равен 1+1=2.

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

вершин. Индекс вершины Ж и будет ответом задачи.

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

пути между пунктами A и Е.

Варианты ответов:
1) 4 2) 5 3) 6 4) 7

графу видно, что есть три маршрута из А в Е:

АВСЕ: 2 + 1 + 2 = 5
АСЕ: 5 +2 = 7
ADCE: 1 + 3 +2 = 6
Кратчайший из них АВСЕ: 2 + 1 + 2 = 5

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

пути между пунктами A и Е.

Варианты ответов:
1) 4 2) 5 3) 6 4) 3

маршрута из А в Е:
АВЕ: 2 + 2 =

4
АВСЕ: 2 + 1 + 2 = 5
АСЕ: 3 +2 = 5
ADCE: 1 + 3 +2 = 6
Кратчайший из них: АВЕ = 2 +2 = 4

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

пути между пунктами В и Е.

Варианты ответов:
1) 10 2) 9 3) 18 4) 8

графу видно, что есть два кратчайших маршрута из В в

Е:
ВАЕ: 5 + 5 = 10
ВDЕ: 4 + 5 = 9
Все остальные гораздо длиннее.
Кратчайший из них  ВDЕ: 4 + 5 = 9

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

пути между пунктами A и Е.

Варианты ответов:
1) 5 2) 7 3) 8 4) 10

графу видно, что есть три маршрута из А в Е:

АВСЕ: 2 + 2 + 3 = 7
АСЕ: 5 +3 = 8
ADCE: 2 + 4 +3 = 9
Кратчайший из них АВСЕ: 2 + 1 + 2 = 5

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

пути между пунктами В и Е.

Варианты ответов:
1) 7 2) 8 3) 9 4) 10

графу видно, что есть пять маршрутов
из В в Е:

ВAЕ: 7 + 4 =11
BСDЕ: 2 + 3 + 5 = 10
BDE: 5 + 5 = 10
BADE: 7 + 1 + 5 = 13
BDAE: 5 + 1 + 4 = 10

Одинаковые по длине кратчайшие маршруты:
BCDE, BDE, ВDAE. Длина каждого равна 10.