Использование и анализ информационных моделей (таблицы, диаграммы, графики)
 Скачать 4.49 Mb.
|
Ещё пример задания:Р-08. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Е. В ответе запишите целое число – так, как оно указано в таблице.  Решение: для того чтобы определить нужные нам вершины В и Е в весовой матрице, легче всего подсчитать степени вершин, то есть для каждой вершины найти количество рёбер, с которыми она связана (петля – ребро, которое соединяет вершину саму с собой, как кольцевая дорога, считается дважды) в весовой матрице степень вершины – это количество непустых клеток в соответствующей строке (показаны справа от таблицы на жёлтом фоне), а для изображения графа- количество пересечений небольшой окружности, проведённой около вершины, со всеми рёбрами:  по изображению графа находим, что вершина В имеет степень 5, а вершина Е – степень 4 в таблице есть ровно одна вершина, степень которой 5 (это П6) и одна вершина, степень которой – 4 (П4), их соединяет ребро длиной 20 (эти ячейки выделены в весовой матрице фиолетовым фоном). Ответ: 20. Бонус: попытаемся теперь определить, как обозначены остальные вершины в таблице. Каждая из вершин Д (степени 2) и Г (степени 3) соединена с уже известными вершинами В и Е, по таблице находим, что вершина Д – это П7, а вершина Г – это П2. Тогда вершина К соединяется с Е (П4) и Г (П2), то есть К – это П1. А вот различить вершины А и Б по этим данным не удаётся.  Ещё пример задания:Р-07. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта А в пункт Д. В ответе запишите целое число – так, как оно указано в таблице.  Решение: определим степени вершин по весовой матрице и по изображению графа (как в предыдущей задаче):  по изображению графа находим, что обе интересующих нас вершины, А и Д, имеют степени 3; кроме того, степень 3 имеет еще и вершина Г в таблице тоже есть три вершины со степенью 3 (это П1, П4 и П6), но вершина П1 (это вершина Г на рисунке!) не имеет общих ребёр с вершинами П4 и П6 (а это А и Д!); таким образом, ответ – это длина ребра между вершинами П4 и П6 (эти ячейки выделены в весовой матрице фиолетовым фоном). Ответ: 46. Бонус: вершины В и Е, имеющие степени 5 и 4, это П3 и П7; с вершиной Г (П1) связана ещё вершина К, имеющая степень 2 – это П5; с Е связана ещё вершина Д – это П6; тогда П4 – это А, а П2 – это Б.  Ещё пример задания:Р-06. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E и не проходящего через пункт B. Передвигаться можно только по указанным дорогам. Решение: поскольку нас интересуют только маршруты, НЕ проходящие через пункт В, столбец и строку, соответствующие этому пункту, можно удалить из таблицы:
дальше действуем так же, как показано при решении следующих далее разобранных задач; причем из всех маршрутов нужно оставить только те, которые проходят через пункт Е первый шаг от А (в скобках указаны длины маршрутов): АС (4), AD (8) прямой маршрут AF не рассматриваем, потому что он не проходит через пункт E второй шаг ACD (7), ADC (11), ADE (13) маршрут ADF не рассматриваем, потому что он не проходит через пункт E третий шаг: ACDE (12), ADEF (18) маршрут ADEF дошел до пункта назначения; маршрут ADC продолжать не имеет смысла, потому что из C можно проехать только в пункты A и D, где мы уже были; маршрут ACDF не рассматриваем, потому что он не проходит через пункт E четвертый шаг: ACDEF(17) этот маршрут тоже дошел до пункта назначения, его длина меньше, чем для предыдущего, его и выбираем Ответ: 17. |