Презентация - Использование и анализ информационных моделей

Задание №1: Использование и анализ информационных моделей (таблицы, диаграммы, графики)
базовый уровень, правильное выполненное –1 балл, время – 1-3 мин.
Д.Е. Трофимов

Теоретические сведения:
Граф – это схема действий объектов, которые могут изображаться точками или геометрическими фигурами – вершины графа. Связи между объектами изображаются линиями – рёбра графа. Граф описывается в виде таблицы (матрицы смежности или весовой матрицы). Чаще всего используется взвешенный граф, где с каждым ребром связано некоторое число (вес). Оно может обозначать, например, расстояние между городами или стоимость перевозки. Такие рёбра называются дугами. Задание: необходимо определить длину дороги из одного пункта в другой, или номера населённых пунктов в таблице
Д.Е. Трофимов

Теоретические сведения:
Рассмотрим граф (рисунок слева), в котором 5 вершин (A, B, C, D и E); он описывается таблицей, расположенной в центре; в ней, например, число 4 на пересечении строки В и столбца С означает, что, во-первых, есть ребро, соединяющее В и С, и во-вторых, вес этого ребра равен 4; пустая клетка на пересечении строки А и столбца В означает, что ребра из А в В нет.
.A.B.C.D.Е
A...3.1.
B...4..2
C.3.4...2
D.1....
Е..2.2..
обратите внимание, что граф по заданной таблице (она еще называется весовой матрицей) может быть нарисован по-разному; например, той же таблице соответствует граф, показанный на рисунке справа от нее в приведенном примере матрица симметрична относительно главной диагонали; это может означать, например, что стоимости перевозки из В в С и обратно равны (это не всегда так) во многих задачах вес – это длина дороги из одного пункта в другой; для рассмотренного при-мера длина дороги из А в С равна 3, дороги из А в Е нет степень вершины – это количество рёбер, которые соединены с этой вершиной; при определении степени вершины по таблице нужно считать число непустых ячеек весовой матрицы в соответствующей строке (или столбце); в примере степень вершины А равна 2 (в первой строке две непустых ячейки со значениями 3 и 1)
Д.Е. Трофимов

Решение типовых задач
Д.Е. Трофимов

Задача 1
На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги из Б в пункт Г. ВНИМАНИЕ! Длины отрезков на схеме не отражают длины дорог.
Д.Е. Трофимов

Пояснение решения
Степени
1 (А)
1 (Д)
3 (В)
3 (Г)
1 (Б)
2 (Е)
1 (К)
Здесь видим, что есть таблица городов (где показаны расстояния), а так же схема городов. Но в таблице не подписано, где какой город. Нам нужно найти длину дороги из Б в пункт Г. 1) начнём решение с определения степени вершин на карте. Особой вершиной в нашем случае является город Е, т.к. в него входят две дороги, больше не у какого города нет двух дорог. Т.е. эта вершина явно отличается от всех остальных. 2) теперь эту вершину можно легко найти в таблице! Проходим построчно нашу таблицу и видим, что две дороги имеет только пункт П6 (Можно проверять и по столбикам). Значит, городу Е соответствует пункт П6. 3) города Г и В имеют по три дороги, но город Г соединён с городом Е (пунктом П6). Поэтому найдём в таблице "тройной город", но который содержит в себе П6. Это пункт П4. Значит, город Г - это П4. 4) теперь посмотрим на карту на город Б. Он "одинарный" и соединён с городом Г (т.е. с пунктом П4). По таблице видно, что это пункт П5. Значит, П5 - это Б. 5) теперь не сложно найти расстояние между пунктами Г и Б. Ищем по таблице число, где пересекаются пункты П4 и П5. Длина равна 15, это и будет ответ.
Ответ: 15.
Д.Е. Трофимов

Задача 2
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах)
.1.2.3.4.5.6.7
1....9...7
2....5..11.
3......12.
4.9.5...4.13.15
5....4..10.8
6..11.12.13.10..
7.7...15.8..
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта Г в пункт Ж. В ответе запишите целое число – так, как оно указано в таблице.
Д.Е. Трофимов

Пояснение решения
Степени
.1.2.3.4.5.6.7
1....9...7
2....5..11.
3......12.
4.9.5...4.13.15
5....4..10.8
6..11.12.13.10..
7.7...15.8..
2 (Г)
2 (В)
1 (А)
5 (Ж)
3 (Е)
4 (Б)
3 (Д)
1) определим для каждой вершины её степень, то есть, количество рёбер, в которыми она связана; в таблице степень вершины – это количество заполненных клеток в строке (или в столбце). 2) сопоставление степеней вершин в таблице и на рисунке позволяет сразу обнаружить в таблице вершины А (она имеет № 3), Ж (№ 4) и Б (№ 6) 3) нас интересуют вершины Г и Ж; вершину Ж мы нашли, вершина Г имеет степень 2 и связана, кроме вершины Ж, с вершиной Д степени 3; 4) степень 2 имеют вершины № 1 и 2, но только вершина № 1 связана, кроме Ж, с вершиной степени 3 (№ 7), поэтому вершина № 1 – это Г 5) по таблице определяем протяжённость дороги из пункта Г в пункт Ж, она равна 9.
Ответ: 9.
Д.Е. Трофимов

Задача 3
На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам A и G на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.
Д.Е. Трофимов

Пояснение решения
Степени
3 (B или D)
3 (B или D)
6 (F)
2 (C или E)
2 (C или E)
3 (A или G)
3 (A или G)
В этой задаче в таблице вместо конкретной длины показан сам факт дороги (или её отсутствие) между городами. 1) определим степени вершин. Вершина F является особой, т.к. только она имеет 6 дорог, а остальные меньше. Цифра 3 - это вершина F. 2) определим вершины C и E. Это легко сделать, т.к. они соединяются с вершиной F и имеют по 2 дороге. По две дороге имеют цифры 4 и 5. Мы точно не можем узнать, где конкретно C, а где E. Просто знаем, что именно эти цифры занимают данные буквы. Цифры 5 и 4 соединяются помимо F(3) c цифрами 1 и 2. Значит, цифры 1 и 2 - это вершины D и B (или B и D). 3) B и D соединены кроме вершины F(3) и "двойных" вершин, рассмотренных ранее, с нашими искомыми вершинами G и A. Из таблицы видно, что вершины G и A - это цифры 6 и 7 (или 7 и 6 ). Данная задача отличается тем, что приходится действовать в условиях не полной определённости. Тем не менее, мы нашли искомые цифры для букв G и A, просто не знаем их точный порядок. Нам в ответе нужно записать эти цифры в порядке возрастания. Ответ будет 67.
Ответ: 67.
Д.Е. Трофимов

Задача 4
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с бук-венными обозначениями на графе. Определите, какова длина дороги из пункта А в пункт Д. В ответе запишите целое число – так, как оно указано в таблице.
Д.Е. Трофимов

Пояснение решения
1) определим степени вершин по весовой матрице и по изображению графа (как в предыдущей задаче) 2) по изображению графа находим, что обе интересующих нас вершины, А и Д, имеют степени 3; кроме того, степень 3 имеет еще и вершина Г 3) в таблице тоже есть три вершины со степенью 3 (это П1, П4 и П6), но вершина П1 (это вер-шина Г на рисунке!) не имеет общих рёбер с вершинами П4 и П6 (а это А и Д!); 4) таким образом, ответ – это длина ребра между вершинами П4 и П6 (эти ячейки выделены в весовой матрице фиолетовым фоном). 5) Ответ: 46
Ответ: 46.
Д.Е. Трофимов

Задача 5
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E и не проходящего через пункт B. Передвигаться можно только по указанным дорогам.
Д.Е. Трофимов

Пояснение решения
1) поскольку нас интересуют только маршруты, НЕ проходящие через пункт В, столбец и строку, соответствующие этому пункту, можно удалить из таблицы:
A
C
D
D
C
E
F
E
F
2) для дальнейшего решения необходимо построить граф типа «дерево»; причем из всех маршрутов нужно оставить только те, которые проходят через пункт Е 3) первый шаг от А (в скобках указаны длины маршрутов): АС (4), AD (8) прямой маршрут AF не рассматриваем, потому что он не проходит через пункт E 4) второй шаг: ACD (7), ADC (11), ADE (13) маршрут ADF не рассматриваем, потому что он не проходит через пункт E 5) третий шаг: ACDE (12), ADEF (18) маршрут ADEF дошел до пункта назначения; маршрут ADC продолжать не имеет смысла, потому что из C можно проехать только в пункты A и D, где мы уже были; маршрут ACDF не рассматриваем, потому что он не проходит через пункт E 6) четвертый шаг: ACDEF(17) 7) этот маршрут тоже дошел до пункта назначения, его длина меньше, чем для предыдущего, его и выбираем 8) Ответ: 17.
Ответ: 17.
Д.Е. Трофимов