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

Версия 22:16, 6 ноября 2007

--Москевич Лариса Вячеславовна 21:31, 5 ноября 2007 (UZT)

Команда 061

Тема: Первая встреча с графом

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

Оборудование: цветной мел и карандаши, Мультимедийный проектор, презентация « Первая встреча с графом», карточки с домашним заданием.

Ход факультативного занятия.

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.