Третья задание в ГИА.
Данное задание относится к разделу информационного моделирования и представления информации.
Оно проверяет способность учащихся перейти от одной формы представления информации к другой. Очевидно, что для поставленной задачи, использование табличной формы представления информации - очень неудобно. Поэтому, в первую очередь необходимо перейти к другой форме. В данном случае нас будет интересовать граф.
Итак, граф - это форма представления информации, в которой объекты представлены в виде вершин, а отношения между объектами - в виде ребер. Графы бывают направленными и ненаправленными. В направленном графе по ребру можно двигаться только в одном направлении, в ненаправленном - в обоих.
Итак, обратимся к заданиям:
Задание 3. Демо-вариант ФИПИ.
Между населёнными пунктами A, B, C, D, E построены дороги,
протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | |
| A | 2 | 5 | 1 | ||
| B | 2 | 1 | |||
| C | 5 | 1 | 3 | 2 | |
| D | 1 | 3 | |||
| E | 2 |
Определите длину кратчайшего пути между пунктами A и Е. Передвигаться
можно только по дорогам, протяжённость которых указана в таблице.
1) 4
2) 5
3) 6
4) 7
Итак, построим граф. В вершинах поставим населенные пункты, а ребрами обозначим дороги с указанием расстояний:
Посмотрев на граф, мы видим, что существует 3 пути из пункта A в пункт E:
1. A->B->C->E
2. A->C->E
3. A->D->C->E
Теперь сложив расстояния получим для каждого из вариантов:
1. 5 км
2. 7 км
3. 6 км
Теперь становится ясно, что длина кратчайшего пути - 5 км, соответственно, правильным будет вариант ответа №2.
Рассмотрим задание 3 из диагностической работы Статград:
Между населёнными пунктами A, B, C, D, E, F построены дороги,
протяжённость которых приведена в таблице.
| A | B | C | D | E | F | |
| A | 8 | 3 | ||||
| B | 8 | 3 | ||||
| C | 3 | 4 | 3 | |||
| D | 3 | 1 | 3 | |||
| E | 4 | 1 | 2 | |||
| F | 3 | 3 | 2 |
Определите длину кратчайшего пути между пунктами A и D (при условии,
что передвигаться можно только по построенным дорогам).
1) 7
2) 8
3) 9
4) 11
Данная задача сложнее только тем, что тут больше пунктов. А большое тело, как известно, громче падает. То есть, данное задание не сложнее предыдущего.
Итак, рассмотрим все возможные пути из А в D:
1. A->B->D
2. A->C->E->D
3. A->C->F->E->D
4. A->C->F->D
5. A->C->E->F->D
Сложим длины дорог для каждого маршрута и получим:
1. 8+3 = 11 км
2. 3+4+1 = 8 км
3. 3+3+2+1 = 9 км
4. 3+3+3 = 9 км
5. 3+4+2+3 = 12 км.
Отсюда, кратчайший путь из A в D - 8 км, следовательно правильный вариант ответа - №2.
Ловушка: Можно поддаться искушению и, не прочитав задание, искать возможные пути из А в F.