Семинар ДООМ: Первая встреча с графом.

--Москевич Лариса Вячеславовна 21:31, 5 ноября 2007 (UZT) Команда 061 Тема: Первая встреча с графом Цель: познакомить учащихся с понятием «граф», научить учащихся определять, изображать и составлять графы, которые можно вычерчивать без отрыва карандаша от бумаги.

Оборудование: цветной мел и карандаши, Мультимедийный проектор, Медиа:Example.oggпрезентация « Первая встреча с графом», карточки с домашним заданием. Ход факультативного занятия. 1.Учитель просит ребят разбиться на группы по 4-5 человек. 2.Учитель показывает 1-й слайд презентации, где изображены два конверта: один – открыт, другой – закрыт. Учитель просит перерисовать их в тетрадь и другим цветом их обрисовать, не отрывая карандаша от бумаги и не проводя дважды ни по одной линии. Учащиеся приходят к выводу, что открытый конверт можно нарисовать, в отличие от закрытого.

3.Учитель предлагает обозначить точки пересечений, а в скобках написать, сколько линий выходит из той или иной точки пересечений, если четное, то поставить «ч», если – нечетное – «н». Показывает, как выполнить данную работу на 2-м слайде. 4.Учитель включает 3-й слайд. На слайде изображены фигуры, представляющие собой окружности, в которых проведены линии и просит перерисовать их в тетрадь, обозначить, как и в предыдущем случае и попытаться обрисовать их не отрывая карандаш от бумаги и не проводя дважды ни одной линии. Учащиеся выполняют задание и приходят к выводу, что фигуры, изображенные на рисунках а); в); д) можно нарисовать одним росчерком не проводя ни одной линии дважды, а остальные – нельзя. 5. Учитель просит учащихся выдвинуть гипотезу о том, в каком случае можно выполнить задание, а в каком нет. Выступает в роли координатора диспута. Если есть необходимость, помогает с помощью наводящих вопросов. Учащиеся высказывают свое мнение, делают предположение о том, что фигуру можно нарисовать, не отрывая карандаш от листа и не проводя дважды ни одной линии, если в одну точку можно войти столько же раз, сколько выйти из нее, за исключением быть может начала и конца пути. 6. Выдвигается гипотеза: фигуру можно нарисовать, не отрывая карандаш от листа и не проводя дважды ни по одной линии, если она содержит не более двух точек, из которых выходит нечетное число линий. 7. Учитель предлагает каждой группе придумать два рисунка, в одном из которых не более двух таких точек, а в другом – 3 или более. Задает вопрос: «Находит ли подтверждение выдвинутая гипотеза?» Учащиеся выполняют задание и приходят к выводу о подтверждении данной гипотезы. 8. Учитель показывает схему мостов Кёнигсберга. Слайд №4. Рассказывает легенду. Имеются исторические сведения о том, что три столетия назад жители тихого Кёнигсберга увлеченно решали задачу: требовалось найти маршрут, проходящий по всем четырем участкам суши по одному разу. При этом через каждый из мостов можно проходить только по одному разу, а конец и начало пути должны совпадать 9.Учащимся предлагается данный рисунок преобразовать в схему, состоящую из точек и линий и сделать вывод о возможности решения данной задачи. Учащиеся составляют схему, нумеруют точки и делают вывод о возможности решения. 10.Учитель продолжает рассказ. Этой головоломкой заинтересовался Леонард Эйлер (слайд №5). Слайд №6. Эйлер доказал, что маршрута, который бы отвечал условиям головоломки, не существует, и разработал теорию решения такого рода головоломок, давшую начало новому разделу математики, получившему название «теория графов». 11.Учитель вводит понятие «граф». Слайд №7. Схемы, состоящие из точек (кружков) и отрезков, соединяющих пары точек называют графами. Точки графа иначе называют вершинами графа, отрезки – ребрами графа. Ребра графа могут изображаться как прямыми, так и кривыми линиями, а точки могут располагаться произвольно. Так на слайде № 8 изображен один и тот же граф. Если вершина графа не соединена с другими вершинами отрезками, ее называют изолированной. Слайд №9. Если каждая вершина графа соединена отрезками со всеми остальными вершинами, то граф называется полным. Слайд №10. 12. Учитель просит учащихся самостоятельно выполнить задания: 1) Нарисовать граф с пятью вершинами и пятью ребрами (3 различных варианта). Слайд №11.

2) Нарисовать граф с четырьмя вершинами и пятью ребрами так, что бы одна вершина была изолированной. Слайд №11.
3) Слайд №12.  Найти три пары одинаковых графов.

13. Обсуждение решений в группе 14. Учитель продолжает объяснение. В связи с задачей о Кёнигсбергских мостах возникло понятие эйлерова пути — так называется путь в графе, проходящий по каждому ребру графа ровно один раз. Если начало и конец эйлерова пути совпадают, то он называется эйлеровым циклом, а такой граф называется эйлеровым графом. Степенью вершины графа называется число ребер графа, которым принадлежит эта вершина. Слайд №13. Эйлер доказал, что граф будет иметь эйлеров цикл, если все его вершины имеют четную степень или граф содержит две нечетные вершины. Если же в графе количество нечетных вершин больше двух, то такой граф не обладает ни эйлеровым циклом, ни эйлеровым путем, его нельзя изобразить одним росчерком, не проходя дважды по одному и тому же ребру 15..Слайд №14. Задание: Найти на рисунке графы: a.которые обладают эйлеровым циклом; b.которые обладают эйлеровым путем; c.которые не обладают ни эйлеровым циклом, ни эйлеровым путем. 16.Учитель просит посмотреть на графы слайда №15 и ответить на вопросы: можно ли их обойти и если можно, то с какой вершины начинать обход и какая окажется в конце пути. 17. В ходе дискуссии ребята формулируют гипотезу: Если все вершины графа имеют четную степень, то тогда обход, о котором идет речь, возможен, и начать этот обход можно с любого участка. Если же из этих вершин две нечетные, то и тогда можно совершить обход, но только начало обхода должно быть взято в одной из этих двух вершин, а конец обхода будет во второй нечетной вершине. 18.Итоги занятия. Учитель: «Попробуйте провести рефлексию сегодняшнего занятия.» Ученики: Познакомились с понятиями граф, ребро, вершина графа. Узнали какой граф можно обойти «одним росчерком», узнали о существовании раздела математики «теории графов», узнали о том, кто и когда основал данную теорию. 19.Домашнее задание (карточки).

1)Составить алгоритм решения задач, в которых необходимо обойти фигуру «одним росчерком».

2)Ответить на вопрос: можно ли фигуру, изображенную на рисунке нарисовать одним росчерком? Решить с помощью графа. 3)Добавьте два моста так, чтобы получившуюся схему можно было обойти, побывав на каждом мосту ровно один раз и вернувшись в исходную точку

Литература:1.Генкин С.А., И.В. Итенберг, Д.В. Фомин. Ленинградские математические кружки: пособие для внеклассной работы. Киров, издательство «АСА», 1994.-272 стр. 2.Гуцанович С.А. Занимательная математика в базовой школе: Пособие для учителей.-Мн.: ТетраСистемс, 2004.-96 стр. 3.Заесенок В.П. Графы в математике и в жизни/Программа интеллектуального развития учащихся/ Выпуск 6/Инновационно-образовательный центр-М.1997-36 стр. 4.http://euler.math.ru.