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

Команда 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) Учитель просит учащихся самостоятельно выполнить задания:  

#13) Обсуждение решений в группе

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

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

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