Использование графов при решении задач. 9 класс

1. Использование графов при решении задач

9 класс
Использование графов
при решении задач
Нечкина Ю.С. / БОУ г. Омска «ШИСОО № 9 им. Д.Т. Язова»

2. Что такое «ГРАФ»?

Типичными графами являются:
• схемы авиалиний
• схемы метро

3. Задача 1

В таблице приведена стоимость перевозок между
населёнными
пунктами.
Укажите
граф,
соответствующий таблице.
4
2

4. Задача 2

На графе изображена схема дорог между селами и
обозначена стоимость перевозки одной тонны зерна между
соседними селами.
Укажите ячейку таблицы, в
которой допущена ошибка
(Пример: DC

5. Задача 3

6.

По таблице построим граф

7.

В
Выбираем кратчайший путь от А до Е.
1
А
2
1
5
С
АСЕ = 5+2=7
D
3
2
АВСЕ = 2+1+2=5
Е
АДСЕ = 1+3+3 = 7

8.

B
ABC= 80
ADC=85
BC=50
BADC = 115
DC=25
DABC=
EC=20
FEC = 55
50
30
C
A
20
25
60
D
E
75
GC=75
GFEC=60
35
F
G
5
≤