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

Материал из ТолВИКИ
(Различия между версиями)
Перейти к: навигация, поиск
Строка 1: Строка 1:
--[[Участник:Москевич Лариса Вячеславовна|Москевич Лариса Вячеславовна]] 21:31, 5 ноября 2007 (UZT) Команда 061
+
--[[Участник:Москевич Лариса Вячеславовна|Москевич Лариса Вячеславовна]] 21:31, 5 ноября 2007 (UZT)
 +
 
 +
Команда 061
 +
 
 
'''Тема:''' Первая встреча с графом
 
'''Тема:''' Первая встреча с графом
 +
 
'''Цель:''' познакомить учащихся с понятием «граф»,
 
'''Цель:''' познакомить учащихся с понятием «граф»,
 
научить учащихся определять, изображать и составлять графы, которые можно вычерчивать без отрыва карандаша от бумаги.
 
научить учащихся определять, изображать и составлять графы, которые можно вычерчивать без отрыва карандаша от бумаги.
Строка 6: Строка 10:
 
'''Оборудование:'''  
 
'''Оборудование:'''  
 
цветной мел и карандаши, Мультимедийный проектор, [[Медиа:Example.ogg]]презентация « Первая встреча с графом», карточки с домашним заданием.
 
цветной мел и карандаши, Мультимедийный проектор, [[Медиа:Example.ogg]]презентация « Первая встреча с графом», карточки с домашним заданием.
 +
 +
 
'''Ход факультативного занятия.'''
 
'''Ход факультативного занятия.'''
1.Учитель просит ребят разбиться на группы по 4-5 человек.
+
 
2.Учитель показывает 1-й слайд презентации, где изображены два конверта: один – открыт, другой – закрыт. Учитель просит перерисовать их в тетрадь и другим цветом их обрисовать, не отрывая карандаша от бумаги и не проводя дважды ни по одной линии. Учащиеся приходят к выводу, что открытый конверт можно нарисовать, в отличие от закрытого.
+
#1) Учитель просит ребят разбиться на группы по 4-5 человек.
 +
 
 +
#2) Учитель показывает 1-й слайд презентации, где изображены два конверта: один – открыт, другой – закрыт. Учитель просит перерисовать их в тетрадь и другим цветом их обрисовать, не отрывая карандаша от бумаги и не проводя дважды ни по одной линии. Учащиеся приходят к выводу, что открытый конверт можно нарисовать, в отличие от закрытого.
 +
 
 
[[Изображение:Example.jpg]]
 
[[Изображение:Example.jpg]]
  
3.Учитель предлагает обозначить точки пересечений, а в скобках написать, сколько линий выходит из той или иной точки пересечений, если четное, то поставить «ч», если – нечетное – «н». Показывает, как выполнить данную работу на 2-м слайде.
+
#3) Учитель предлагает обозначить точки пересечений, а в скобках написать, сколько линий выходит из той или иной точки пересечений, если четное, то поставить «ч», если – нечетное – «н». Показывает, как выполнить данную работу на 2-м слайде.
 
[[Изображение:Example.jpg]]
 
[[Изображение:Example.jpg]]
4.Учитель  включает 3-й слайд. На слайде изображены фигуры, представляющие собой окружности, в которых проведены линии и просит перерисовать их в тетрадь, обозначить, как и в предыдущем случае и попытаться обрисовать их не отрывая карандаш от бумаги и не проводя дважды ни одной линии. Учащиеся выполняют задание и приходят к выводу, что фигуры, изображенные  на рисунках а); в); д) можно нарисовать одним росчерком не проводя ни одной линии дважды, а остальные – нельзя.
+
 
 +
#4) Учитель  включает 3-й слайд. На слайде изображены фигуры, представляющие собой окружности, в которых проведены линии и просит перерисовать их в тетрадь, обозначить, как и в предыдущем случае и попытаться обрисовать их не отрывая карандаш от бумаги и не проводя дважды ни одной линии. Учащиеся выполняют задание и приходят к выводу, что фигуры, изображенные  на рисунках а); в); д) можно нарисовать одним росчерком не проводя ни одной линии дважды, а остальные – нельзя.
 
[[Изображение:Example.jpg]]
 
[[Изображение:Example.jpg]]
5. Учитель просит учащихся выдвинуть гипотезу о том, в каком случае можно выполнить задание, а в каком нет. Выступает в роли координатора диспута. Если есть необходимость, помогает с помощью наводящих вопросов. Учащиеся высказывают свое мнение, делают предположение о том, что фигуру можно нарисовать, не отрывая карандаш от листа и не проводя дважды ни одной линии, если в одну точку можно войти столько же раз, сколько выйти из нее, за исключением быть может начала и конца пути.
+
 
6. Выдвигается гипотеза: фигуру можно нарисовать, не отрывая карандаш от листа и не проводя дважды ни по одной линии, если она содержит не более двух точек, из которых выходит нечетное число линий.
+
#5) Учитель просит учащихся выдвинуть гипотезу о том, в каком случае можно выполнить задание, а в каком нет. Выступает в роли координатора диспута. Если есть необходимость, помогает с помощью наводящих вопросов. Учащиеся высказывают свое мнение, делают предположение о том, что фигуру можно нарисовать, не отрывая карандаш от листа и не проводя дважды ни одной линии, если в одну точку можно войти столько же раз, сколько выйти из нее, за исключением быть может начала и конца пути.
7. Учитель предлагает каждой группе придумать два рисунка, в одном из которых не более двух  таких точек, а в другом – 3 или более. Задает вопрос: «Находит ли подтверждение выдвинутая гипотеза?» Учащиеся выполняют задание и приходят к выводу о подтверждении данной гипотезы.
+
 
8. Учитель показывает схему мостов Кёнигсберга. Слайд №4. Рассказывает легенду. Имеются исторические сведения о том, что три  столетия назад жители  тихого Кёнигсберга увлеченно решали задачу: требовалось найти маршрут, проходящий по всем четырем участкам суши по одному разу. При этом через каждый из мостов можно проходить только по одному разу, а конец и начало пути должны совпадать
+
#6) Выдвигается гипотеза: фигуру можно нарисовать, не отрывая карандаш от листа и не проводя дважды ни по одной линии, если она содержит не более двух точек, из которых выходит нечетное число линий.
 +
 
 +
#7) Учитель предлагает каждой группе придумать два рисунка, в одном из которых не более двух  таких точек, а в другом – 3 или более. Задает вопрос: «Находит ли подтверждение выдвинутая гипотеза?» Учащиеся выполняют задание и приходят к выводу о подтверждении данной гипотезы.
 +
 
 +
#8) Учитель показывает схему мостов Кёнигсберга. Слайд №4. Рассказывает легенду. Имеются исторические сведения о том, что три  столетия назад жители  тихого Кёнигсберга увлеченно решали задачу: требовалось найти маршрут, проходящий по всем четырем участкам суши по одному разу. При этом через каждый из мостов можно проходить только по одному разу, а конец и начало пути должны совпадать
 +
 
 
[[Изображение:Example.jpg]]
 
[[Изображение:Example.jpg]]
9.Учащимся предлагается данный рисунок преобразовать в схему, состоящую из точек и линий и сделать вывод о возможности решения данной задачи. Учащиеся составляют схему, нумеруют точки и делают вывод о возможности решения.  
+
 
10.Учитель продолжает рассказ. Этой головоломкой заинтересовался Леонард Эйлер (слайд №5). Слайд №6. Эйлер доказал, что маршрута, который бы отвечал условиям головоломки, не существует, и разработал теорию решения такого рода головоломок, давшую начало новому разделу математики, получившему название «теория графов».  
+
#9) Учащимся предлагается данный рисунок преобразовать в схему, состоящую из точек и линий и сделать вывод о возможности решения данной задачи. Учащиеся составляют схему, нумеруют точки и делают вывод о возможности решения.
 +
 +
#10) Учитель продолжает рассказ. Этой головоломкой заинтересовался Леонард Эйлер (слайд №5). Слайд №6. Эйлер доказал, что маршрута, который бы отвечал условиям головоломки, не существует, и разработал теорию решения такого рода головоломок, давшую начало новому разделу математики, получившему название «теория графов».  
 
[[Изображение:Example.jpg]]
 
[[Изображение:Example.jpg]]
11.Учитель вводит понятие «граф». Слайд №7. Схемы, состоящие из точек (кружков) и отрезков, соединяющих пары точек называют графами. Точки графа иначе называют вершинами графа, отрезки – ребрами графа. Ребра  графа могут изображаться как прямыми, так и кривыми линиями, а точки могут располагаться произвольно. Так  на слайде № 8 изображен один и тот же граф. Если вершина графа не соединена с другими вершинами отрезками, ее называют изолированной. Слайд №9. Если каждая вершина графа соединена отрезками со всеми остальными вершинами, то граф называется полным. Слайд №10.
+
 
 +
#11) Учитель вводит понятие «граф». Слайд №7. Схемы, состоящие из точек (кружков) и отрезков, соединяющих пары точек называют графами. Точки графа иначе называют вершинами графа, отрезки – ребрами графа. Ребра  графа могут изображаться как прямыми, так и кривыми линиями, а точки могут располагаться произвольно. Так  на слайде № 8 изображен один и тот же граф. Если вершина графа не соединена с другими вершинами отрезками, ее называют изолированной. Слайд №9. Если каждая вершина графа соединена отрезками со всеми остальными вершинами, то граф называется полным. Слайд №10.
 
[[Изображение:Example.jpg]]
 
[[Изображение:Example.jpg]]
12. Учитель просит учащихся самостоятельно выполнить задания: 1) Нарисовать граф с пятью вершинами и пятью ребрами (3 различных варианта). Слайд №11.
+
 
 +
#12) Учитель просит учащихся самостоятельно выполнить задания:  
 +
1) Нарисовать граф с пятью вершинами и пятью ребрами (3 различных варианта). Слайд №11.
 +
 
 
  2) Нарисовать граф с четырьмя вершинами и пятью ребрами так, что бы одна вершина была изолированной. Слайд №11.
 
  2) Нарисовать граф с четырьмя вершинами и пятью ребрами так, что бы одна вершина была изолированной. Слайд №11.
 +
 
  3) Слайд №12.  Найти три пары одинаковых графов.
 
  3) Слайд №12.  Найти три пары одинаковых графов.
 +
 
[[Изображение:Example.jpg]]
 
[[Изображение:Example.jpg]]
13. Обсуждение решений в группе
+
 
14. Учитель продолжает объяснение. В связи с задачей о  Кёнигсбергских мостах возникло понятие эйлерова пути — так называется путь в графе, проходящий по каждому ребру графа ровно один раз. Если начало и конец эйлерова пути совпадают, то он называется эйлеровым циклом, а такой граф называется эйлеровым графом. Степенью вершины графа называется число ребер графа, которым принадлежит эта вершина. Слайд №13. Эйлер доказал, что граф будет иметь эйлеров цикл, если все его вершины имеют четную степень или граф содержит две нечетные вершины. Если же в  графе количество нечетных вершин больше двух, то такой граф не обладает ни эйлеровым циклом, ни эйлеровым путем, его нельзя изобразить одним росчерком, не проходя дважды по одному и тому же ребру
+
#13) Обсуждение решений в группе
 +
 
 +
#14) Учитель продолжает объяснение. В связи с задачей о  Кёнигсбергских мостах возникло понятие эйлерова пути — так называется путь в графе, проходящий по каждому ребру графа ровно один раз. Если начало и конец эйлерова пути совпадают, то он называется эйлеровым циклом, а такой граф называется эйлеровым графом. Степенью вершины графа называется число ребер графа, которым принадлежит эта вершина. Слайд №13. Эйлер доказал, что граф будет иметь эйлеров цикл, если все его вершины имеют четную степень или граф содержит две нечетные вершины. Если же в  графе количество нечетных вершин больше двух, то такой граф не обладает ни эйлеровым циклом, ни эйлеровым путем, его нельзя изобразить одним росчерком, не проходя дважды по одному и тому же ребру
 
[[Изображение:Example.jpg]]
 
[[Изображение:Example.jpg]]
15..Слайд №14. Задание: Найти на рисунке графы:  
+
 
 +
#15) Слайд №14. Задание: Найти на рисунке графы:
 +
 
a.которые обладают эйлеровым циклом;
 
a.которые обладают эйлеровым циклом;
 +
 
b.которые обладают эйлеровым путем;
 
b.которые обладают эйлеровым путем;
 +
 
c.которые не обладают ни эйлеровым циклом, ни эйлеровым путем.
 
c.которые не обладают ни эйлеровым циклом, ни эйлеровым путем.
 +
 
[[Изображение:Example.jpg]]
 
[[Изображение:Example.jpg]]
16.Учитель просит посмотреть на графы слайда №15 и ответить на вопросы: можно ли их обойти и если можно, то с какой вершины начинать обход и какая окажется в конце пути.
+
 
 +
#16) Учитель просит посмотреть на графы слайда №15 и ответить на вопросы: можно ли их обойти и если можно, то с какой вершины начинать обход и какая окажется в конце пути.
 
[[Изображение:Example.jpg]]
 
[[Изображение:Example.jpg]]
17. В ходе дискуссии ребята формулируют гипотезу: Если все вершины графа имеют четную степень, то тогда обход, о котором идет речь, возможен, и начать этот обход можно с любого участка. Если же из этих вершин две нечетные, то и тогда можно совершить обход, но только начало обхода должно быть взято в одной из этих двух вершин, а конец обхода будет во второй нечетной вершине.
+
 
18.Итоги занятия. Учитель: «Попробуйте провести рефлексию сегодняшнего занятия.» Ученики: Познакомились с понятиями граф, ребро, вершина графа. Узнали  какой граф можно обойти «одним росчерком», узнали о существовании раздела математики «теории графов», узнали о том, кто и когда основал данную теорию.
+
#17) В ходе дискуссии ребята формулируют гипотезу: Если все вершины графа имеют четную степень, то тогда обход, о котором идет речь, возможен, и начать этот обход можно с любого участка. Если же из этих вершин две нечетные, то и тогда можно совершить обход, но только начало обхода должно быть взято в одной из этих двух вершин, а конец обхода будет во второй нечетной вершине.
19.Домашнее задание (карточки).
+
 
 +
#18) '''Итоги занятия.'''
 +
 
 +
Учитель: «Попробуйте провести рефлексию сегодняшнего занятия.» Ученики: Познакомились с понятиями граф, ребро, вершина графа. Узнали  какой граф можно обойти «одним росчерком», узнали о существовании раздела математики «теории графов», узнали о том, кто и когда основал данную теорию.
 +
 
 +
#19) '''Домашнее задание''' (карточки).
 +
 
 
  1)Составить алгоритм решения задач, в которых необходимо обойти фигуру «одним росчерком».
 
  1)Составить алгоритм решения задач, в которых необходимо обойти фигуру «одним росчерком».
2)Ответить на вопрос: можно ли фигуру, изображенную на рисунке нарисовать одним росчерком? Решить с помощью графа.
+
 
3)Добавьте два моста так, чтобы получившуюся схему можно было
+
2)Ответить на вопрос: можно ли фигуру, изображенную на рисунке нарисовать одним росчерком? Решить с помощью графа.
 +
 
 +
3)Добавьте два моста так, чтобы получившуюся схему можно было
 
обойти, побывав на каждом мосту ровно один раз и вернувшись в исходную точку
 
обойти, побывав на каждом мосту ровно один раз и вернувшись в исходную точку
 +
  
 
[[Изображение:Example.jpg]]
 
[[Изображение:Example.jpg]]
'''Литература:'''1.Генкин С.А., И.В. Итенберг, Д.В. Фомин. Ленинградские математические кружки: пособие для внеклассной работы. Киров, издательство «АСА», 1994.-272 стр.
+
 
 +
'''Литература:'''
 +
1.Генкин С.А., И.В. Итенберг, Д.В. Фомин. Ленинградские математические кружки: пособие для внеклассной работы. Киров, издательство «АСА», 1994.-272 стр.
 +
 
 
2.Гуцанович С.А. Занимательная математика в базовой школе: Пособие для учителей.-Мн.: ТетраСистемс, 2004.-96 стр.
 
2.Гуцанович С.А. Занимательная математика в базовой школе: Пособие для учителей.-Мн.: ТетраСистемс, 2004.-96 стр.
 +
 
3.Заесенок В.П. Графы в математике и в жизни/Программа интеллектуального развития учащихся/ Выпуск 6/Инновационно-образовательный центр-М.1997-36 стр.
 
3.Заесенок В.П. Графы в математике и в жизни/Программа интеллектуального развития учащихся/ Выпуск 6/Инновационно-образовательный центр-М.1997-36 стр.
 +
 
4.http://euler.math.ru.
 
4.http://euler.math.ru.
 +
[[Категория: Проект ДООМ]]

Версия 17:33, 6 ноября 2007

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

Команда 061

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

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

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


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

  1. 1) Учитель просит ребят разбиться на группы по 4-5 человек.
  1. 2) Учитель показывает 1-й слайд презентации, где изображены два конверта: один – открыт, другой – закрыт. Учитель просит перерисовать их в тетрадь и другим цветом их обрисовать, не отрывая карандаша от бумаги и не проводя дважды ни по одной линии. Учащиеся приходят к выводу, что открытый конверт можно нарисовать, в отличие от закрытого.

Example.jpg

  1. 3) Учитель предлагает обозначить точки пересечений, а в скобках написать, сколько линий выходит из той или иной точки пересечений, если четное, то поставить «ч», если – нечетное – «н». Показывает, как выполнить данную работу на 2-м слайде.

Example.jpg

  1. 4) Учитель включает 3-й слайд. На слайде изображены фигуры, представляющие собой окружности, в которых проведены линии и просит перерисовать их в тетрадь, обозначить, как и в предыдущем случае и попытаться обрисовать их не отрывая карандаш от бумаги и не проводя дважды ни одной линии. Учащиеся выполняют задание и приходят к выводу, что фигуры, изображенные на рисунках а); в); д) можно нарисовать одним росчерком не проводя ни одной линии дважды, а остальные – нельзя.

Example.jpg

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

Example.jpg

  1. 9) Учащимся предлагается данный рисунок преобразовать в схему, состоящую из точек и линий и сделать вывод о возможности решения данной задачи. Учащиеся составляют схему, нумеруют точки и делают вывод о возможности решения.
  1. 10) Учитель продолжает рассказ. Этой головоломкой заинтересовался Леонард Эйлер (слайд №5). Слайд №6. Эйлер доказал, что маршрута, который бы отвечал условиям головоломки, не существует, и разработал теорию решения такого рода головоломок, давшую начало новому разделу математики, получившему название «теория графов».

Example.jpg

  1. 11) Учитель вводит понятие «граф». Слайд №7. Схемы, состоящие из точек (кружков) и отрезков, соединяющих пары точек называют графами. Точки графа иначе называют вершинами графа, отрезки – ребрами графа. Ребра графа могут изображаться как прямыми, так и кривыми линиями, а точки могут располагаться произвольно. Так на слайде № 8 изображен один и тот же граф. Если вершина графа не соединена с другими вершинами отрезками, ее называют изолированной. Слайд №9. Если каждая вершина графа соединена отрезками со всеми остальными вершинами, то граф называется полным. Слайд №10.

Example.jpg

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

Example.jpg

  1. 13) Обсуждение решений в группе
  1. 14) Учитель продолжает объяснение. В связи с задачей о Кёнигсбергских мостах возникло понятие эйлерова пути — так называется путь в графе, проходящий по каждому ребру графа ровно один раз. Если начало и конец эйлерова пути совпадают, то он называется эйлеровым циклом, а такой граф называется эйлеровым графом. Степенью вершины графа называется число ребер графа, которым принадлежит эта вершина. Слайд №13. Эйлер доказал, что граф будет иметь эйлеров цикл, если все его вершины имеют четную степень или граф содержит две нечетные вершины. Если же в графе количество нечетных вершин больше двух, то такой граф не обладает ни эйлеровым циклом, ни эйлеровым путем, его нельзя изобразить одним росчерком, не проходя дважды по одному и тому же ребру

Example.jpg

  1. 15) Слайд №14. Задание: Найти на рисунке графы:

a.которые обладают эйлеровым циклом;

b.которые обладают эйлеровым путем;

c.которые не обладают ни эйлеровым циклом, ни эйлеровым путем.

Example.jpg

  1. 16) Учитель просит посмотреть на графы слайда №15 и ответить на вопросы: можно ли их обойти и если можно, то с какой вершины начинать обход и какая окажется в конце пути.

Example.jpg

  1. 17) В ходе дискуссии ребята формулируют гипотезу: Если все вершины графа имеют четную степень, то тогда обход, о котором идет речь, возможен, и начать этот обход можно с любого участка. Если же из этих вершин две нечетные, то и тогда можно совершить обход, но только начало обхода должно быть взято в одной из этих двух вершин, а конец обхода будет во второй нечетной вершине.
  1. 18) Итоги занятия.

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

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

обойти, побывав на каждом мосту ровно один раз и вернувшись в исходную точку


Example.jpg

Литература: 1.Генкин С.А., И.В. Итенберг, Д.В. Фомин. Ленинградские математические кружки: пособие для внеклассной работы. Киров, издательство «АСА», 1994.-272 стр.

2.Гуцанович С.А. Занимательная математика в базовой школе: Пособие для учителей.-Мн.: ТетраСистемс, 2004.-96 стр.

3.Заесенок В.П. Графы в математике и в жизни/Программа интеллектуального развития учащихся/ Выпуск 6/Инновационно-образовательный центр-М.1997-36 стр.

4.http://euler.math.ru.

Личные инструменты
наши друзья
http://аудиохрестоматия.рф/