PDF Печать E-mail

 A2 (базовый уровень, время – 2 мин)

 

Тема:  Использование информационных моделей (таблицы, диаграммы, графики). 

 

Проверяемые элементыУмение представлять и считывать данные в разных типах информационных моделей (схемы, карты,

таблицы, графики и формулы)

 

Теоретический материал: 

 

 Граф это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. 

 

Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра - линиями, соединяющими точки.

 

 

Пустым называется граф без ребер. Полным называется граф, в котором каждые две вершины смежные.

 

Взвешенным называется  граф, с каждым ребром которого связано некоторое число (вес), оно может обозначать, например, расстояние между городами или стоимость перевозки. Чаще всего взвешенный граф описывается в виде таблицы. Число, стоящее на пересечении строки и столбца, является весом данного ребра, а пустая клетка на пересечении строки и столбца означает, что ребра нет.

 

Пример 1:

Ребро, соединяющее А и С, имеет вес 3, а ребра, соединяющего А и В, нет. 


 

Маршрут в графе — это последовательность ребер, в которой конечная вершина всякого ребра, отличного от последнего, является начальной вершиной следующего. 

 

Пример задания:

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

 

A

B

C

D

E

F

A

 

2

4

 

 

 

B

2

 

1

 

7

 

C

4

1

 

3

4

 

D

 

 

3

 

3

 

E

 

7

4

3

 

2

F

 

 

 

 

2

 

 Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).  

 1) 9                       2) 10                         3) 11                            4) 12

Общий подход: 

Построить граф, соответствующий таблице. Перебрать все возможные маршруты из 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

Ответ: 1) 9 

 

Задачи для тренировки:

1)      В таблицах приведена протяженность автомагистралей между соседними населенными пунктами. Если пересечение строки и столбца пусто, то соответствующие населенные пун­кты не соединены автомагистралями. Укажите номер таблицы, для которой выполняется условие «Максимальная протяженность маршрута от пункта А до пункта С не больше 5». Протяженность маршрута складывается из протяженности автомагистралей между соответствующими соседними населенными пунктами. При этом любой населенный пункт должен встречаться на маршруте не более одного раза.

1)

2)

3)

4)

 

A

B

C

D

A

 

2

 

2

B

2

 

1

3

C

 

1

 

3

D

2

3

3

 

 

 

A

B

C

D

A

 

2

2

 

B

2

 

1

1

C

2

1

 

3

D

 

1

3

 

 

 

A

B

C

D

A

 

2

3

2

B

2

 

2

2

C

3

2

 

 

D

2

2

 

 

 

 

A

B

C

D

A

 

3

2

1

B

3

 

2

 

C

2

2

 

1

D

1

 

1

 

 

2)      В таблицах приведена протяженность автомагистралей между соседними населенными пунктами. Если пересечение строки и столбца пусто, то соответствующие населенные пункты не являются соседними. Укажите номер таблицы, для которой выполняется условие «Максимальная протяженность маршрута от пункта А до пункта С не больше 6». Протяженность маршрута складывается из протяженности автомагистралей между соответствующими соседними населенными пунктами. При этом через любой насеченный пункт маршрут должен проходить не более одного раза.

1)

2)

3)

4)

 

 

 

A

B

C

D

A

 

1

 

2

B

1

 

4

3

C

 

4

 

3

D

2

3

3

 

 

 

A

B

C

D

A

 

1

2

 

B

1

 

4

2

C

2

4

 

3

D

 

2

3

 

 

 

A

B

C

D

A

 

3

3

2

B

3

 

4

3

C

3

4

 

 

D

2

3

 

 

 

 

A

B

C

D

A

 

3

2

1

B

3

 

4

 

C

2

4

 

1

D

1

 

1

 

 

         

3)      В таблицах приведена протяженность автомагистралей между соседними населенными пунктами. Если пересечение строки и столбца пусто, то соответствующие населенные пункты не являются соседними. Укажите номер таблицы, для которой выполняется условие «Максимальная протяженность маршрута от пункта C до пункта B не больше 6». Протяженность маршрута складывается из протяженности автомагистралей между соответствующими соседними населенными пунктами. При этом через любой насеченный пункт маршрут должен проходить не более одного раза.

1)

2)

3)

4)

 

A

B

C

D

E

A

 

4

3

 

7

B

4

 

 

2

 

C

3

 

 

6

 

D

 

2

6

 

1

E

7

 

 

1

 

 

 

A

B

C

D

E

A

 

2

5

 

6

B

2

 

 

3

 

C

5

 

 

 

 

D

 

3

 

 

1

E

6

 

 

1

 

 

 

A

B

C

D

E

A

 

 

2

2

6

B

 

 

 

2

 

C

2

 

 

2

 

D

2

2

2

 

 

E

6

 

 

 

 

 

 

A

B

C

D

E

A

 

5

2

 

6

B

5

 

 

5

 

C

2

 

 

2

 

D

 

5

2

 

3

E

6

 

 

3

 

 

 

4)      Турист-паломник должен добраться из МУРМАНСКА в КИЕВ. Автобусная компания предложила ему следующий список маршрутов, которые проходят через города: МУРМАНСК, КИЕВ, МОСКВУ и СМОЛЕНСК.

         

Пункт отправления

Пункт прибытия

Стоимость (у.е.)

Число монастырей

МУРМАНСК

КИЕВ

200

81

МУРМАНСК

МОСКВА

100

10

МУРМАНСК

СМОЛЕНСК

110

30

МОСКВА

КИЕВ

60

7

МОСКВА

МУРМАНСК

100

9

МОСКВА

СМОЛЕНСК

20

15

СМОЛЕНСК

КИЕВ

40

15

СМОЛЕНСК

МОСКВА

30

15

КИЕВ

МОСКВА

60

7

КИЕВ

СМОЛЕНСК

35

10

КИЕВ

МУРМАНСК

190

37

В таблице путешественник указал для себя количество монастырей, мимо которых будет проезжать автобус. Помогите путешественнику добраться в пункт назначения, затратив на дорогу не более 190 у.е. и увидев максимальное количество монастырей. В ответе укажите маршрут паломника:

1) МУРМАНСК – СМОЛЕНСК – КИЕВ

2) МУРМАНСК – МОСКВА – КИЕВ        

3) МУРМАНСК – МОСКВА – СМОЛЕНСК – КИЕВ                 

4) МУРМАНСК – СМОЛЕНСК – МОСКВА – КИЕВ

 

5)     Между городами МОСКВА, САМАРА, РЯЗАНЬ и СОЧИ ежедневно ходят поезда. В таблице приведен фрагмент расписания:

Отправление из 

Прибытие в             

  Время отправления   

 Время в пути (ч)

МОСКВА

РЯЗАНЬ

 10:00

3

МОСКВА

РЯЗАНЬ

13:00

3

МОСКВА

САМАРА

11:00

12

МОСКВА

СОЧИ

11:00

20

САМАРА

РЯЗАНЬ

12:00

10

САМАРА

СОЧИ

14:00

20

САМАРА

МОСКВА

10:00

12

РЯЗАНЬ

САМАРА

15:00

10

РЯЗАНЬ

МОСКВА

10:00

3

СОЧИ

МОСКВА

10:00

22

СОЧИ

САМАРА

11:00

20

Известно, что ни один маршрут не проходит через перечисленные города. Пассажир оказался в 9 часов утра 1 июня в МОСКВЕ. Определите самое раннее время, когда он может попасть в СОЧИ:

1) 2 июня 7:00     2) 2 июня 9:00               3) 2 июня 14:00       4) 2 июня 23:00 

 

6)      Между четырьмя местными аэропортами: ПОЛЕВОЕ, СОКОЛИНОЕ, ГРИГОРЬЕВО и ЛИПКИ, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними:

Аэропорт вылета

Аэропорт прилета

Время вылета

Время прилета

ГРИГОРЬЕВО

ПОЛЕВОЕ

09:30

10:15

ПОЛЕВОЕ

СОКОЛИНОЕ

10:30

11:20

ЛИПКИ

ГРИГОРЬЕВО

10:45

11:25

ПОЛЕВОЕ

ГРИГОРЬЕВО

11:00

11:45

СОКОЛИНОЕ

ПОЛЕВОЕ

11:15

12:05

ПОЛЕВОЕ

ЛИПКИ

11:55

13:40

ЛИПКИ

СОКОЛИНОЕ

12:00

12:55

СОКОЛИНОЕ

ЛИПКИ

12:10

13:55

ЛИПКИ

ПОЛЕВОЕ

12:15

14:00

ГРИГОРЬЕВО

ЛИПКИ

12:55

13:35

 

Путешественник оказался в аэропорту ПОЛЕВОЕ в полночь. Определите самое раннее время, когда он может попасть в аэропорт ЛИПКИ. Считается, что путешественник успевает совершить пересадку в аэропорту, если между временем прилета в этот аэропорт и временем вылета проходит не менее часа.

1) 12:55                   2) 13:35                            3) 13:40                      4) 14:00

7)      Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 

A

B

C

D

E

F

A

 

4

 

 

 

 

B

4

 

6

3

6

 

C

 

6

 

 

4

 

D

 

3

 

 

2

 

E

 

6

4

2

 

5

F 

 

 

 

 

5

 

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

1) 9                        2) 13                         3) 14                            4) 15

8)      (http://ege.yandex.ru) Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 

A

B

C

D

E

F

A

 

 

3

 

 

 

B

 

 

9

 

4

 

C

3

9

 

3

8

 

D

 

 

3

 

2

 

E

 

4

8

2

 

7

F

 

 

 

 

7

 

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

1) 11                     2) 13                         3) 15                            4) 17 

 

Назад в меню

 
 
belovo-lyceum22.ru , Powered by Joomla 1.5 and designed by joomlaworld.ru