Similar presentations:
Решение комбинаторных задач с помощью. Урок 4
1.
Подсчёт вариантовс помощью графов
2. Цели урока
3.
ГРАФ – совокупность объектов со связями междуними. Объекты представляются как вершины, или
узлы графа, а связи – как дуги, или ребра.
вершины
ребра
»
3
4. Задача 1
В первенстве класса по настольному теннису принималиучастие 5 учеников:
Андрей, Борис, Галина, Олег, Елена.
Первенство проводилось по круговой системе – каждый
участник играет с каждым из остальных один раз.
К настоящему моменту некоторые игры уже проведены:
• Андрей сыграл с Борисом, Галиной и Еленой;
• Борис с Андреем и Галиной;
• Галина с Андреем и Олегом.
Сколько игр проведено к настоящему
моменту и сколько ещё осталось?
5. Решение
•Андрей сыграл с Борисом, Галиной и Еленой;•Борис с Андреем и Галиной
•Галина с Андреем и Олегом.
Андрей
Борис
Галина
Олег
Елена
6. Историческая справка
Впервые основы теорииграфов появились в
работе Леонарда
Эйлера, где он
описывает решение
головоломок и
математических
задач(1736).
7. Задача 2
Андрей, Борис, Виктор и Григорий играли вшахматы. Каждый сыграл с каждым по одной
партии. Сколько партий было сыграно?
А
Б
Г
В
Ответ: 6 партий
8. Задача 3
Андрей, Борис, Виктор и Григорий подарили на памятьдруг другу свои фотографии. Причём каждый мальчик
подарил каждому по одной фотографии. Сколько всего
фотографий было подарено?
А
Б
Г
В
Ответ: 12 фотографий
9. Задача 4
Маше на День рождения подарили три букета цветов: из роз, астр илилий. В доме было две вазы: хрустальная и керамическая. Маша
пробовала устанавливать каждый букет в каждую вазу. Перечислите
все полученные сочетания букета с вазой
10. Задача 5
Туристическая фирма планирует посещение туристамив Италии трёх городов: Венеции, Рима и Флоренции.
Сколько существует вариантов такого маршрута?
1 город
В
Р
Ф
2 город
Р
Ф
В
Ф
В
Р
3 город
ф
Р
Ф
В
Р
В
Ответ: 6 вариантов маршрута
11.
ФлоренцияРим
Венеция
12. Задача 6
На обед в школьной столовой предлагают двасупа: щи и борщ; три вторых блюда: рыба, гуляш и
плов; два третьих: компот и чай. Перечислите все
возможные варианты обедов из трех блюд.
1 блюдо
Щ
Р
2 блюдо
3 блюдо
К
Б
Г
Ч
К
П
Ч
К
Р
Ч
К
Г
Ч
К
П
Ч
К
Ответ: 12 вариантов
Ч
13. Задача 7
Из четырех ребят надо выделить двоих длядежурства по классу. Сколькими способами это
можно сделать?
1
Первый дежурный
Второй дежурный
2
3
2
4
3
3
4
Ответ: 6 способов
14. Задача 8
Сколько трехзначных чисел можно составить изцифр 0, 2, 4 при условии, что цифры не должны
повторяться ?
2
Первая цифра
4
Вторая цифра
0
4
0
2
Третья цифра
4
0
2
0
Ответ: 4 числа
15. Задача 9
Сколько трехзначных чисел можно составить изцифр 1, 3, 5 при условии, что цифры не должны
повторяться?
1
Первая цифра
3
5
Вторая цифра
3
5
1
5
3
1
Третья цифра
5
3
5
1
1
3
Ответ: 6 чисел