Презентация «Готовимся к ОГЭ по информатике. Задание 4»

ОГЭ по информатике

Часть 1. Задание 4

Справочная информация

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

Графы – графические информационные модели для отображения систем.

Объекты системы изображаются вершинами , а связи между ними – линиями ( рёбрами ).

У взвешенного графа вершины или рёбра характеризуются некоторой дополнительной информацией – весами вершин или рёбер.

Цепь – это путь по вершинам и рёбрам графа, в который любое ребро графа входит только один раз (C-D-E).

Цикл – цепь, начальная и конечная вершины которой совпадают (C-D-E-C).

Сеть – граф с циклом.

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

корень

C

A

80

D

90

C

B

B

60

70

50

E

D

E

A

90

Взвешенный граф

Иерархический граф (дерево)

Справочная информация

Табличные информационные модели представляют информацию об объектах в наглядной форме в виде прямоугольной таблицы, состоящей из столбцов и строк.

Таблица типа «объект - объект» – это таблица, содержащая информацию о некотором одном свойстве пар объектов одного или разных классов.

Например, приведенный ранее взвешенный граф может быть схемой дорог, соединяющих населённые пункты A, B, C, D, E.

Этому графу соответствует следующая таблица ( весовая матрица ):

Одной и той же таблице могут соответствовать графы, внешне не похожие друг на друга:

C

80

А

А

В

В

С

50

С

50

D

D

Е

90

Е

90

90

90

80

80

60

60

70

70

D

C

A

90

80

90

B

60

70

D

50

60

50

E

90

A

E

B

70

90

4-1

Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами А и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.

А

А

В

В

С

С

2

2

5

D

5

D

1

3

1

Е

3

Е

3

3

2

2

Решение.

По данным таблицы (весовой матрицы) построим граф. Так как таблица симметрична относительно диагонали, будем рассматривать только её половину. Например, выше диагонали.

А

А

В

В

С

2

С

2

5

5

D

D

3

Е

1

1

Е

3

3

3

2

2

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

4-1

Из вершины A рёбра в вершины B, C, D с весами соответственно 2, 5, 1.

А

А

В

В

2

С

С

2

D

5

D

5

Е

1

3

3

1

Е

3

3

2

2

Из вершины B ребро в вершину C с весом 3.

Из вершины C рёбра в вершины D, E с весами соответственно 3, 2.

Из вершины D рёбер в другие вершины нет (кроме уже рассмотренных).

Для удобства перерисуем граф в более наглядном виде:

2

2

B

A

A

B

E

5

1

5

1

2

3

3

3

3

2

D

C

C

D

E

Проанализируем все возможные пути из A в E:

ABCE = 2+3+2 = 7

ACE = 5+2 = 7

ADCE = 1+3+2 = 6

Кратчайшим путём является путь ADCE протяжённостью 6.

Ответ: 6.

4-2

Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами А и Е, проходящего через пункт С. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.

А

А

В

В

1

С

1

С

4

D

D

4

2

3

Е

2

3

Е

7

5

5

7

3

3

2

2

Решение.

По данным таблицы построим граф:

1

Нам нужно определить длину кратчайшего пути между пунктами А и Е, проходящего через пункт С, при этом каждый пункт можно посетить только один раз.

Разобьём задачу на две подзадачи. Найдём отдельно кратчайший путь между пунктами A и C, затем между пунктами C и E.

Перебирая возможные варианты, определяем кратчайшие пути:

ABC = 1+2 = 3

CDE = 3+2 = 5

Тогда искомый путь ABCDE = 3+5 = 8.

A

B

7

5

E

3

2

4

2

3

D

C

Ответ: 8.

4-3

Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами А и F, проходящего через пункт С. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.

А

А

В

В

С

С

3

3

5

5

D

D

1

1

Е

Е

4

4

F

F

15

2

2

15

3

9

3

9

6

6

4

4

Решение.

По данным таблицы построим граф:

3

B

A

Нам нужно определить длину кратчайшего пути между пунктами А и F, проходящего через пункт С, при этом каждый пункт можно посетить только один раз. Разобьём задачу на две подзадачи.

Найдём отдельно кратчайший путь между пунктами A и C, затем между пунктами C и F.

Перебирая возможные варианты, определяем кратчайшие пути:

ABC = 3+1 = 4

CDF = 2+6 = 8

Тогда искомый путь ABCDF = 4+8 = 12.

5

1

C

15

4

9

2

6

F

D

4

3

E

Ответ: 12.

4-4

Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами А и F, проходящего через пункт С. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.

А

А

В

В

3

С

С

3

D

5

D

5

2

2

Е

1

1

Е

F

F

5

3

6

3

6

5

7

7

2

2

7

7

4

4

Решение. По данным таблицы построим граф:

3

A

B

6

Нам нужно определить длину кратчайшего пути между пунктами А и F, проходящего через пункт С, при этом каждый пункт можно посетить только один раз.

Разобьём задачу на две подзадачи. Найдём отдельно кратчайший путь между пунктами A и C, затем между пунктами C и F.

Перебирая возможные варианты, определяем кратчайшие пути:

ABC = 3+1 = 4

CDEF = 3+2+4 = 9

Тогда искомый путь ABCDEF = 4+9 = 13.

1

5

2

F

C

4

3

5

2

D

E

7

7

Ответ: 13.