А2 ЕГЭ А3 ГИА Графы, диаграммы, графики.
(базовый уровень, время – 2 мин)
Тема: Использование информационных моделей (таблицы, диаграммы, графики).
Перебор вариантов, выбор лучшего по какому-то признаку.
Для решения з
адач данного типа не нужны никакие знания по информатике, кроме здравого смысла и умения перебирать варианты:
- полезно знать, что такое граф (это набор вершин и соединяющих их ребер) и как он описывается в виде таблицы, хотя, как правило, все необходимые объяснения даны в формулировке задания
- рассмотрим граф (рисунок слева), в котором 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 |
|
|
Задачи на определение кратчайшего пути
Пример 1 А2 Демо ЕГЭ 2013г Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
1)11 2)12 3)13 4) 18
Решение:
Изобразим с помощью графа данные таблицы. Точками обозначим населенные пункты. Там, где пункты соединены дорогой, там соединяем точки.
Нарисуем путь из пункта А в F. Начнем с конца, с пункта F. В него идет дорога из Е:
в пункт Е ведут дороги из B, C и D:
В пункт B ведет дорога из A, в пункт С ведет дорога из В, в пункт D ведет дорога из B:
В пункт В ведет дорога из А:
Видим, что из А в F ведет 3-и пути. Надо найти кратчайший путь из трех. Добавим в граф значение расстояний между пунктами:
1-й путь: A−B−E−F=3+7+3=13
2-й путь: A−B−C−E−F=3+7+5+3=18
3-й путь: A−B−D−E−F=3+4+2+3=12
Получили кратчайший путь: A−B−D−E−F. Его длина равна 12.
Задачи на соответствие между таблицей и графом
Пример 1. В таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую таблице.
|
|
|
|
|
|
|
|
|
3 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 1) | 2) | 3) | 4) |
 |
 |
 |
 |
Решение
Будем проверять каждое значение в таблице на соответствие по графу, отбрасывая неподходящие варианты.
- =3, Не подходят графы 1), 3)
А=1, 2)и 4) графы оба подходят
АВ=ВА этот вариант мы уже проверяли
ВС=2, оба графа 2) и 4) подходят
В=1, оба графа 2) и 4) подходят
СВ=ВС, этот вариант мы уже проверяли
СВ=4, не подходит 2)
Остается вариант 4
Ответ 4