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

Материал из ТолВИКИ
(Различия между версиями)
Перейти к: навигация, поиск
Строка 42: Строка 42:
  
 
#11) Учитель вводит понятие «граф». Слайд №7. Схемы, состоящие из точек (кружков) и отрезков, соединяющих пары точек называют графами. Точки графа иначе называют вершинами графа, отрезки – ребрами графа. Ребра  графа могут изображаться как прямыми, так и кривыми линиями, а точки могут располагаться произвольно. Так  на слайде № 8 изображен один и тот же граф. Если вершина графа не соединена с другими вершинами отрезками, ее называют изолированной. Слайд №9. Если каждая вершина графа соединена отрезками со всеми остальными вершинами, то граф называется полным. Слайд №10.
 
#11) Учитель вводит понятие «граф». Слайд №7. Схемы, состоящие из точек (кружков) и отрезков, соединяющих пары точек называют графами. Точки графа иначе называют вершинами графа, отрезки – ребрами графа. Ребра  графа могут изображаться как прямыми, так и кривыми линиями, а точки могут располагаться произвольно. Так  на слайде № 8 изображен один и тот же граф. Если вершина графа не соединена с другими вершинами отрезками, ее называют изолированной. Слайд №9. Если каждая вершина графа соединена отрезками со всеми остальными вершинами, то граф называется полным. Слайд №10.
[[Изображение:gr7.gif]] [[Изображение:gr8.gif]] [[Изображение:gr9.gif]] [[Изображение:gr10.gif]]
+
[[Изображение:gr7.gif]] [[Изображение:gr8.jpg]] [[Изображение:gr9.jpg]] [[Изображение:gr10.jpg]]
  
 
#12) Учитель просит учащихся самостоятельно выполнить задания:  
 
#12) Учитель просит учащихся самостоятельно выполнить задания:  
Строка 51: Строка 51:
 
  3) Слайд №12.  Найти три пары одинаковых графов.
 
  3) Слайд №12.  Найти три пары одинаковых графов.
  
[[Изображение:gr12.gif]]
+
[[Изображение:gr12.jpg]]
  
 
#13) Обсуждение решений в группе
 
#13) Обсуждение решений в группе
  
 
#14) Учитель продолжает объяснение. В связи с задачей о  Кёнигсбергских мостах возникло понятие эйлерова пути — так называется путь в графе, проходящий по каждому ребру графа ровно один раз. Если начало и конец эйлерова пути совпадают, то он называется эйлеровым циклом, а такой граф называется эйлеровым графом. Степенью вершины графа называется число ребер графа, которым принадлежит эта вершина. Слайд №13. Эйлер доказал, что граф будет иметь эйлеров цикл, если все его вершины имеют четную степень или граф содержит две нечетные вершины. Если же в  графе количество нечетных вершин больше двух, то такой граф не обладает ни эйлеровым циклом, ни эйлеровым путем, его нельзя изобразить одним росчерком, не проходя дважды по одному и тому же ребру
 
#14) Учитель продолжает объяснение. В связи с задачей о  Кёнигсбергских мостах возникло понятие эйлерова пути — так называется путь в графе, проходящий по каждому ребру графа ровно один раз. Если начало и конец эйлерова пути совпадают, то он называется эйлеровым циклом, а такой граф называется эйлеровым графом. Степенью вершины графа называется число ребер графа, которым принадлежит эта вершина. Слайд №13. Эйлер доказал, что граф будет иметь эйлеров цикл, если все его вершины имеют четную степень или граф содержит две нечетные вершины. Если же в  графе количество нечетных вершин больше двух, то такой граф не обладает ни эйлеровым циклом, ни эйлеровым путем, его нельзя изобразить одним росчерком, не проходя дважды по одному и тому же ребру
[[Изображение:gr13.gif]]
+
[[Изображение:gr13.jpg]]
  
 
#15) Слайд №14. Задание: Найти на рисунке графы:
 
#15) Слайд №14. Задание: Найти на рисунке графы:
Строка 66: Строка 66:
 
c.которые не обладают ни эйлеровым циклом, ни эйлеровым путем.
 
c.которые не обладают ни эйлеровым циклом, ни эйлеровым путем.
  
[[Изображение:gr14.gif]]
+
[[Изображение:gr14.jpg]]
  
 
#16) Учитель просит посмотреть на графы слайда №15 и ответить на вопросы: можно ли их обойти и если можно, то с какой вершины начинать обход и какая окажется в конце пути.
 
#16) Учитель просит посмотреть на графы слайда №15 и ответить на вопросы: можно ли их обойти и если можно, то с какой вершины начинать обход и какая окажется в конце пути.
[[Изображение:gr15.gif]]
+
[[Изображение:gr15.jpg]]
  
 
#17) В ходе дискуссии ребята формулируют гипотезу: Если все вершины графа имеют четную степень, то тогда обход, о котором идет речь, возможен, и начать этот обход можно с любого участка. Если же из этих вершин две нечетные, то и тогда можно совершить обход, но только начало обхода должно быть взято в одной из этих двух вершин, а конец обхода будет во второй нечетной вершине.
 
#17) В ходе дискуссии ребята формулируют гипотезу: Если все вершины графа имеют четную степень, то тогда обход, о котором идет речь, возможен, и начать этот обход можно с любого участка. Если же из этих вершин две нечетные, то и тогда можно совершить обход, но только начало обхода должно быть взято в одной из этих двух вершин, а конец обхода будет во второй нечетной вершине.
Строка 87: Строка 87:
  
  
[[Изображение:gr16.gif]]
+
[[Изображение:gr16.jpg]]
  
 
'''Литература:'''
 
'''Литература:'''

Версия 21:04, 6 ноября 2007

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

Команда 061

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

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

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


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

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

Gr1.jpg

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

Gr2.gif

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

[[Изображение:]]

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

Example.jpg

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

Gr6.gif

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

Gr7.gif Gr8.jpg Gr9.jpg Gr10.jpg

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

Gr12.jpg

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

Gr13.jpg

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

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

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

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

Gr14.jpg

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

Gr15.jpg

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

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

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

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


Gr16.jpg

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

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

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

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

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