Графы
план-конспект урока по геометрии (6 класс) по теме

Методическая разработка

 по геометрии

«Графы»

6  класс

Подготовила:  учитель математики

                          Самойленко Е.А.

Урок 13.   Графы.

Тип урока: урок изучения нового материала.

Характеристика темы урока. Содержанием темы являются понятия: граф, узлы графа, задачи на вычерчивание фигур одним росчерком.

Цели урока: 

1. Образовательные

1. Сформировать понятия  граф, узлы графа;
2. Показать применение этих понятий при решении различных практических задач:

• задачи на вычерчивание одним росчерком;
• задачи на прохождение всех комнат лабиринта,
• задача о кенигсбергских мостах.

1. 2.    Воспитательные:
2. Организация внимания у учащихся;
3. Повышение интереса к предмету;
4. Формирование сознательного отношения к труду.
5. Культура оформления записей в тетради.

3.   Развивающие:

Развитие творческих способностей учащихся, умений сравнивать,  анализировать, делать выводы.

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

Методы обучения:  эвристический, иллюстративный, исследовательский методы.

Структура урока.

1. Организационный момент.
2. Проверка домашнего задания.
3. Изучение нового материала.
4. Закрепление нового материала.
5. Подведение итогов, домашнее задание.

Ход урока.

1. Организационный момент.
2. Проверка домашнего задания. На предыдущем уроке учащимся были предложены в качестве домашнего задания следующие задачи:

Задача 1. Что получится, если ленту перекрутить на три оборота и склеить.

1. Взять бумажную ленту.
2. Повернуть один из концов полоски на три оборота, т.е. на 540 градусов.
3. Склеить концы ленты.
4. Теперь возьмите ножницы и аккуратно разрежьте полоску посередине. Результаты занести в таблицу.

Задача 2.   Не отрывая карандаша от бумаги и не проводя два раза по одной и той же линии, требуется начертить фигуры:

а)                                                                      б)

Первое задание было направлено на закрепление материала по теме «Лист Мебиуса», второе дано в опережающем плане для изучения нового материала к уроку 13. Учитель заранее предупреждает учащихся, что не у всех может получится вычертить данную фигуру, но у кого получится вычертить обе фигуры, обязательно будет отмечен и получит оценку «5».

При проверке домашнего задания проверяются результаты эксперимента (задание 1), которые учащиеся должны были занести в таблицу.

При проверке задачи 2 выясняется, что с первой частью задания справились практически все учащиеся, но вторую часть задания выполнить не смогли. В чем причина? Не получается вычертить данную фигуру, не отрывая карандаша от бумаги и не проводя два раза по одной и той же линии.

3. Объяснение нового материала. Формулирование темы, целей, задач урока.

Учитель: Оказывается, не всегда можно начертить фигуру, не отрывая карандаша от бумаги и не проводя два раза по одной и той же линии. А для того, чтобы ответить на вопрос: «Почему так происходит?», необходимо изучить новый материал. Данная задача относится к топологическим задачам на вычерчивание фигур одним росчерком. Связную сеть кривых, которую вы построили в задаче №2 под буквой а), носит название «граф», поэтому и тема сегодняшнего урока и будет посвящена этому понятию. На доске записывается тема урока, формулируются цели, задачи урока.  

Впервые основы теории графов появились в работе Л.Эйлера, где он описывал решения головоломок и математических развлекательных задач, а широкое развитие теория графов получила с 50-х гг. XX века в связи со становлением кибернетики и развитием вычислительной техники.

Слово «граф» произошло от греческого слова grapho – «пишу». В математике графом называют совокупность точек, соединенных линиями, а точки, в которых соединяются линии – узлами графа. Сами линии по-другому называют ребрами графа.

Узлы                                  

графа                   Ребра                          

                  графа

Задание 1. Посчитайте, сколько всего на этом графе узлов и сколько ребер?

Задание 2. Найдите на следующем слайде графы и посчитайте количество узлов и количество ребер графа.

Рис. 1                                 Рис. 2                 Рис. 3                                               Рис. 4

Задание 3. При взгляде на географическую карту сразу бросается в глаза сеть железных дорог, автомобильных дорог. Является ли она графом? Что в этом случае будет узлами, а что – ребрами? Приведите свои примеры графов, которые мы можем встретить в повседневной жизни.

Учитель: графы бывают полными и неполными. Граф называется полным, если каждые два его узла соединены ребрами. В противном случае граф – неполный.

Граф

Полный              Неполный   

Граф,  каждые два узла которого

соединены ребрами

Задание 4. Найдите на рис. 1- 4 полные и неполные графы. Ответ обоснуйте.

Задание 5. Чем ещё отличается граф на рис. 4 от графов на рис. 1, рис.3?

Учащиеся:  на ребрах нанесены стрелки, указывающие направление ребер.

Учитель:  Такой граф называют направленным. А можно ли из графов на рис. 1 и рис.3 сделать направленные графы? 

Граф

Направленный             Ненаправленный

Задание 6. Постройте свой граф, который является направленным.

Учащиеся выполняют задание в тетради, учитель, проходя по рядам, просматривает выполнение задания.

 Задание 7.  Вернемся к домашней задаче №2. Можно ли назвать фигуры – графом?

Назовите количество узлов, подпишите каждый узел. Назовите количество ребер графа. Является ли он полным? Направленным?

Одно из возможных решений задачи под буквой а).

                   Рис. 5        2                             Рис. 6            2

                         1                        3                         1                        3

                                                                                       9      8

                       4                           5                        4       6      7        5                    

   Чем отличаются эти два графа? Учащиеся перечисляют отличия графов.

Учитель: Если мы посмотрим на граф, то можно заметить, что в  узлах соединяется разное количество ребер. В узле 1 на рис. 5 соединяются три ребра, в узле 2 – два ребра.

Узел, в котором соединяется четное число ребер называют четным, а нечетное – нечетным. 1 узел – нечетный, 2 узел – четный.

Задание 8.  Перечислите по рис.5, рис.6 четные и нечетные узлы.

Помимо всех перечисленных отличий, у этих графов есть еще одно очень важное отличие, из-за которого первый граф можно вычертить указанным способом, а второй – нет. Зная его, можно по виду графа или фигуры определить можно его вычертить одним росчерком или нет. Чтобы отыскать это свойство графа, предлагаю вам выполнить следующую лабораторную работу. На столах имеются заготовки таблиц. В первом столбике изображены графы. Необходимо  подсчитать количество четных и нечетных узлов и результаты подсчетов занести в таблицу.                

Учащиеся. Выполняют лабораторную работу, результаты заносят в таблицу.

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

Свойство. Если в фигуре (на графе) число нечетных узлов больше двух, то её нельзя нарисовать одним росчерком!

Свойство 2. Число нечетных узлов графа всегда четно.

Учитель. Давайте теперь вернемся к домашней задаче №2 и проверим количество нечетных узлов в фигурах.

                     Рис.  7    2                             Рис. 8            2

                         1                        3                         1                        3

                                                                                       9      8

                       4                          5                         4       6      7        5                    

На рис. 7 нечетные узлы – 1, 3, т.е. всего их два. На рис. 8 нечетные узлы – 1, 3, 7, 6, т.е. – четыре. Во втором случае число нечетных узлов больше двух, поэтому вторую фигуру нельзя нарисовать одним росчерком!

4. Закрепление изученного материала.

1. Можно ли одним росчерком вычертить фигуры, изображенные на слайде и почему?

Решение. Первую фигуру указанным способом вычертить нельзя (число нечетных узлов больше двух), вторую – можно.

                                                 9               4   8                     7  

                                             3                   2    5                   6  12

                                          10  1                                          11          

2. Задача «о кенигсбергских мостах». Раньше город Кенигсберг был расположен на берегах и двух островах реки Преголь. Различные части города были соединены семью мостами (слайд). Совершая прогулки в воскресные дни, горожане заспорили: можно ли выбрать маршрут так, чтобы пройти один и только один раз по каждому мосту и затем вернуться в начальную точку пути?

Учитель. Долго бы спорили жители города, если бы через Кенигсберг не проезжал Леонард Эйлер. Он заинтересовался спором и … разрешил его. А сможете ли это сделать вы?

                                           А

        1

                                    2      

                                                                                  3

                                                     р. Преголь

                              В                       4                   

                                                                                   С

                5                                                            

                                   6  

                                                                                    7                              

                                                  D                

Решение.  План города для решения этой задачи можно изобразить графом, который будет иметь четыре узла графа – это берега A и D, острова В и С; 7 ребер – мосты 1 – 7. Если бы существовал искомый маршрут, то этот граф можно было бы вычертить одним росчерком. Чего сделать нельзя, так как количество нечетных узлов больше двух.

                                 А

             В

                                                             С

                                D

3. На слайде изображен план подвала из десяти комнат. Можно ли пройти через все двери всех комнат, запирая каждый раз ту дверь, через которую вы проходите? С какой комнаты надо начинать движение?

Решение.  Необходимо начать с нечетного узла.

5. Подведение итогов, домашнее задание.

1. Можно ли начертить фигуры одним росчерком. Если да, то как это сделать?

Использованная литература:

1. И.Ф. Шарыгин, Л.Н.Ерганжиева «Наглядная геометрия, 5-6 классы». М., Дрофа, 1998 г.
2. Энциклопедический словарь юного математика./Сост. А.П.Савин.-М.: Педагогика, 1985 г.

Задачи, решаемые с помощью теории графов.

1. Почтальон Печкин разнес почту во все дома деревни, после чего зашел с посылкой к дяде Федору. На рисунке показаны все тропинки, по которым проходил Печкин, причем, как оказалось, ни по одной из них он не проходил дважды. Каков мог быть маршрут почтальона Печкина? В каком доме живет дядя Федор?

Решение: тропинки образуют сеть с двумя «нечетными» узлами – у почты и дома №5. Начало маршрута на почте, а конец у дома №5 – там и живет дядя Федор.

2. Кто играет Ляпкина-Тяпкина?

             В школьном драмкружке решили ставить гоголевского «Ревизора». И тут разгорелся жаркий спор. Все началось с Ляпкина-Тяпкина.

   - Ляпкиным-Тяпкиным буду я! – решительно заявил Гена.

   - Нет, я буду Ляпкиным-Тяпкиным, - возразил Дима. – С раннего детства мечтал воплотить этот образ на сцене.

   - Ну, хорошо, согласен уступить эту роль, если мне дадут сыграть Хлестакова, - проявил великодушие Гена.

   - …А мне – Осипа – не уступил ему в великодушии Дима.

   - Хочу быть Земляникой или Городничим, - сказал Вова.

   - Нет, Городничим буду я, - хором закричали Алик и Боря. – Или Хлестаковым, - добавили они одновременно.

Удастся ли распределить роли так, чтобы исполнители были довольны? (Мы не спрашиваем, будут ли довольны зритель.)

3.  Корзины, полные хлебцов. 

            В пяти корзинах лежат хлебцы пяти сортов. Хлебцы первого сорта лежат в корзинах Г и Д; хлебцы второго сорта – в корзинах А, Б и Г; в корзинах А, Б и В имеются хлебцы пятого сорта, в корзине В имеются к тому же хлебцы четвертого сорта, а в корзине Д – третьего. Требуется дать каждой корзине номер, но так, чтобы в корзине № 1 были хлебцы первого сорта (хотя бы один), в корзине № 2 – второго и т.д.

       А                    Б                    В                     Г                     Д

    4.  Первенство классов.

            В первенстве класса по настольному теннису принимали участие 6 учеников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводится по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной и Еленой; Борис, как уже говорилось, с Андреем и еще с Галиной; Виктор – с Галиной, Дмитрием и Еленой; Галина – с Андреем и Виктором. Сколько игр проведено к настоящему моменту и сколько еще осталось?

5. Задача о трех домах и трех колодцах.

Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 2). Эта задача была решена (показано, что решение не существует) Куратовским в 1930 году (см. рис.).

6. Задача о четырех красках.

Разбиение на плоскости на непересекающиеся области называется картой. Области на карте называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом (рис. 12).

С конца позапрошлого века известна гипотеза, что для этого достаточно четырех красок. В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которое базировалось на переборе вариантов с помощью компьютера. Решение этой задачи «программным путем» явилось прецедентом, породившим бурную дискуссию, которая отнюдь не закончена. Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера. Проверить «вручную» полученное решение невозможно – объем перебора выходит далеко за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки… Методы формального доказательства правильности программ не применимы к программам такой сложности, как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок и в данном случае вообще невозможно. Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они сделали все правильно.

7. Задачи Дьюдени.

1. Смит, Джонс и Робинсон работают в одной поездной бригаде машинистом, кондуктором и кочегаром. Профессии их названы не обязательно в том же порядке, что и фамилии. В поезде, который обслуживает бригада, едут трое пассажиров с теми же фамилиями. В дальнейшем каждого пассажира мы будем почтительно называть «мистер» (м-р)

2. М-р Робинсон живет в Лос-Анджелесе.

3. Кондуктор живет в Омахе.

4. М-р Джонс давно позабыл всю алгебру, которой его учили в колледже.

5. Пассажир – однофамилец кондуктора живет в Чикаго.

6. Кондуктор и один из пассажиров, известный специалист по математической физике, хотя в одну церковь.

7. Смит всегда выигрывает у кочегара, когда им случается встречаться за партией в бильярд.

Как фамилия машиниста? (рис.13)

Здесь 1-5 – номера ходов, в скобках – номера пунктов задачи, на основании которых сделаны ходы (выводы).

Далее следует из п.7, что кочегар не Смит, следовательно, Смит-машинист.