Решение задач с помощью деревьев. 9 класс

1. Решение задач с помощью деревьев

1
Решение задач с
помощью
деревьев
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

2. Дерево – это граф?

Моделирование, 9 класс
2
Дерево – это граф?
!
Дерево – это связный граф без
циклов (замкнутых путей).
A
A
C
B
D
B
ABC
BCD
D
ABDC
CCC…
К.Ю. Поляков, Е.А. Ерёмин, 2018
H
C
E
F
G
J
дерево
http://kpolyakov.spb.ru

3. Кратчайший путь (перебор)

Моделирование, 9 класс
3
Кратчайший путь (перебор)
A B
2
A
B 2
C 4 1
D
E 6
C D E
4
6
1
5 1
5
3
1 3
1) Определите кратчайший путь
между пунктами A и D.
A
2
B
4
С
2
6
E
4
1
С
5
D
8
1
С
3
6
3
7
D
9
1
E
4
3
дерево возможных
путей
К.Ю. Поляков, Е.А. Ерёмин, 2018
D
7
http://kpolyakov.spb.ru

4. Кратчайший путь

Моделирование, 9 класс
4
Кратчайший путь
A B
2
A
B 2
C 4 1
D
7
E
C D E
4
1
7
3 5
3
3
5 3
К.Ю. Поляков, Е.А. Ерёмин, 2018
2) Решите задачу. Дерево
зарисовать в тетради.
Определите кратчайший
путь между пунктами A и E.
http://kpolyakov.spb.ru

5. Проверка задачи 2)

Моделирование, 9 класс
5
Проверка задачи 2)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

6. Кратчайший путь

Моделирование, 9 класс
6
Кратчайший путь
A B
A
B
C 3
D 1
E
4
C D E
3 1
4
2
2
2
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
3) Решите задачу. Дерево
зарисовать в тетради.
Определите кратчайший
путь между пунктами A и B.
http://kpolyakov.spb.ru

7. Ответ к задаче 3

Моделирование, 9 класс
7
Ответ к задаче 3
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

8. Кратчайший путь

Моделирование, 9 класс
8
Кратчайший путь
A B
A
B
C 3
D 1
E 1
4
C D E
3 1 1
4
2
4) Определите кратчайший
путь между пунктами A и B.
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

9. Ответ к 4 задаче

Моделирование, 9 класс
9
Ответ к 4 задаче
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

10. Кратчайший путь

Моделирование, 9 класс
10
Кратчайший путь
A B
A
B
C 3
D 1
E 4
4
C D E
3 1 4
4
2
2
2
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
5) Решите задачу. Дерево
зарисовать в тетради.
Определите кратчайший
путь между пунктами A и B.
http://kpolyakov.spb.ru

11. Ответ к задаче 5 :

Моделирование, 9 класс
11
Ответ к задаче 5 :
А-Е-В = 6 км
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

12. Кратчайший путь

Моделирование, 9 класс
12
Кратчайший путь
A B
A
B
C
D 1
E
4
1
C D E
1
4
1
4 2
4
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
6) Решите задачу. Дерево
зарисовать в тетради.
Определите кратчайший
путь между пунктами A и B.
http://kpolyakov.spb.ru

13. Ответ к задаче 6 :

Моделирование, 9 класс
13
Ответ к задаче 6 :
А – D – C – E - B: 8 км
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

14. Самостоятельное решение задач (тренируемся)

Моделирование, 9 класс
14
Самостоятельное решение задач
(тренируемся)
Сайт «Решу ОГЭ», вариант учителя
12885914
или по ссылке:
https://infoge.sdamgia.ru/test?id=12844600&nt=False&
pub=1
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru