Презентация - Использование графов при решении задач (11.04.2019)

Нажмите для просмотра
Использование графов при решении задач (11.04.2019)
Распечатать
  • Последний IP: 188.225.77.64
  • Уникальность: 99%
  • Слайдов: 19
  • Просмотров: 4997
  • Скачиваний: 3210
  • Размер: 3.08 MB
  • Онлайн: Да
  • Формат: ppt и pptx
В закладки
Оцени!

Слайды и текст этой онлайн презентации

Слайд 1

Использование графов при решении задач (11.04.2019), слайд 1
Использование графов при решении задач
9 класс
Автор: Александрова З.В., учитель физики и информатики, МБОУ СОШ №5 пгт Печенга, Мурманская область
2018 г.

Слайд 2

Использование графов при решении задач (11.04.2019), слайд 2
Что такое «Граф»
Схема метрополитена
Генеалогическое древо
Компьютерные сети
Файловая система
Графический редактор

Слайд 3

Использование графов при решении задач (11.04.2019), слайд 3
Граф – это совокупность непустого множества вершин и связей между вершинами. Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – ребрами.

Слайд 4

Использование графов при решении задач (11.04.2019), слайд 4
Виды графов 1. Ориентированный граф (кратко орграф) — рёбрам которого присвоено направление. 2. Неориентированный граф - это граф, в котором нет направления линий. 3. Взвешенный граф – дуги или ребра имеют вес (дополнительная информация)

Слайд 5

Использование графов при решении задач (11.04.2019), слайд 5
Если в графе вершины или рёбра характеризуются некоторой дополнительной информацией - весами вершин или рёбер, то такой граф называется ВЗВЕШЕННЫМ.

Слайд 6

Использование графов при решении задач (11.04.2019), слайд 6
Два варианта значения слова «граф» 1) удобная форма описания структур типа дорожной сети или сети передачи данных; 2) математический объект G := (V, E), где V — это непустое множество вершин, E — множество ребер (пар вершин).

Слайд 7

Использование графов при решении задач (11.04.2019), слайд 7
Для описания графа часто используют квадратную таблицу, которая описывает все возможные связи между узлами (без учета дублирования) – матрицу.
А Б В Г
А 5 8
Б 5 11 3
В 11 7
Г 8 3 7
ВЕСОВАЯ МАТРИЦА

Слайд 8

Использование графов при решении задач (11.04.2019), слайд 8
Задача 1.

Слайд 9

Использование графов при решении задач (11.04.2019), слайд 9
Сколько трехзначных чисел можно записать с помощью цифр 1, 3, 5, 7 при условии, что в записи числа не должно быть одинаковых цифр?
0
1
3
5
7
3
5
7
1
3
5
1
5
7
1
3
7
5
7
3
7
3
5
5
7
1
7
1
5
3
7
1
7
1
3
3
5
1
5
1
3
Ответ: 24 числа
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
Задача 2.

Слайд 10

Использование графов при решении задач (11.04.2019), слайд 10
На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
А
Б
В
Г
Д
Ж
Е
1. А-Б-Д-Ж
2. А-Б-Г-Д-Ж
3. А-Б-Г-Ж
4. А-В-Б-Д-Ж
5. А-В-Б-Г-Д-Ж
6. А-В-Б-Г-Ж
7. А-В-Г-Д-Ж
8. А-В-Г-Ж
9. А-В-Ж
10. А-В-Е-Ж
Ответ: 10 путей
Задача 3.

Слайд 11

Использование графов при решении задач (11.04.2019), слайд 11
Задача 4.

Слайд 12

Использование графов при решении задач (11.04.2019), слайд 12
Задача 3.
У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо?

Слайд 13

Использование графов при решении задач (11.04.2019), слайд 13
Задача 5.
Решение: Обозначим ученых вершинами графа и проведем от каждой вершины линии к четырем другим вершинам. Получаем 10 линий, которые и будут считаться рукопожатиями.

Слайд 14

Использование графов при решении задач (11.04.2019), слайд 14
Определить кратчайшее расстояние между наиболее удаленными друг от друга пунктами.
А Б В Г
А 5 8
Б 5 11 3
В 11 7
Г 8 3 7
А – В ?
А
Г
Б
5
8
В
Г
11
3
В
7
5+3+7 = 15
Задача 6.

Слайд 15

Использование графов при решении задач (11.04.2019), слайд 15
1. Определение вершины. 2. Построение графа.
3. Ответ ABDEF=12
E,2
Задача 7.

Слайд 16

Использование графов при решении задач (11.04.2019), слайд 16
Задача 8.

Слайд 17

Использование графов при решении задач (11.04.2019), слайд 17
Задача 9.
(Самостоятельно)

Слайд 18

Использование графов при решении задач (11.04.2019), слайд 18
Задача 10.
(Самостоятельно)

Слайд 19

Использование графов при решении задач (11.04.2019), слайд 19
Спасибо за работу на уроке!
^ Наверх
X

Благодарим за оценку!

Мы будем признательны, если Вы так же поделитесь этой презентацией со своими друзьями и подписчиками.