Похожие презентации:
Подсчёт вариантов с помощью графов
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. Домашнее задание
• На обед в столовой предлагают три супа: щи, уха и борщ; три вторых блюда:рыба, гуляш и плов; три третьих: компот, какао и чай,а также два десерта.
Перечислите все возможные варианты обедов из четырех блюд. ПОСТРОИТЬ
граф.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е. По каждой дороге можно двигаться
только в одном направлении, указанном стрелкой. Сколько существует различных путей из города
А в город Е?