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

Использование графов при решении задач

9 класс

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

2018 г.

Что такое «Граф»

Схема метрополитена

Генеалогическое древо

Компьютерные сети

Файловая система

Графический редактор

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

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

Виды графов

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

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

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

1) удобная форма описания структур типа дорожной сети или сети передачи данных;


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

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

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

Задача 1.

Сколько трехзначных чисел можно записать с помощью
цифр 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. А-Б-Д-Ж

2. А-Б-Г-Д-Ж

3. А-Б-Г-Ж

4. А-В-Б-Д-Ж

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

6. А-В-Б-Г-Ж

7. А-В-Г-Д-Ж

8. А-В-Г-Ж

9. А-В-Ж

10. А-В-Е-Ж

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

Задача 3.

Задача 4.

Задача 3.

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

Задача 5.

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

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

А – В ?

А

Г

Б

5

8

В

Г

11

3

В

7

5+3+7 = 15

Задача 6.

1. Определение вершины.
2. Построение графа.

3. Ответ ABDEF=12

E,2

Задача 7.

Задача 8.

Задача 9.

(Самостоятельно)

Задача 10.

(Самостоятельно)

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