План занятий 1-2 на тему: «Теория графов»

План занятий 1-2 на тему: «Теория графов»

Цели урока:

• познакомить учащихся с понятием “Граф”, основными принципами его построения;

• формировать умение выделять отношения, связывающие объекты;

• развивать внимание, способность к логическому рассуждению;

• воспитывать взаимопомощь, умение работать в коллективе

• закрепление полученных знаний на практике

• развитие памяти, внимания;

• развитие самостоятельности;

• воспитание познавательной активности.

Оборудование:

• компьютерный класс, оснащенный современной техникой, видеопроектор, экран;

• компьютеры с ОС Windows XP, программа Microsoft Office 2003 PowerPoint;

• оборудование доски (тема урока, новые термины). Раздаточный материал.

План урока.

I. Организационный момент. Актуализация знаний.

II. Изложение нового материала. (10 мин. )

III. Закрепление материала. Практическая работа. (15-20 мин.)

IV. Подведение итога урока.(2 мин)

V. Домашнее задание.

I. Организационный момент. Актуализация знаний.

Здравствуйте! Наш урок называется “Графы”. Мы познакомимся с понятие “Графы”, научимся их изображать и решать задачи по этой теме.

II Изложение нового материала.

Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 г.), хотя термин “граф” впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых (примеры графов изображены на рисунке 1)

 С помощью графов часто упрощалось решение задач, сформулированных в различных областях знаний: в автоматике, электронике, физике, химии и др. С помощью графов изображаются схемы дорог, газопроводов, тепло- и электросети. Помогают графы в решении математических и экономических задач.

Граф – (от греческого grapho – пишу) - это средство наглядного представления элементов объекта связей между ними. Это замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач.

Граф – это некоторая информационная модель

Граф состоит из вершин или узлов, связанных дугами или отрезками - рёбрами. Линия может быть направлена, т. е. иметь стрелку (дуга), если не направлена – ребро. Две вершины, соединённые дугой или ребром называются смежными.

Примеры графов (Слайд 4, 5, 6)

Задание 1 (Слайд 7):

Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам:

Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс; Марс – Уран.

Можно ли долететь на рейсовых ракетах с Земли до Марса ?

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

Теперь сразу видно, что долететь с Земли до Марса нельзя.

Две вершины, соединённые дугой или ребром называются смежными. Каждому ребру или дуге соотносится какое-нибудь число. Число может обозначать расстояние между населёнными пунктами, время перехода от одной вершины к другой и т. д.

Задание 2 (9 слайд) – решение у доски. Маша пришла в зоопарк и хочет увидеть как можно больше зверей. По какой тропинке ей надо идти? Желтая, красная, зеленая?

Задание 3 (11 слайд) – решение у доски. Пять футбольных команд А, Б, В, Г, Д должны сыграть в матчи друг с другом. Уже сыграли А с Б, В, Г; Б с А, В, Д. сколько матчей уже сыграно? Сколько осталось сыграть?

Представление графов (Слайд 12)

Граф может быть представлен в виде списка дуг (АВ; 7), графически или с помощью таблицы.

 развернуть таблицу

 развернуть таблицу

III. Закрепление материалы: учащимся предлагается разделить на группы и выполнить задания. Работая в малой группе, ученики обсуждают модели, основываясь на теоретических знаниях, полученных в начале урока. Тем самым достигается повторение и закрепление материала.

Задание 2 (Слайд 13)

Задание 3 (Слайд14)

Приложене 1

IV. Итог урока

Ребята, какие новые слова вы сегодня узнали? (Граф, вершина графа, ребра графа.)

- Что могут обозначать вершины графа? (Города; объекты, которые; связаны.)

- Что обозначают ребра графа (Пути, движения, направления)

Приведите пример, где в жизни мы можем с ними встретиться?

Как изображаются графы?

V. Домашнее задание. (Слайд 15)