ЕГЭ-2015 задание 5.

Анализ информационных моделей

При решении задач данного вида используется знания информационных моделей (таблицы, диаграммы, графики) и перебор вариантов, выбор лучшего по какому-то признаку

Теория

• особых знаний, кроме умения перебирать варианты (не пропустив ни одного!) здесь, как правило, не требуется
• полезно знать, что такое граф (это набор вершин и соединяющих их ребер) и как он описывается в виде таблицы, хотя, как правило, все необходимые объяснения даны в формулировке задания
• чаще всего используется взвешенный граф, где с каждым ребром связано некоторое число (вес), оно может обозначать, например, расстояние между городами или стоимость перевозки
• рассмотрим граф (рисунок слева), в котором 5 вершин (A, B, C, D и E); он описывается таблицей, расположенной в центре; в ней, например, число 5 на пересечении строки В и столбца С означает, что, во-первых, есть ребро, соединяющее В и С, и во-вторых, вес этого ребра равен 5; пустая клетка на пересечении строки А и столбца В означает, что ребра из А в В нет

• обратите внимание, что граф по заданной таблице (она еще называется весовой матрицей) может быть нарисован по-разному; например, той же таблице соответствует граф, показанный на рисунке справа от нее 
• в приведенном примере матрица симметрична относительно главной диагонали; это может означать, например, что стоимости перевозки из В в С и обратно равны (это не всегда так)
• желательно научиться быстро (и правильно) строить граф по весовой матрице и наоборот

Задача

Между населенными пунктами A, B, C, D, E, F, G построены дороги, протяженность которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

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

Решение

Из пункта A за 1 шаг можно попасть в пункты B и D. AB(2) и AD(6) - в скобках указана длина маршрута.
Из пункта B можно попасть в пункты C и D. ABC(2+5=7) и ABD(2+3=5).
Из пункта C можно попасть в пункты D и G. ABCD(2+5+1=8) (этот путь длиннее прямого AD и его можно не рассматривать дальше) и ABCG(2+5+8=15) - первый способ добраться в конечный пункт длиной 15.
Из пункта D можно попасть в пункты E и F, причем будем учитывать только кратчайший маршрут ABD длиной 5. Соответственно ABDE (2+3+9=14) и ABDF (2+3+7=11).
Из пункта E попадаем в G и общая длина пути ABDEG (2+3+9+5=19) равна 19.
Из пункта F попадаем в G и общая длина пути ABDFG (2+3+7+7=19) тоже равна 19.

Правильный ответ: 15.

• < Назад
• Вперёд >