Задание 3
ТЕМА 3
«Анализ информационных моделей»
Пример 1
На рисунке схема дорог района изображена в виде графа, а в таблице содержатся сведения о длине этих дорог в километрах.
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги от пункта Д до пункта Г. В ответе запишите целое число.
Решение
По графу видно, что пункт Л является вершиной, с исходящими четырьмя дорогами. В таблице единственный пункт с таким набором дорог П8.
Из пункта В выходит две дороги, каждая в пункт, который имеет по три дороги. Из таблицы видно, что в пункт П2 ведут две дороги из пунктов с тремя дорогами, следовательно П2 это пункт В.
Из пункта E идут дороги в Л и В, но при этом, в отличие от пункта А, третье ребро ведет в вершину, из которой нет ребра в Л. Значит пункт П1 это Е.
Из пункта Б ведёт три дороги, две из них в пункты с тремя дорогами, третья в пункт с четырьмя дорогам. Из таблицы видно, что этому условию соответствует пункт П6, из которого дороги идут аналогично. Следовательно П6 это пункт Б.
Из пункта А ведут дороги в пункты Б, В и Л. По таблице определяем, что из пункта П3 дороги ведут в Б, В и Л.Тогда П3 это пункт А.
Из пункта Г дороги идут в Б, Д и Л. Из таблицы видно, что из пунктов П3 и П5 идут дороги в Б и Л, а так как пункт П3 это А, тогда П5 это пункт Г.
Из пункта Д ведут две дороги, одна — в пункт Г с тремя дорогами, другая — в пункт К, имеющий две дороги. Из таблицы видно, что такой набор путей идет из пункта П7, значит П7 это пункт Д.
Следовательно оставшийся пункт П4 это К.
Расстояние от пункта Д (П7) до пункта Г (П5) 16 км
Ответ: 16
Пример 2
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E. Передвигаться можно только по указанным дорогам.
Решение
Способ 1
В пункт Е можно попасть только из пунктов D и F, значит, в искомом маршруте должен присутствовать пункт D. Составим все возможные маршруты, придерживаясь этой особенности:
А – B – D – E – F: 19 км
A – C – D – E – F: 19 км
A – D – E – F: 18 км
Ответ: 18 км
Способ 2
Для решения можно построить взвешенный граф, соответствующий заданной таблице. По графу легко определить все пути из пункта A в пункт F, проходящий через E. Останется определить только кратчайшее расстояние:
Кратчайший путь A – D – E – F: 18 км
Ответ: 18 км
Пример 3
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и Е, проходящего через пункт С. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Решение
Способ 1
Найдём все варианты маршрутов из A в E, проходящие через пункт С и выберем самый короткий используя исходную таблицу. Таких оптимальных маршрутов можно построить только три, т.к. остальные будут с циклами.
A — B — C — D — E: длина маршрута 9 км.
A — C — D — E: длина маршрута 8 км.
A — C — B — D — E: длина маршрута 14 км.
Способ 2
Можно построить взвешенный граф маршрутов в виде дерева, соответствующий данной таблице. На дереве видны все возможные варианты маршрутов. Среди них легко определить длину кратчайшего пути между пунктами А и E, проходящего через пункт С.
Ответ: 8
Пример 4
Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых (в километрах) приведена в таблице:
Определите длину кратчайшего пути между пунктами А и F, проходящего через пункт D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Решение
Построим взвешенный граф маршрутов в виде дерева, соответствующий исходной таблице. На дереве можно выделить все возможные варианты маршрутов. Среди них легко определить длину кратчайшего пути между пунктами А и F, проходящего через пункт D.
Ответ: 8
Комментарии, отзывы и предложения Вы можете направить на e-mail, указанный в контактах или оставить в гостевой книге, указав тему вопроса: перейти в гостевую книгу