Внеурочная деятельность по теме "ГРАФЫ"

Лопатина Любовь Владимировна,

учитель математики

Муниципальное бюджетное общеобразовательное

учреждение «Средняя общеобразовательная

школа №1 им. М.П.Кочнева г.Нерюнгри»

Занятие математического кружка 8 класс Тема занятия: «Графы»

Форма занятия: Практикум по решению задач.

Цель занятия:

1. Через размышления над задачами, поиски решений развивать мышление, сообразительность.

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

3. Способствовать повышению математической грамотности, творческой активности.

Ход занятия:

I. Математическая разминка. ( Работа в парах)

Решение устных задач.

1. Попробуйте решить устно

Решение:

1. Найдите простой прием вычислений и воспользуйтесь им для вычисления суммы.

Решение:

Перепишем

(1-1/2) +(1/2 -1/3)+(1/3-1/4 ) +… +(1/9 – 1/10 )=1-1/10 =9/10

1. Найдите возможно быстрее частное и какой остаток получается при делении числа на 5

Решение: частное 1 остаток

1. Вычислите:

1000000-(1000000-(1000000 –(1000000-(1000000-999999))))

Решение:

1000000-(1000000-(1000000 –(1000000-1)))= 1000000-(1000000-(1000000 –999999))=

=1000000-(1000000-1)= 1000000-999999=1

1. Запишите число 100, пользуясь знаком «+»1) четырьмя 9, 2) шестью 9

(Допускается использование дробной черты)

Решение:

1. 99+9/9

2. 99+99/99

1. Какое натуральное число в 7 раз больше цифры его единиц?

Ответ:35

1. Как нужно расставить знаки + в записи 9 8 7 6 5 4 3 2 1 =99

Ответ: 9+8+7+65+4+3+2+1=99

1. Как 7 яблок разделить поровну между 12 мальчиками, не разрезая ни одного яблока больше, чем на 4 части?

Решение: Каждому достанется 1/3 яблока+1/4 яблока 1/3+1/4= 7/12

1. Найдите число, одна треть и одна четверть которого составляет 21.

Решение:

(1/3+1/4)х =21

х=36

1. Полтрети- число100. Что это за число?

Решение:

1/2( 1/3х)=100

х=600

II. Вводная часть. (Коллективная форма работы)

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

«Граф» имеет корнем греческое слово «графо», что означает «пишу»

Для иллюстрации понятия графа рассмотрим пример:

Задача 1.

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

Обсуждение:

Изобразим данные задачи в виде схемы:

Участников будем изображать точками:

Андрея- точкой А, Бориса- точкой Б, и т.д.

Если двое участников уже сыграли между собой,

то будем соединять изображающие их точки отрезками.

Такие схемы называются графами. Точки А, Б ,В,Г,Д,Е

Называются – вершинами графа, соединяющие их отрезки – ребрами графа. Число игр, проведенных к настоящему времени, равно числу ребер, т.е.7.

Чтобы найти число игр, которые осталось провести, построим еще один граф с теми же вершинами, но ребрами будем соединять тех участников, которые еще не играли друг с другом. Ребер у этого графа оказалось 8, значит осталось провести 8 игр.

Ответ: проведено 7 игр, осталось 8 игр.

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

1. Примеры решения задач.

Задача 2.

Может ли шахматный конь обойти все 9 полей доски 3 × 3?

Решение:

Все клетки шахматной доски перенумеруем с 1 до 9.

Представим каждую клетку в виде вершины графа, т.е точки с соответствующим номером.

1	2	3
4	5	6
7	8	9

Затем клетки (вершины) соединим ребрами, если из одной из них можно одним ходом коня перейти в другую. Например, из клетки с номером «1» можно ходом коня попасть в клетку с номерами «6» и «8» и обратно. Из клетки с номером «2» в «7» и «9» и т.д. В результате получим схему.

Как видно вершина с номером «5» не соединены ребром ни с одной из других вершин. Это значит, что в клетку «5» ни из одной клетки нельзя попасть ходом коня и, если конь стоит на этой клетке, то у него нет хода в другие клетки.

Ответ: Клетки шахматной доски 3×3 нельзя обойти ходом коня, побывав в каждой клетке.

Задача 3.

Выпишите в ряд цифры от 1 до 9 так, чтобы число составленное из двух соседних цифр, делилось либо на 7, либо на 13.

Решение:

Напишем цифры на листе. Соединим стрелками те цифры, которые могут следовать друг за другом. Стрелка от «7» к «8» показывает, что на 7 или 13 делится число 78, а от «4» к «2» и «9», что таких чисел два: 42 и 49.Из рисунка видно «7» выходит только одна стрелка – это означает, что «7» может только первой, а «6»- наоборот только последней, так как из «6» не выходит ни одной стрелки.

Выпишем первые цифры числа. Это будут 784: Из «7» выходит только одна стрелка и из «8» выходит тоже только одна стрелка. Цифры 7,8 и 4 уже использованы, поэтому стрелки «9-8», «2-8» и «1-4» уже не могут быть использованы (каждая цифра используется по условию задачи только один раз). Тогда получим следующий рисунок.

После цифры 4 могут стоять либо 2, либо 9.

Рассмотрим первый случай: допустим, четвертая цифра – это «2», тогда за «2» должна следовать «1», а за «1» - «3».После «3» есть также две возможности: либо «5», либо «9». Но в том и другом случае одна цифра не используется, а по условию должны быть использованы все девять цифр. Следовательно после «4» «2» не может стоять – это тупиковый путь. Рассмотрим «9» .Из «9» выходит только одна стрелка, т.е. следующей будет «1», дальше «3», «5», «2», «6».

Ответ: 784913526

В этом примере ребрами являются не отрезки, а стрелки, то есть направление существенно. Такие графы называются ориентированными.

Количество ребер, выходящих из вершины, называют его степенью.

Задача 4.

На занятиях кружка пришли 15 учеников. Некоторые из них поздоровались за руку. Могло ли быть так, что каждый поздоровался ровно с пятью другими.

Решение:

Предположим что, это возможно. Рассмотрим тогда граф, вершины которого ученики, а ребрами соединим тех из них, которые поздоровались за руку. В этом графе степень каждой вершины 5. Просуммируем все степени, получим 5*15. Это число равно удвоенному числу всех ребер, так как каждое рукопожатие считалось два раза, но число 5*15 нечетно.

Ответ: Нет, такого не могло быть.

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

Теорема. Число нечетных вершин любого графа четно.

Граф называется четным, если у него все вершины четные, связным- если между любыми вершинами существует путь, состоящий из ребер графа, плоским – если он нарисован на плоскости так, что его ребра не пересекаются.

Задачи по теме «Графы». (Работа в группах)

1. В соревновании по круговой системе с двенадцатью участниками провели все встречи. Сколько встреч было сыграно?

2. В футбольном турнире 20 команд сыграли 8 туров: Каждая команда сыграла с 8 разными командами. Докажите, что найдутся три команды, не сыгравшие между собой пока ни одного матча.

3. Каждый из семи мальчиков имеет не менее трех братьев. Докажите, что все мальчики- братья.

4. Каждый из учеников 7а класса дружит с тремя учениками 7б класса, а каждый ученик 7б класса дружит с тремя учениками 7а класса. Докажите, что число учеников в этих классах одинаково.

Указания к решению. Ответы.

1. .Построим граф встреч игроков. Поскольку каждая пара игроков встретилась между собой из каждой вершины графа выходит 11 ребер. В произведении 11×12 каждое ребро учтено дважды, поэтому граф имеет 11× 12 : 2 =66 ребер.

2. Построим граф встреч команд. По условию степень каждой вершины равна 8. Рассмотрим произвольную вершину v- она не смежна с 11 вершинами. Среди этих 11-ти вершин найдутся две вершины u и w не смежные между собой, так как в противном случае степень каждой вершины была бы не меньше 10.Вершины v, u и w будут той тройкой команд, не сыгравшей между собой ни одной встречи.

3. Предположим противное, что не все мальчики братья. Тогда граф состоит из не связанных друг с другом компонент, одна из которых имеет не более трех вершин. Степень каждой вершины этой компоненты не больше двух – противоречие. Следовательно, все мальчики братья.

4. Поставим в соответствии ученикам вершины графа G, а если два ученика дружат , то соединим ребром соответствующие вершины. Группу вершин графа, соответствующие ученикам 7 «а» класса обозначим А, а группу вершин, соответствующие ученикам 7 «б» класса - Б. Пусть в группе А n вершин, тогда количество ребер, выходящих из них равна 3n, количество вершин группы Б обозначим m. Тогда количество ребер, выходящих из группы Б равна 3m и 3n=3m. Отсюда n=m.

Рефлексия:

Результаты работы в группах: из19 учащихся все задачи не решил никто оставшиеся задачи попробовать решить дома.

3 задачи решили- 5 учеников– получили оценку за урок «5»

2 задачи - 9 учеников – получили оценку «4»

Контрольная работа по теме «Графы».

1. Брауну, Смиту и Джону предъявлено обвинение в соучастии в ограблении банка. Похитители скрылись на поджидавшем их автомобиле. На следствии Браун сказал, что преступники были на синем «Бьюике», Смит заявил, что это был черный «Крайслер», а Джонс утверждал, что это был «Форд» и ни в коем случае не синий. Желая запутать следствие, каждый из них указал правильно либо только марку, либо только цвет машины. Определите марку и цвет автомобиля, на котором скрылись грабители.

2. Леня, Женя и Миша имеют фамилии Орлов, Соколов, Ястребов. Какую фамилию имеет каждый мальчик, если Женя, Миша и Соколов члены математического кружка, а Миша и Ястребов занимаются музыкой.

3. Утверждают, что в одной компании из пяти человек каждый знаком с двумя и только с двумя другими. Возможна ли такая компания?

4. Девять шахматистов проводят турнир в один круг (каждый из участников должен сыграть с каждым из остальных по одному разу). Покажите, что в любой момент найдутся двое, закончившие одинаковое число партий.

Итоги контрольной работы:

Успеваемость-95%, качество – 82%, творчество- 43%