a2
.pdf
A2
A2 (базовый уровень, время – 2 мин)
Тема: Использование информационных моделей (таблицы, диаграммы, графики).
Проверяемые элементы: Умение представлять и считывать данные в разных типах информационных моделей (схемы, карты,
таблицы, графики и формулы)
Теоретический материал:
Граф это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек.
1 / 67
A2
Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра - линиями, соединяющими точки.
Пустым называется граф без ребер. Полным называется граф, в котором каждые две вершины смежные.
Взвешенным называется граф, с каждым ребром которого связано некоторое число (вес), оно может обозначать, например, расстояние между городами или стоимость перевозки. Чаще всего взвешенный граф описывается в виде таблицы. Число, стоящее на пересечении строки и столбца, является весом данного ребра, а пустая клетка на пересечении строки и столбца означает, что ребра нет.
Пример 1:
2 / 67
A2
Ребро, соединяющее А и С, имеет вес 3, а ребра, соединяющего А и В, нет.
Маршрут в графе — это последовательность ребер, в которой конечная вершина всякого ребра, отличного от последнего, является начальной вершиной следующего.
Пример задания:
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
A
B
C
D
3 / 67
A2
E
F
A
2
4
B
2
4 / 67
A2
1
7
C
4
1
3
4
5 / 67
A2
D
3
3
E
7
4
3
6 / 67
A2
2
F
2
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
1) 9 |
2) 10 |
3) 11 |
4) 12 |
7 / 67
A2
Общий подход:
Построить граф, соответствующий таблице. Перебрать все возможные маршруты из A в F. Найти кратчайший путь.
Решение:
Возможные маршруты:
A - B - E - F = 11
A - B - C - E - F = 9
A - C - E - F = 10
A - C - D - E - F = 12
A - C - B - E - F = 14
А – В – C – D – Е = 12
8 / 67
A2
Ответ: 1) 9
Задачи для тренировки:
1) В таблицах приведена протяженность автомагистралей между соседними населенными пунктами. Если пересечение строки и столбца пусто, то соответствующие населенные пункты не соединены автомагистралями. Укажите номер таблицы, для которой выполняется условие «Максимальная протяженность маршрута от пункта А до пункта С не больше 5». Протяженность маршрута складывается из протяженности автомагистралей между соответствующими соседними населенными пунктами. При этом любой населенный пункт должен встречаться на маршруте не более одного раза.
1)
2)
3)
4)
A
B
9 / 67
A2
C
D
A
2
2
B
2
1
10 / 67