Презентация для подготовки к ОГЭ по информатике "Информационные модели (3 задание)" (9 класс)

Теория:

Граф — это группа объектов со связями между ними.

Объекты представляются как вершины графа ,

а связи — это линии соединяющие вершины.

Алгоритм построения графа:

1. На основании таблицы нужно построить граф всех возможных путей перемещения из начального пункта в конечный пункт.

2. Обозначить на схеме расстояние между пунктами.

3. Определить расстояние по каждому возможному пути.

Практическое решение задач с пояснением.

Задача № 1

Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:

A

A

B

B

C

1

1

C

D

D

E

2

E

2

2

2

7

7

3

3

4

4

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

1) 5 2) 6 3) 7 4) 8

Пояснение:

Найдём все варианты маршрутов из A в E и выберем самый короткий.

A—B—C—E : 1+2+3 = 6 км.

A—B—D—E : 1+2+4 = 7 км.

A—B—E : 1+7 = 8 км.

Правильный ответ № 2.

Задача № 2

Между населёнными пунк­та­ми А, В, С, D, Е по­стро­е­ны дороги, протяжённость ко­то­рых (в километрах) при­ве­де­на в таблице:

A

A

B

B

C

7

7

C

4

4

D

D

E

2

2

E

4

4

4

4

4

4

Определите длину крат­чай­ше­го пути между

пунк­та­ми А и E. Пе­ре­дви­гать­ся можно толь­ко по дорогам, протяжённость ко­то­рых ука­за­на в таблице.

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

Пояснение

Найдём все ва­ри­ан­ты марш­ру­тов из A в E и вы­бе­рем самый короткий.

A—B—C—D—E: 7+2+4+4=17 км.

A—B—E: 7+4=11 км.

A—C—D—E: 4+4+4=12 км.

A—C—B—E: 4+2+4=10 км.

Правильный ответ № 2.

Задача № 3

Между населёнными пунк­та­ми А, В, С, D, Е, F по­стро­е­ны дороги, протяжённость ко­то­рых (в километрах) при­ве­де­на в таблице:

A

A

B

B

C

6

C

6

D

4

4

D

2

E

1

E

1

2

F

1

F

1

3

3

1

1

1

1

6

6

Определите длину крат­чай­ше­го пути между пунк­та­ми А и F. Пе­ре­дви­гать­ся можно толь­ко по дорогам, протяжённость ко­то­рых указана в таблице.

1) 5 2) 6 3) 7 4) 4

Пояснение

Найдём все ва­ри­ан­ты маршрутов из A в E и вы­бе­рем самый короткий.

A—E—F: 1+6 = 7 км.

A—B—C—F : 6+1+1 = 8 км.

A—C—D—E—F: 4+3+1+6 = 14 км.

A—D—E—F: 2+1+6 = 9 км.

A—C—F: 4+1 = 5 км.

Правильный ответ № 1.

Задача № 4

Сельская ма­ло­ком­плект­ная школа на­хо­дит­ся в по­сел­ке Ивановское. Коля Ива­нов живёт в де­рев­не Вершки. Определите, какое ми­ни­маль­ное рас­сто­я­ние ему надо пройти, чтобы до­брать­ся до школы:

Борки

Борки

Вершки

Вершки

5

Красное

5

Красное

Дальнее

Дальнее

8

8

10

Дубово

Дубово

10

4

4

Ивановское

Ивановское

9

2

2

9

1

1

3

3

5

5

1) 6 2) 9 3) 12 4) 14

Пояснение

Найдём все ва­ри­ан­ты марш­ру­тов от де­рев­ни Верш­ки до по­сел­ка Ива­нов­ское и вы­бе­рем самый короткий.

(Борки ( Б ), Вершки ( В ), Красное ( К ), Дальнее ( Да ), Дубово ( Д ), Ивановское ( И ))

В—Б—К—И : 5+8+3 = 16 км.

В—Б—Да—И : 5+10+5 = 20 км.

В—Б—И: 5+9 = 14 км.

В—Да—И : 4+5 = 9 км.

В—Д—К—И: 2+1+3 = 6 км.

Правильный ответ № 1.

Задача № 5

Водитель ав­то­мо­би­ля дол­жен до­брать­ся из пунк­та А в пункт D за 5 часов. Из пред­став­лен­ных таб­лиц вы­бе­ри­те такую, со­глас­но ко­то­рой во­ди­тель смо­жет до­е­хать из пунк­та А в пункт D за это время. В ячей­ках таб­ли­цы ука­за­но время (в часах), ко­то­рое за­ни­ма­ет до­ро­га из од­но­го пунк­та в другой. Пе­ре­дви­гать­ся можно толь­ко по дорогам, ука­зан­ным в таблицах.

1 2

3 4

A

A

A

A

B

B

B

B

C

6

C

2

2

6

C

C

D

6

D

3

D

3

D

6

7

2

7

2

3

1

1

3

1

1

A

A

B

B

C

C

D

2

2

D

1

1

3

3

A

A

B

B

C

C

6

6

3

D

D

3

6

2

2

6

7

7

1) 1 2) 2 3) 3 4) 4

Пояснение

Найдём крат­чай­шие марш­ру­ты из A в D для каж­дой таблицы.

Исходя из пер­вой таблицы, крат­чай­ший марш­рут из A в D:

A—C—B—D , его можно пре­одо­леть за 6 часов.

Крат­чай­ший марш­рут из A в D для вто­рой таблицы:

A—B—D , его можно пре­одо­леть за 5 часов.

Для тре­тьей таб­ли­цы крат­чай­шая дорога:

A—C—B—D , она за­ни­ма­ет 6 часов.

Для четвёртой таб­ли­цы крат­чай­ший маршрут:

A—D , его можно пре­одо­леть за 6 часов.

Правильный ответ № 2.

Задача № 6

В таб­ли­це при­ве­де­на сто­и­мость пе­ре­во­зок между пятью же­лез­но­до­рож­ны­ми станциями, обо­зна­чен­ны­ми бук­ва­ми A, B, C, D, E. Ука­жи­те схему, со­от­вет­ству­ю­щую таблице.

A

A

B

B

C

C

1

1

1

1

D

D

2

2

E

E

3

3

5

2

2

5

4

4

1

3

4

2

Пояснение

Из таб­ли­цы видно, что из пунк­та A есть до­ро­ги в любой дру­гой пункт.

Следовательно, под­хо­дит толь­ко ва­ри­ант 2.

Правильный ответ № 2.