Цели урока:
- образовательные: передать систему математических знаний по теме «элементарные факты теории графов», выработать умения решать основные типы математических задач, связанные с графами, формировать умения анализировать, выдвигать гипотезы и предположения, строить доказательства, переносить знания в новые ситуации;
- развивающие: создать условия для развития следующих компетенций:
- уверенность в себе;
- самостоятельность мышления, оригинальность;
- критическое мышление;
- готовность работать над чем-либо спорным и вызывающим беспокойство;
- способность принимать решения;
- персональная ответственность;
- способность слушать других людей и принимать во внимание то, что они говорят;
- воспитательные: воспитывать стремление к приобретению новых знаний, интерес к предмету.
Дидактическое обеспечение:
- Презентация Power Point, карточки для рефлексии.
Время занятия: 1 урок (45 минут).
Ход урока.
I. Организационный момент (приветствие, постановка цели урока, заполнение журнала в части указания отсутствующих на уроке).
Слайд 1.
II. Историческая справка. Мотивация.
Итак, как вы все знаете, 1ая работа по теории графов принадлежит Леонарду Эйлеру. Ещё в 1736 году в одном из своих писем итальянскому математику и инженеру Мариони он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Но при решении этой задачи сам Эйлер не использует термин «граф». Только через 200 лет, в 1936 году, этот термин был предложен венгерским математиком Денешом Кёнигом в его работе «Теории конечных и бесконечных графов». В начале 20 века наряду с термином «граф» употреблялись и другие: карта, комплекс, диаграмма, сеть, лабиринт и т.п. В настоящее время, термин «граф» считается устоявшимся, хотя в прикладной математике, наряду с ним употребляется и термин «сеть» (сети Петри, нейронные сети и т.д.).
Слайд 2.
Я предлагаю рассматривать тему сегодняшнего занятия через призму задач.
III. Актуализация знаний и их практическое применение.
Давайте рассмотрим достаточно известную задачу о космическом сообщении (была использована в программе летней школы Дилемма – 2010 для 3 группы 6 класса, г.Казань, приведена в [3], [4]): между 9 планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля – Меркурий, Плутон – Венера, Земля – Плутон, Плутон – Меркурий, Меркурий – Венера, Уран – Нептун, Нептун – Сатурн, Сатурн – Юпитер, Юпитер – Марс и Марс – Уран. Можно ли добраться с Земли до Марса?.
Слайд 3.
Собственно, при решении этой задачи возникают понятия графа (определим неформально так схему, состоящую из точек и соединяющих эти точки отрезки прямых или кривых), его вершин и ребер. В приведенном примере также применяется связность (в данной задаче получаем граф, состоящий из двух несвязных компонент). По ходу решения прошу учащихся озвучить соответствующие определения. Именно наглядное представление условий задачи в виде графа позволяет сразу дать ответ о невозможности сообщения между Землей и Марсом.
Рисунок 1
Следующая задача о конях известна в различных вариациях и была использована в программе летней школы Дилемма – 2010 для учащихся 1, 2 групп 6 класса, г.Казань, а также приведена в [1], [3], [4] книгах. Сформулируем ее следующим образом: В углах доски 3´3 стоят четыре коня: сверху белые, снизу черные. Можно ли их переставить за несколько ходов так, чтобы одноцветные кони стояли в противоположных углах доски?
Слайд 4.
Рисунок 2
При решении этой задачи «всплывает» такое понятие, как изолированная вершина, т.е. вершина, из которой не исходит ни одного ребра. Это 5ая клетка доски. Для решения задачи это понятие не используется. Здесь мы опять-таки используем понятие связности графа, соответствующего условию задачи: он является несвязным и состоит из двух «частей», одна из которых является изолированной вершиной. Движение коней возможно только по вершинам графа, соединенным ребрами. И, т.к. разноцветные кони не могут «перешагнуть» друг через друга (не возможно разместить в одной клетке доски два коня одновременно), то получаем отрицательный ответ на вопрос задачи.
Следующая задача о расстановке чисел приведена в [3], [4]: можно ли выписать в ряд цифры от 0 до 9 так, чтобы сумма любых двух рядом стоящих цифр делилась либо на 5, либо на 7, либо на 13?
Слайд 5.
Данная задача – яркий представитель еще одного класса задач, в которых можно использовать графы: задачи на расстановки чисел или каких-то других элементов в определенном порядке.
Решение. За вершины графа примем цифры 0, 1, 2, …, 9. Если сумма двух рядом стоящих цифр делится либо на 5, либо на 7, либо на 13, то соединим соответствующие вершины ребром. Получим граф.
Перебором находим одно из возможных решений: 0 – 7 – 3 – 4 – 6 – 1 – 9 – 5 – 8 – 2.
Рисунок 3
Обратить внимание учащихся, что приведённый ответ не является единственным.
Задачи о дорогах между 100 городами и о количестве песен взяты из [1], [3], [4] и решаются они по одному и тому же принципу.
Слайд 6.
Задача о дорогах между 100 городами. В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?
Задача о количестве песен на концерте. На концерте каждую песню исполняли двое артистов, и никакая пара не выступала вместе более одного раза. Всего было 12 артистов, каждый выступил по 5 раз. Сколько песен было спето?
Считать ребра графа легче, чем дороги или песни: ребра можно нарисовать, разрезать на части (т.е. рассмотреть их концы) и т.п. Именно свойство наглядности и обуславливает широкое распространение графов.
В обеих задачах этого слайда возникает понятие степени (или порядка) вершины, т.е. количества ребер, исходящих из этой вершины. В соответствии с этим понятием вершины делят на четные и нечетные.
Следующая задача о дорогах между 15 городами [1], [5], [6] с неявным использованием понятия «степень вершины» сформулирована следующим образом: В стране 15 городов, каждый из которых соединён дорогами не менее чем с семью другими. Докажите, что из любого города можно добраться в любой город (возможно, проезжая через другие города).
Слайд 7.
При доказательстве обратить внимание учащихся на тот момент, что чертить граф не всегда удобно (слишком много вершин), но можно представить его мысленно.
Следующая задача «на 10 девчонок по статистике 9 рябят»: на дискотеке каждый мальчик танцевал ровно с десятью девочками, а каждая девочка – ровно с девятью мальчиками. Кого больше: мальчиков или девочек?
Слайд 8.
Если эту задачу из [4] книги переформулировать в равносильную, но с другим сюжетом, то решение становится очевидным: к празднику было куплено несколько тортов, и каждый был разрезан на 9 кусков. Каждому пришедшему досталось по 10 кусков. Чего было меньше: тортов или пришедших? Здесь сразу ясно, что каждому досталось по 10/9 торта, то тортов было больше.
Решение следующей задачи предлагаю сама, для того, чтобы подвести учащихся к формулировке и доказательству леммы о рукопожатиях.
Задача: Аркадий, Борис, Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько рукопожатий было сделано?
Слайд 9.
Решение. Пусть каждому из 5 молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени, а производимому рукопожатию – ребро графа, соединяющее соответствующие вершины.
Рисунок 4
В построенном графе ровно 10 ребер, которые и соответствуют 10 рукопожатиям.
На самом деле задачу о рукопожатиях из [2] проще решить исходя из логических соображений: всего 5 человек и каждый пожал руку 4ым, но ведь если один пожал руку другому, то и другой пожал руку первому, т.е. число рукопожатий равно 5·4:2 = 10.
Применительно к теме «Графы», при разборе данной задачи полезно записать сначала понятия неполного и полного графа. Графы, в которых построены не все возможные ребра называются неполными. Во всех рассмотренных ранее задачах речь шла о неполных графах. Если же в графе для любой вершины найдется ребро, соединяющее эту вершину со всеми другими, отличными от данной, то такой граф считается полным. Если данную задачу переформулировать в равносильную на языке графов, то требуется узнать число ребер в полном графе из 5 вершин.
Из рассмотренной задачи о рукопожатиях естественным образом возникает обобщение на полный граф из n вершин. Число ребер в нем выражается приведенной формулой.
Слайд 10.
Кроме того, рассмотрим и некоторые очевидные закономерности для графов [2], [4].
- Количество ребер в полном графе с n вершинами определяется как число неупорядоченных пар, составленных из n точек без повторений, т.е. число сочетаний без повторений из n элементов по 2:
. - Степени вершин полного графа одинаковы, и каждая на 1 меньше числа вершин этого графа.
- Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа (закономерность справедлива для любого графа, не только полного, и носит название леммы о рукопожатиях).
- Число нечетных вершин любого графа четно (следствие из леммы о рукопожатиях).
А теперь будем решать задачи с использованием приведенных закономерностей.
Слайды 11 – 24.
Рассмотрим задачу о вассалах короля из [1], [6]: у короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств?
Слайд 11.
Решение базируется на том факте, что при построении графа, соответствующего условиям задачи получаем противоречие со следствием леммы о рукопожатиях о четном количестве нечетных вершин графа.
Задача: докажите, что не существует многогранника, у которого было бы ровно семь ребер.
Слайд 12.
Доказательство. Если у многогранника 4 вершины, то это тетраэдр, имеющий 6 ребер (каждая из 4·3:2=6 пар вершин соединена не более, чем одним ребром).
Пусть число вершин многогранника n ³ 5. В каждой вершине многогранника сходится по крайней мере три грани, т.е. из каждой вершины многогранника выходит не меньше, чем 3 ребра.
Значит всего ребер не меньше, чем 
, что и требовалось доказать.
При решении задачи о 9 отрезках на плоскости из [2], [6], как и в задаче о вассалах короля используется следствие леммы о рукопожатиях.
Слайд 13.
Задача: Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?
Решение. Построим граф, 9-тью вершинами которого будут отрезки. Две вершины соединим ребром только в том случае, если соответствующие отрезки пересекаются, т.е. степень каждой вершины по условию задачи должна равняться 3. Но ранее доказали, число нечетных вершин любого графа четно.
Ответ: нет, не возможно.
Задача о мышах: в норке живёт семья из 24 мышей. Каждую ночь ровно четыре из них отправляются на склад за сыром. Может ли так получиться, что в некоторый момент времени каждая мышка побывала на складе с каждой ровно по одному разу?
Слайд 14.
При решении задачи о мышах из [6] используются не только логические рассуждения, но и признак делимости на 3.
Задача об абонентах в системе связи с некоторыми модификациями приведена в [2], [6]: В системе связи, состоящей из 2013 абонентов, каждый абонент связан ровно с n другими. Определите все возможные значения n.
Слайд 15, 16.
Для решения этой задачи используется понятие степени вершины и лемма о рукопожатиях.
Задача: Петя заметил, что у всех его 25 одноклассников различное число друзей в этом классе. Сколько друзей у Пети? (Укажите все возможные решения)
Слайд 17, 18, 19.
В задаче о друзьях Пети из [6] используется в неявном виде понятие степени вершины. В ходе решения этой задачи обнаруживается факт о возможности двух различных случаев, приводящих к разным ответам. Так как ситуации равновозможные, то в ответ записывает оба случая.
Задача: на плоскости нарисовано несколько точек, некоторые пары точек соединены отрезками. Известно, что из каждой точки выходит не более k отрезков. Докажите, что точки можно покрасить в k + 1 цвет таким образом, чтобы любые две точки, соединенные отрезком, были покрашены в разные цвета.
Слайд 20, 21.
В задаче о покраске точек [1], [6] используем индукцию.
И последняя задача на сегодня из [1], [6] имеет уровень сложности 6 из 7. Для ее решения необходимо будет использовать понятие степени вершины и лемму о рукопожатиях.
Задача: Гидры состоят из голов и шей (любая шея соединяет ровно две головы). Одним ударом меча можно снести все шеи, выходящие из какой-то головы A гидры. Но при этом из головы A мгновенно вырастает по одной шее во все головы, с которыми A не была соединена. Геракл побеждает гидру, если ему удастся разрубить ее на две несвязанные шеями части. Найдите наименьшее N, при котором Геракл сможет победить любую стошеюю гидру, нанеся не более, чем N ударов.
Слайд 22, 23, 24.
Решение. Перейдем к графу, в котором головы – вершины, шеи – ребра, а удар по шеям, выходящим из головы A назовем инвертированием вершины A.
Тогда, если есть вершина X степени не больше 10, то достаточно инвертировать ее соседей, и она отделится, т.е. эта вершина не будет соединена с остальными вершинами графа. Если есть вершина, соединенная со всеми вершинами, за исключением n (n £ 9 ), то нужно инвертировать сначала эту вершину, а затем те n вершин, с которыми она вначале не была соединена, и тогда эта вершина отделится. Если же для каждой вершины есть хотя бы 11 вершин, соединенных с ней, и хотя бы 10, не соединенных с ней, то всего вершин не меньше 22, и ребер не меньше, чем 22·11:2 = 121 > 100.
Приведем пример гидры, которую нельзя разрубить за 9 ударов: две группы по 10 голов и 100 шей, соединяющих все пары голов из разных групп. Заметим, что состояние ребра между вершинами A и B не изменилось (т.е. оно осталось, если было вначале, и не появилось, – иначе) Û вершины A и B отрубали в сумме четное число раз. Поэтому порядок отрубания вершин неважен, и бессмысленно отрубать вершину два раза.
Пусть по этой гидре нанесено не более 9 ударов. Тогда в каждой группе осталось по не отрубленной голове, и поэтому есть шея из одной группы в другую; более того, все не отрубленные головы образуют связное множество.
С другой стороны, каждая не отрубленная голова связана со всеми отрубленными в своей группе. Поэтому, если в каждой части отрублено хотя бы по голове, то гидра осталась связной. Если же все отрубленные головы в одной части, то гидра тоже осталась связной: любая не отрубленная голова в этой части связана со всей другой частью и со всеми отрубленными.
Ответ: 10 ударов.
Если найдется учащийся, сумевший решить эту задачу самостоятельно или с незначительными подсказками, то стоит оценить его положительно сразу же.
V. Домашнее задание.
К следующему уроку придумайте и решите по 3 задачи каждый на сегодняшнюю тему.
VI. Подведение итогов. Рефлексия.
Я рада, что вы все работали хорошо. А теперь вспомните основные моменты нашего урока.
Чему вы научились во время занятия? Учащиеся отвечают.
Сегодня за работу у доски получают оценки…, а также хочу отметить и поощрить за активную работу устно:…
(рефлексия)
Ребята, обратите внимание, у вас у каждого есть картинки с жестами. Оставьте перед уходом мне на столе тот, что соответствует вашим ощущениям от урока. Если не стесняетесь, то подпишите свою карточку.
Рисунок 5
Рисунок 6
Спасибо за работу. До свидания.
Список литературы:
- Генкин С. А., Итенберг И.В., Фомин Д. В. Ленинградские математические кружки: пособие для внеклассной работы. – Киров: АСА, 1994. – 272 с.
- Бутусов В. Ф., Колягин Ю. М., Сидоров Ю. В. и др. Математика: учебник для экономистов, – 10 – 11 кл. – М.: Сантакс-Пресс, 1996. – 199 с.: ил.
- Канель-Белов А. Я., Ковальджи А. К. Как решают нестандартные задачи / Под ред. В.О. Бугаенко. – 6-е изд., стереотип. – М.: МЦНМО, 2010, 96 с
- Гуровиц В. М., Ховрина В. В. Графы. – М.: МЦНМО, 2008. – 32 с.: ил.
- материалы Детской летней математической школы «Дилемма» (http://www.kazan-math.info/dilemma.php).
- задачи с сайта http://www.problems.ru/view_by_subject_new.php?parent=192.