![9 класс Использование графов при решении задач Автор: Александрова З.В., учитель физики и информатики, МБОУ СОШ №5 пгт Печенга, Мурманская область 2018 г.](http://fsd.compedu.ru/html/2018/11/06/i_5be1bf3bde0aa/img_phpwO3fDO_GRAFY-pri-reshenii-zadach-9-kl-AZV-2018_0.jpg)
9 класс
Использование графов при решении задач
Автор: Александрова З.В., учитель физики и информатики,
МБОУ СОШ №5 пгт Печенга, Мурманская область
2018 г.
![Что такое «Граф» Компьютерные сети Схема метрополитена Файловая система Графический редактор Генеалогическое древо](http://fsd.compedu.ru/html/2018/11/06/i_5be1bf3bde0aa/img_phpwO3fDO_GRAFY-pri-reshenii-zadach-9-kl-AZV-2018_1.jpg)
Что такое «Граф»
Компьютерные сети
Схема метрополитена
Файловая система
Графический редактор
Генеалогическое древо
![Граф – это совокупность непустого множества вершин и связей между вершинами. Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – ребрами.](http://fsd.compedu.ru/html/2018/11/06/i_5be1bf3bde0aa/img_phpwO3fDO_GRAFY-pri-reshenii-zadach-9-kl-AZV-2018_2.jpg)
Граф – это совокупность непустого множества вершин и связей между вершинами.
Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – ребрами.
![Виды графов 1. Ориентированный граф (кратко орграф ) — рёбрам которого присвоено направление. 2. Неориентированный граф - это граф, в котором нет направления линий. 3. Взвешенный граф – дуги или ребра имеют вес (дополнительная информация)](http://fsd.compedu.ru/html/2018/11/06/i_5be1bf3bde0aa/img_phpwO3fDO_GRAFY-pri-reshenii-zadach-9-kl-AZV-2018_3.jpg)
Виды графов
1. Ориентированный граф (кратко орграф ) — рёбрам которого присвоено направление.
2. Неориентированный граф - это граф, в котором нет направления линий.
3. Взвешенный граф – дуги или ребра имеют вес (дополнительная информация)
![Если в графе вершины или рёбра характеризуются некоторой дополнительной информацией - весами вершин или рёбер, то такой граф называется ВЗВЕШЕННЫМ.](http://fsd.compedu.ru/html/2018/11/06/i_5be1bf3bde0aa/img_phpwO3fDO_GRAFY-pri-reshenii-zadach-9-kl-AZV-2018_4.jpg)
Если в графе вершины или рёбра характеризуются некоторой дополнительной информацией - весами вершин или рёбер, то такой граф называется ВЗВЕШЕННЫМ.
![Два варианта значения слова «граф» 1) удобная форма описания структур типа дорожной сети или сети передачи данных; 2) математический объект G := (V, E) , где V — это непустое множество вершин, E — множество ребер (пар вершин).](http://fsd.compedu.ru/html/2018/11/06/i_5be1bf3bde0aa/img_phpwO3fDO_GRAFY-pri-reshenii-zadach-9-kl-AZV-2018_5.jpg)
Два варианта значения слова «граф»
1) удобная форма описания структур типа дорожной сети или сети передачи данных;
2) математический объект
G := (V, E) ,
где V — это непустое множество вершин,
E — множество ребер (пар вершин).
![Для описания графа часто используют квадратную таблицу, которая описывает все возможные связи между узлами (без учета дублирования) – матрицу. А А Б Б В 5 В 5 Г Г 8 11 11 8 3 3 7 7 ВЕСОВАЯ МАТРИЦА](http://fsd.compedu.ru/html/2018/11/06/i_5be1bf3bde0aa/img_phpwO3fDO_GRAFY-pri-reshenii-zadach-9-kl-AZV-2018_6.jpg)
Для описания графа часто используют квадратную таблицу, которая описывает все возможные связи между узлами (без учета дублирования) – матрицу.
А
А
Б
Б
В
5
В
5
Г
Г
8
11
11
8
3
3
7
7
ВЕСОВАЯ МАТРИЦА
![Задача 1.](http://fsd.compedu.ru/html/2018/11/06/i_5be1bf3bde0aa/img_phpwO3fDO_GRAFY-pri-reshenii-zadach-9-kl-AZV-2018_7.jpg)
Задача 1.
![Задача 2. Сколько трехзначных чисел можно записать с помощью цифр 1, 3, 5, 7 при условии, что в записи числа не должно быть одинаковых цифр? 0 1 3 5 7 7 1 1 7 5 5 5 3 1 7 3 3 1 5 7 3 7 5 1 5 3 3 1 7 1 7 3 5 1 7 1 7 5 5 3 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 Ответ: 24 числа](http://fsd.compedu.ru/html/2018/11/06/i_5be1bf3bde0aa/img_phpwO3fDO_GRAFY-pri-reshenii-zadach-9-kl-AZV-2018_8.jpg)
Задача 2.
Сколько трехзначных чисел можно записать с помощью
цифр 1, 3, 5, 7 при условии, что в записи числа не должно
быть одинаковых цифр?
0
1
3
5
7
7
1
1
7
5
5
5
3
1
7
3
3
1
5
7
3
7
5
1
5
3
3
1
7
1
7
3
5
1
7
1
7
5
5
3
3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
Ответ: 24 числа
![Задача 3. На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж? Б Д Ж А Г Е В 3. А-Б-Г-Ж 5. А-В-Б-Г-Д-Ж 7. А-В-Г-Д-Ж 9. А-В-Ж 1. А-Б-Д-Ж 4. А-В-Б-Д-Ж 6. А-В-Б-Г-Ж 8. А-В-Г-Ж 10. А-В-Е-Ж 2. А-Б-Г-Д-Ж Ответ: 10 путей](http://fsd.compedu.ru/html/2018/11/06/i_5be1bf3bde0aa/img_phpwO3fDO_GRAFY-pri-reshenii-zadach-9-kl-AZV-2018_9.jpg)
Задача 3.
На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
Б
Д
Ж
А
Г
Е
В
3. А-Б-Г-Ж
5. А-В-Б-Г-Д-Ж
7. А-В-Г-Д-Ж
9. А-В-Ж
1. А-Б-Д-Ж
4. А-В-Б-Д-Ж
6. А-В-Б-Г-Ж
8. А-В-Г-Ж
10. А-В-Е-Ж
2. А-Б-Г-Д-Ж
Ответ: 10 путей
![Задача 4.](http://fsd.compedu.ru/html/2018/11/06/i_5be1bf3bde0aa/img_phpwO3fDO_GRAFY-pri-reshenii-zadach-9-kl-AZV-2018_10.jpg)
Задача 4.
![Задача 3. У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо?](http://fsd.compedu.ru/html/2018/11/06/i_5be1bf3bde0aa/img_phpwO3fDO_GRAFY-pri-reshenii-zadach-9-kl-AZV-2018_11.jpg)
Задача 3.
У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо?
![Задача 5. Решение: Обозначим ученых вершинами графа и проведем от каждой вершины линии к четырем другим вершинам. Получаем 10 линий, которые и будут считаться рукопожатиями.](http://fsd.compedu.ru/html/2018/11/06/i_5be1bf3bde0aa/img_phpwO3fDO_GRAFY-pri-reshenii-zadach-9-kl-AZV-2018_12.jpg)
Задача 5.
Решение: Обозначим ученых вершинами графа и проведем от каждой вершины линии к четырем другим вершинам. Получаем 10 линий, которые и будут считаться рукопожатиями.
![Задача 6. Определить кратчайшее расстояние между наиболее удаленными друг от друга пунктами. А – В ? А А Б Б 5 В В 5 Г Г 8 11 11 8 3 3 7 7 А 5 8 Г Б 11 3 В Г 7 В 5+3+7 = 15](http://fsd.compedu.ru/html/2018/11/06/i_5be1bf3bde0aa/img_phpwO3fDO_GRAFY-pri-reshenii-zadach-9-kl-AZV-2018_13.jpg)
Задача 6.
Определить кратчайшее расстояние между наиболее удаленными друг от друга пунктами.
А – В ?
А
А
Б
Б
5
В
В
5
Г
Г
8
11
11
8
3
3
7
7
А
5
8
Г
Б
11
3
В
Г
7
В
5+3+7 = 15
![Задача 7. 1. Определение вершины. 2. Построение графа. A 3 B,3 4 D,4 7 E,2 7 2 C,7 3 F,12 E,7 3 5 E,5 F,13 3 3. Ответ ABDEF=12 F,18](http://fsd.compedu.ru/html/2018/11/06/i_5be1bf3bde0aa/img_phpwO3fDO_GRAFY-pri-reshenii-zadach-9-kl-AZV-2018_14.jpg)
Задача 7.
1. Определение вершины.
2. Построение графа.
A
3
B,3
4
D,4
7
E,2
7
2
C,7
3
F,12
E,7
3
5
E,5
F,13
3
3. Ответ ABDEF=12
F,18
![Задача 8.](http://fsd.compedu.ru/html/2018/11/06/i_5be1bf3bde0aa/img_phpwO3fDO_GRAFY-pri-reshenii-zadach-9-kl-AZV-2018_15.jpg)
Задача 8.
![(Самостоятельно) Задача 9.](http://fsd.compedu.ru/html/2018/11/06/i_5be1bf3bde0aa/img_phpwO3fDO_GRAFY-pri-reshenii-zadach-9-kl-AZV-2018_16.jpg)
(Самостоятельно)
Задача 9.
![Задача 10. (Самостоятельно)](http://fsd.compedu.ru/html/2018/11/06/i_5be1bf3bde0aa/img_phpwO3fDO_GRAFY-pri-reshenii-zadach-9-kl-AZV-2018_17.jpg)
Задача 10.
(Самостоятельно)
![Спасибо за работу на уроке!](http://fsd.compedu.ru/html/2018/11/06/i_5be1bf3bde0aa/img_phpwO3fDO_GRAFY-pri-reshenii-zadach-9-kl-AZV-2018_18.jpg)
Спасибо за работу на уроке!