Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

/ a2

.pdf
Скачиваний:
1
Добавлен:
30.05.2015
Размер:
460.09 Кб
Скачать

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]