Понятие графа. Решение задач

1.

Подсчёт вариантов
с помощью графов

2. Цели урока

3. Задача 1

В первенстве класса по настольному теннису принимали
участие 5 учеников:
Андрей, Борис, Галина, Олег, Елена.
Первенство проводилось по круговой системе – каждый
участник играет с каждым из остальных один раз.
К настоящему моменту некоторые игры уже проведены:
• Андрей сыграл с Борисом, Галиной и Еленой;
• Борис с Андреем и Галиной;
• Галина с Андреем и Олегом.
Сколько игр проведено к настоящему
моменту и сколько ещё осталось?

4. Решение

•Андрей сыграл с Борисом, Галиной и Еленой;
•Борис с Андреем и Галиной
•Галина с Андреем и Олегом.
Андрей
Борис
Галина
Олег
Елена

5. Графы

Граф - это геометрическая фигура, состоящая из точек
(вершин графа) и соединяющих их отрезков(ребер графа)
Вершины
А
Б
Г
О
Е
Рёбра

6. Историческая справка

Впервые основы теории
графов появились в
работе Леонарда
Эйлера, где он
описывает решение
головоломок и
математических
задач(1736).

7. Задача 2

Андрей, Борис, Виктор и Григорий играли в
шахматы. Каждый сыграл с каждым по одной
партии. Сколько партий было сыграно?
А
Б
Г
В
Ответ: 6 партий

8. Задача 3

Андрей, Борис, Виктор и Григорий подарили на память
друг другу свои фотографии. Причём каждый мальчик
подарил каждому по одной фотографии. Сколько всего
фотографий было подарено?
А
Б
Г
В
Ответ: 12 фотографий

9. Задача 4

У Васи в альбоме нарисован прямоугольник, разделённый на три равные
части. Он должен закрасить каждую из этих частей в один из трёх цветов:
красный, жёлтый, зелёный. Нельзя закрашивать разные части одинаковым
цветом. Сколько вариантов рисунка может получиться?
1 клетка
2 клетка
3 клетка
Ответ: 6 вариантов

10. Задача 5

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

11. Задача 6

Туристическая фирма планирует посещение туристами
в Италии трёх городов: Венеции, Рима и Флоренции.
Сколько существует вариантов такого маршрута?
1 город
В
Р
Ф
2 город
Р
Ф
В
Ф
В
Р
3 город
ф
Р
Ф
В
Р
В
Ответ: 6 вариантов маршрута

12.

Флоренция
Рим
Венеция

13. Задача 7

На обед в школьной столовой предлагают два
супа: щи и борщ; три вторых блюда: рыба, гуляш и
плов; два третьих: компот и чай. Перечислите все
возможные варианты обедов из трех блюд.
1 блюдо
Щ
Р
2 блюдо
3 блюдо
К
Б
Г
Ч
К
П
Ч
К
Р
Ч
К
Г
Ч
К
П
Ч
К
Ответ: 12 вариантов
Ч

14. Задача 8

Из четырех ребят надо выделить двоих для
дежурства по классу. Сколькими способами это
можно сделать?
1
Первый дежурный
Второй дежурный
2
3
2
4
3
3
4
Ответ: 6 способов

15. Задача 9

Сколько трехзначных чисел можно составить из
цифр 0, 2, 4 при условии, что цифры не должны
повторяться ?
2
Первая цифра
4
Вторая цифра
0
4
0
2
Третья цифра
4
0
2
0
Ответ: 4 числа

16. Задача 10

Сколько трехзначных чисел можно составить из
цифр 1, 3, 5 при условии, что цифры не должны
повторяться?
1
Первая цифра
3
5
Вторая цифра
3
5
1
5
3
1
Третья цифра
5
3
5
1
1
3
Ответ: 6 чисел

17. Домашнее задание

• п. 4 №1, №2, №6
• Эйлеровы графы, задача о трех мостах