Презентация по теме "Решение задач с помощью графов"
презентация к уроку по алгебре (9 класс) на тему

Слайд 1

Презентация подготовлена учителем математики МБОУ «Лицей №35» Шепталенко Т.Н.

Слайд 2

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

Слайд 3

Пусть задано некоторое непустое множество V и множество E пар различных элементов из V . Элементы множества V называются вершинами графа, элементы множества E – ребрами графа. Множество вершин и множество ребер называют графом . Будем использовать геометрическое представление графа. Вершины графа изображаются в виде точек на плоскости. Если две вершины образуют ребро, то соответствующую пару точек соединяют линией. Например, на рис.1 изображен граф G , заданный множеством вершин V = { 1,2,3,4,5 } и множеством ребер E = { (1,2), (2,3), (4,3), (4,2) } Число ребер, выходящих из вершины v , называют степенью вершины v и обозначается d(v) . Вершина степени 0 называется изолированной , вершина степени 1 – висячей . 0≤ d(v) ≤ n-1 , где n - число вершин графа. Рис.1

Слайд 4

Задача 1. Сколько диагоналей имеет пятиугольник? n- угольник? Решение. Всего отрезков, соединяющих 2 вершины n- угольника равно Из них n отрезков являются сторонами, остальные – диагонали. Получим формулу для нахождения числа диагоналей: Замечание: Сумма степеней вершин графа равна удвоенному числу ребер. Для пятиугольника : Рис.2

Слайд 5

Задача 2. В шахматном турнире по круговой системе участвуют 7 школьников. Информация о сыгранных партиях представлена в таблице. С кем сыграл Леша? Имя Количество игр Ваня 6 Толя 5 Леша 3 Дима 3 Семен 2 Илья 2 Женя 1 Решение. Построим граф встреч игроков, в котором каждая вершина соответствует участнику. В Т Л Д С И Ж По графу видно, что Леша встречался с Ваней, Толей и Димой. Кроме этого можно сказать, с кем встречались остальные школьники.

Слайд 6

Задача 3. Соревнование проводится по круговой системе. Это означает, что каждая пара игроков встречается между собой ровно один раз. Докажите, что в любой момент времени найдутся хотя бы два игрока, проведшие одинаковое количество встреч. Рис.3 Решение. Поставим в соответствие каждому игроку точку плоскости – вершину графа. Если 2 игрока встретились между собой, то соединим соответствующие вершины графа ребром. Получим граф встреч игроков. Надо доказать, что существуют 2 игрока, проведших одинаковое количество встреч, т.е. в графе обязательно найдутся 2 вершины, степени которых одинаковы . Доказательство (от противного). Допустим, что существует граф H , степени всех вершин которого различны. В промежутке от 0 до n-1 существует ровно n целых чисел: 0,1, 2,…, n-1 . Степени n вершин графа тоже расположены в этом промежутке. Поэтому должны существовать такие вершины v 1 , v 2 , …, v n , что d(v 1 )=0 , d(v 2 )=1, …, d(v n )=n-1 . Т.к. d(v 1 )=0 , то вершина v 1 не соединена ребром ни с какой другой вершиной. d(v n )=n-1 , следовательно, вершина v n соединена со всеми остальными вершинами, в том числе и с v 1 . Пришли к противоречию. Существование графа H , степени всех вершин которого различны, невозможно. Вывод: Хотя бы два игрока проведут одинаковое количество встреч.

Слайд 7

Задача 4. Андрей пошел с отцом в тир. Уговор был такой: Андрей делает 5 выстрелов и за каждое попадание получает еще по 2 выстрела. Андрей выстрелил 25 раз. Сколько раз он попал? Решение. Стрельбу Андрея можно описать деревом, которое называется корневым деревом. В этом дереве все вершины, кроме верхней, соответствуют выстрелам. Если Андрей попал, то степень соответствующей вершины равна 3, если промахнулся -1. Степень верхней вершины равна 5. Дерево имеет 26 вершин и 25 ребер. Пусть n - число попаданий. Тогда граф содержит n вершин степени 3, (25- n ) вершин степени 1 и одну вершину степени 5. Т.к. сумма степеней вершин графа равна удвоенному числу ребер, получим : 3· n+1 · (25-n)+5=2 · 25 n=10 Ответ: Андрей попал 10 раз.

Слайд 8

Следует отметить, что применение графов для решения задач не всегда целесообразно. Например, большое количество ребер графа может запутать учеников. Однако, с помощью графов можно наглядно моделировать задачу, что несомненно важно для развития комбинаторного мышления учащихся.