Решение комбинаторных задач с помощью графов

Урок по комбинаторике в 9-м классе по теме:

"Решение комбинаторных задач с помощью графов"

Задачи урока:

Обучающие:

знакомство учащихся с комбинаторными задачами,

знакомство учащихся с понятием графа,

научить учащихся решать комбинаторные задачи с помощью графов,

познакомить учащихся с правилом умножения при решении комбинаторных задач,

отработка навыков решения комбинаторных задач с помощью графов.

Развивающие:

развитие комбинаторного мышления учащихся,

формирование интеллектуальных умений: анализировать, выделять главное, сравнивать, обобщать и систематизировать, разрешать проблемы,

развитие умений владеть собой,

развитие инициативы, уверенности в своих силах, умения преодолевать трудности в учении.

Воспитывающие:

содействовать формированию основных мировоззренческих идей,

содействовать профориентации учащихся.

Тип урока. Урок изучения нового материала.

Структура урока.

Организационный момент.

Мотивация и сообщение темы урока.

Формирование новых понятий и способов действий.

Применение знаний, умений и навыков в различных ситуациях (стандартных и нестандартных)

Подведение итогов, задание на дом.

Ход урока

1. Организационный момент.

2.Мотивация и сообщение темы урока.

Переходим к уроку.

Тема нашего урока: "Решение комбинаторных задач с помощью графов". Запишите её в тетради.

Ребята, вы решали комбинаторные задачи?

Какие задачи вы решали?

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

Почему нам нужно научиться решать комбинаторные задачи? Как вы думаете?

Потому что в программу 9 класса включен материал: "Элементы комбинаторики и теории вероятностей" и возможно в экзаменационных тестах вам встретится задание по этой теме.

3.Формирование новых понятий и способов действий.

Чтобы вы хотели узнать по теме нашего урока. Поставим вопросы к уроку.

• Чем занимается комбинаторика?

Какие задачи относятся к комбинаторным?

Что такое граф?

Как решаются комбинаторные задачи с помощью графа?

Ребята, где мы можем найти ответы на интересующие нас вопросы? Назовите источники информации.

Предполагаемый ответ: источниками информации могут быть книги и Интернет ресурсы.

Найдём, пользуясь ими, ответ на первый вопрос.Что такое комбинаторика?

Ребята, раз комбинаторика это наука, то что мы можем о ней узнать? Комбинаторика - раздел математики, рассматривающий вопросы (задачи), связанные с подсчётом числа всевозможных комбинаций из элементов данного конечного множества при сделанных исходных предположениях.

Историю её возникновения, этапы её развития, учёных внёсших вклад в развитие этой науки, проблемы комбинаторики. Этими вопросами вы займётесь дома.

Попробуем найти ответ на следующий вопрос. Что такое граф?

Граф- это геометрическая фигура, состоящая из точек (вершины графа) и линий, их соединяющих (рёбра графа).

При этом с помощью вершин изображают элементы некоторого множества (предметов, людей и т.д.), а с помощью рёбер - определённые связи между элементами. Для удобства иллюстрации условия задачи, вершины графа могут быть заменены кругами или прямоугольниками. Ребята, теория графов входит в программу зарубежных школ, наших вузов и институтов, но не изучается в наших школах. Вы можете самостоятельно найти информацию о истории возникновения графов, о терминологии, изображении графов, применении теории графов. Через теорию графов происходит проникновение математических методов в науку и технику. Графами можно изображать схемы дорог коммуникаций, электрических цепей, молекулы химических соединений, связи между людьми и группами людей. Вы в этом сейчас сами убедитесь.

Задача №1.

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

Решение: ребята найдут ответ, начертив граф.

Задача решается с помощью полного графа с четырьмя вершинами А,Б,В,Г, обозначенными по первым буквам имён каждого из мальчиков. В полном графе проводятся всевозможные рёбра. В данном случае отрезки-рёбра обозначают сыгранные шахматные партии. Из рисунка видно, что граф имеет 6 рёбер, значит, и партий сыграно 6 партий.

Ответ: 6 партий.

Задание для самостоятельной работы: придумайте задачи с похожим условием.

Математика повсюду -
Глазом только поведешь
И примеров сразу уйму
Ты вокруг себя найдешь:

Задача№2.

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

Решение: ребята легко найдут ответ, начертив граф.

Решение.

1 способ. С помощью стрелок на рёбрах полного графа показан процесс обмена фотографиями. Очевидно, что стрелок в 2 раза больше, чем рёбер, т.е. 12.

2 способ. Каждый из 4 мальчиков подарил друзьям 3 фотографии, следовательно, всего было подарено 3*4=12 фотографий.

Ответ:12 фотографий.

Задача №3.

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

Решение задачи: сначала выбирается конверт, а затем выбирается марка.

Ответ: 6 вариантов.

Отличается ли данный граф от- предыдущих? Он имеет внешнее сходство с деревом, поэтому он так и называется - граф-дерево. Рёбра графа- дерева иногда называют ветвями, а сам граф -деревом вариантов. Вычерчивать дерево полезно, когда требуется записать все существующие комбинации элементов.

Решим следующую задачу с помощью графа-дерева.

Задача №4

Ужасные грабители Кнопка и Скрёпка решили украсть из сейфа золотой ключик Буратино, который знает пока 4 цифры:1,2,3,4.Сколько вариантов придётся перебрать им, чтобы проникнуть в дом, подобрав двузначный код?

Ответ:16 вариантов.

Задача №5.

Сколько двузначных чисел можно составить из чисел 1,2,3.4 ,используя в записи числа каждую из них не более одного раза?

Ответ:12 чисел.

Задача №6.

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

Решение. Первую цифру трёхзначного числа можно выбрать четырьмя способами. Так как после выбора первой цифры останутся три, то вторую цифру, из оставшихся, можно выбрать тремя способами. Наконец третью цифру можно выбрать из оставшихся двумя способами.

Ответ.24 числа.

Задача №7.

Антон, Борис и Василий купили 3 билета на 1-е, 2-е и 3-е места первого ряда на футбольный матч. Сколькими способами они могут занять имеющиеся места?

Ответ: 6 способов.

Задача №8.

В пятницу у вас 4 урока: алгебра, русский, физика, история. Сколькими способами можно составить расписание на пятницу?

Ответ. 24 способа.

5.Подведение итогов урока.

Ребята, на все ли поставленные вопросы мы ответили? Ещё раз обратим на них внимание и дадим на них ответы.

Дома вы решите похожие задачи и найдёте ответы на вопросы, поставленные в начале урока.

Задание на дом.

Подготовьте материал по темам:

История возникновения комбинаторики и этапы её развития. Учёные, внёсшие вклад в развитие комбинаторики. Проблемы комбинаторики. История возникновения теории графов. Терминология теории графов. Некоторые задачи теории графов.

Решите задачи:

1. Сколько различных трёхзначных чисел можно записать с помощью цифр:

1)1 и 2;2)0 и 1?

2. Сколько различных трёхзначных чисел можно записать с помощью цифр 5,6,7,8,9,если:

1) цифры в числе могут повторяться;

2) цифры в числе должны быть различны?

Адрес публикации: https://www.prodlenka.org/metodicheskie-razrabotki/302691-reshenie-kombinatornyh-zadach-s-pomoschju-gra