9 класс
Использование графов при решении задач
Автор: Александрова З.В., учитель физики и информатики,
МБОУ СОШ №5 пгт Печенга, Мурманская область
2018 г.
Что такое «Граф»
Компьютерные сети
Схема метрополитена
Файловая система
Графический редактор
Генеалогическое древо
Граф – это совокупность непустого множества вершин и связей между вершинами.
Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – ребрами.
Виды графов
1. Ориентированный граф (кратко орграф ) — рёбрам которого присвоено направление.
2. Неориентированный граф - это граф, в котором нет направления линий.
3. Взвешенный граф – дуги или ребра имеют вес (дополнительная информация)
Если в графе вершины или рёбра характеризуются некоторой дополнительной информацией - весами вершин или рёбер, то такой граф называется ВЗВЕШЕННЫМ.
Два варианта значения слова «граф»
1) удобная форма описания структур типа дорожной сети или сети передачи данных;
2) математический объект
G := (V, E) ,
где V — это непустое множество вершин,
E — множество ребер (пар вершин).
Для описания графа часто используют квадратную таблицу, которая описывает все возможные связи между узлами (без учета дублирования) – матрицу.
А
А
Б
Б
В
5
В
5
Г
Г
8
11
11
8
3
3
7
7
ВЕСОВАЯ МАТРИЦА
Задача 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 числа
Задача 3.
На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
Б
Д
Ж
А
Г
Е
В
3. А-Б-Г-Ж
5. А-В-Б-Г-Д-Ж
7. А-В-Г-Д-Ж
9. А-В-Ж
1. А-Б-Д-Ж
4. А-В-Б-Д-Ж
6. А-В-Б-Г-Ж
8. А-В-Г-Ж
10. А-В-Е-Ж
2. А-Б-Г-Д-Ж
Ответ: 10 путей
Задача 4.
Задача 3.
У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо?
Задача 5.
Решение: Обозначим ученых вершинами графа и проведем от каждой вершины линии к четырем другим вершинам. Получаем 10 линий, которые и будут считаться рукопожатиями.
Задача 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
Задача 8.
(Самостоятельно)
Задача 9.
Задача 10.
(Самостоятельно)
Спасибо за работу на уроке!
