Презентация, доклад на тему Использование графов при решении задач

Содержание

Что такое «Граф»Схема метрополитенаГенеалогическое древоКомпьютерные сетиФайловая системаГрафический редактор

Слайд 1Использование графов при решении задач
9 класс
Автор: Александрова З.В., учитель физики и

информатики,
МБОУ СОШ №5 пгт Печенга, Мурманская область

2018 г.

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

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

Что такое «Граф»Схема метрополитенаГенеалогическое древоКомпьютерные сетиФайловая системаГрафический редактор

Слайд 3Граф – это совокупность непустого множества вершин и связей между вершинами.



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

Слайд 4Виды графов

1. Ориентированный граф (кратко орграф) — рёбрам которого присвоено направление.
2. Неориентированный граф - это граф, в

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

Слайд 5Если в графе вершины или рёбра характеризуются некоторой дополнительной информацией -

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

Слайд 6Два варианта значения слова «граф»

1) удобная форма описания структур типа дорожной

сети или сети передачи данных;


2) математический объект
G := (V, E),
где V — это непустое множество вершин,
E — множество ребер (пар вершин).



Два варианта значения слова «граф»1) удобная форма описания структур типа дорожной сети или сети передачи данных;2) математический

Слайд 7Для описания графа часто используют квадратную таблицу, которая описывает все возможные

связи между узлами (без учета дублирования) – матрицу.

ВЕСОВАЯ МАТРИЦА

Для описания графа часто используют квадратную таблицу, которая описывает все возможные связи между узлами (без учета дублирования)

Слайд 8Задача 1.

Задача 1.

Слайд 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.

Сколько трехзначных чисел можно записать с помощью цифр 1, 3, 5, 7 при условии, что в записи

Слайд 10На рисунке - схема дорог, связывающих города А, Б, В, Г,

Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

А

Б

В

Г

Д

Ж

Е

1. А-Б-Д-Ж

2. А-Б-Г-Д-Ж

3. А-Б-Г-Ж

4. А-В-Б-Д-Ж

5. А-В-Б-Г-Д-Ж

6. А-В-Б-Г-Ж

7. А-В-Г-Д-Ж

8. А-В-Г-Ж

9. А-В-Ж

10. А-В-Е-Ж

Ответ: 10 путей

Задача 3.

На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге

Слайд 11Задача 4.

Задача 4.

Слайд 12Задача 3.
У Наташи есть 2 конверта: обычный и авиа, и 3

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

Слайд 13Задача 5.
Решение: Обозначим ученых вершинами графа и проведем от каждой вершины

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

Слайд 14Определить кратчайшее расстояние между наиболее удаленными друг от друга пунктами.
А –

В ?

А

Г

Б

5

8

В

Г

11

3

В

7

5+3+7 = 15

Задача 6.

Определить кратчайшее расстояние между наиболее удаленными друг от друга пунктами.А – В ?АГБ58ВГ113В75+3+7 = 15Задача 6.

Слайд 151. Определение вершины.
2. Построение графа.
3. Ответ ABDEF=12
E,2
Задача 7.

1. Определение вершины.2. Построение графа.3. Ответ ABDEF=12E,2Задача 7.

Слайд 16Задача 8.

Задача 8.

Слайд 17Задача 9.
(Самостоятельно)

Задача 9.(Самостоятельно)

Слайд 18Задача 10.
(Самостоятельно)

Задача 10.(Самостоятельно)

Слайд 19Спасибо за работу на уроке!

Спасибо за работу на уроке!

Что такое shareslide.ru?

Это сайт презентаций, где можно хранить и обмениваться своими презентациями, докладами, проектами, шаблонами в формате PowerPoint с другими пользователями. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами.


Для правообладателей

Яндекс.Метрика

Обратная связь

Email: Нажмите что бы посмотреть