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

Слайд #1

Граф – множество точек (вершин), соединенных линиями (ребрами)
A
B
C
D
E
Ориентированный граф –
граф, в котором каждое ребро
имеет направление
A
B
C
D
E
Неориентированный граф –
граф, в котором ребра не имеют определенного направления
Использование графов при решении задач ОГЭ по информатике

Слайд #2

A
B
C
D
E
вершина
вершина
вершина
вершина
ребро
ребро
ребро
Ненаправленная (без стрелки) линия, соединяющая вершины графа, называется ребром.

Вершины неориентированного графа соединены ребрами.
Неориентированный граф

Слайд #3

вершина
A
B
C
D
E
вершина
вершина
вершина
дуга
дуга
дуга
Направленная (со стрелкой) линия называется дугой.
Вершины ориентированного графа соединены дугами.

Путь – это последовательность ребер (дуг), по которым можно перейти из одной вершины в другую. Например, A→B→C→E→D
Ориентированный граф

Слайд #4

ABCD: 2+1+4 = 7
Задача 1
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
 Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
А
E
C
D
B
2
4
5
1
4
3
3
ABCED: 2+1+3+3 = 9
ACD: 4+4 = 8
ACED: 4+3+3 = 10
AECD: 5+3+4 = 12
AED: 5+3 = 8
Ответ: 7
Решение:

Слайд #5

Задача 2
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. Определите длину кратчайшего пути между пунктами E и D, проходящего через пункт C (при условии, что передвигаться можно только по указанным в таблице дорогам). Каждый пункт можно посетить только один раз.
Ответ: 7
Решение:
А
E
C
D
B
1
2
4
6
7
EACD: 2 + 4 + 1 = 7
1
ECD: 7 + 1 = 8

Слайд #6

Задача 3.1
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
В = А = 1
Б = А + В = 1 + 1 = 2
1
2
Г = А + В = 1 + 1 = 2
2
Д = Б + В = 2 + 1 = 3
3
6
Е = Г + В + Д = 2 + 1 + 3 = 6
Ж = Д + Е = 3 + 6 = 9
9
Ответ: 9
Решение:

Слайд #7

Задача 3.2
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж, проходящих через пункт Д ?
В = А = 1
Б = А + В = 1 + 1 = 2
1
2
Д = Б + В = 2 + 1 = 3
3
3
Е = Д = 3 = 3
Ж = Д + Е = 3 + 3 = 6
6
Ответ: 6
Решение:

Слайд #8

Задача 3.3
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж, не проходящих через пункт Д?
В = А = 1
1
3
Г = А + В = 1 + 1 = 2
Ж = Е = 3
3
Ответ: 3
Решение:
Е = В + Г = 1 + 2 = 3
2

Слайд #9

Используемая литература:

1. Босова Л.Л., Босова А.Ю. Информатика. 9 класс: учебник. – М., Просвещение, 2022.

2. Образовательный портал для подготовки к экзаменам Сдам ГИА: Решу ОГЭ
(https://inf-oge.sdamgia.ru/)

3. Открытый банк заданий ОГЭ | Информатика
(https://oge.fipi.ru/bank/index.php)