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