НПК "Шаг в будущее" тема работы: ГРАФЫ

МКУ «Управление образования администрации МО «Баргузинский район»

МБОУ «Улюкчиканская основная общеобразовательная школа»

671601,Республика Бурятия, с. Улюкчикан, ул. Цыденжапова, 16, тел. 83013194-141.,

 e-mail: ulukschool@mail.ru.

ГРАФЫ

Работу выполнил (а): Зандраев Бэлигто, 8 класс

Научный руководитель: Линхоева Л.Б., учитель математики

                                                                         2015-16 г. 

      Введение
 Актуальность исследования.

    На  одном  из факультативных  занятий по математике  нам, ученикам  5-6 классов,  предложили  задачу  на  вычерчивании фигур одним  росчерком. Какие –то из  этих  фигур нам  удалось начертить сразу, решение других пришло через некоторое время,  а  третьи вообще  не рисуются. Когда  мы спросили у учителя , почему так происходит, она предложила  прочитать книгу о графах.   На одном из занятий  по шахматам в качестве домашнего задания была предложена задача, в которой нужно было просчитать перестановку фигур за меньшее число ходов. Как это сделать? Я стал искать пути решения, и оказалось, что это можно сделать с помощью графов. Раньше понятием «граф» я встречался только на уроке истории при изучении темы дворянство.
Графы заинтересовали меня своей возможностью помогать в решении различных головоломок, математических и логических задач. Теория графов  стала в наши дни  одной из  наиболее  бурно развивающихся частей  комбинаторики. Это объясняется тем, что в виде графовых моделей описываются многие объекты и ситуации: коммуникационные сети, схемы электрических и электронных приборов, химические молекулы, отношения между людьми, всевозможные транспортные схемы и многое-многое другое. Очень важное, для нормального функционирования общественной жизни. Именно этот фактор определяет актуальность их более подробного изучения. Я решил разобраться, какую роль в обычной жизни играют графы.
 
Целью   данной работы является исследование  роли графов в нашей жизни.
Задачи исследования:

1.познакомиться с историей возникновения графов;

2.познакомиться с основными понятиями графа, видами, элементами;

3.научиться решать задачи с помощью графов;

4.составить своё родословное дерево.

Методы исследования: частично - поисковый, аналитический.

Объект исследования: понятие граф


Предмет исследования: степень распространенности применения графов

                                  Основная часть
1. Понятие графа

   На первом слайде портрет великого  русского писателя, графа Льва Николаевича  Толстого.  И здесь же схема  московского  метро. Слово «граф» имеет несколько значений, и схема метро – это  математический  граф.  Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. С дворянским титулом «граф» их связывает общее происхождение от латинского слова «графио» - пишу.
    В математике определение графа дается так: «графом называется конечное множество точек, некоторые из которых соединены линиями».  
Граф состоит из вершин и линий связи. Вершины могут быть изображены кругами, овалами, точками, прямоугольниками. Вершины могут быть связаны дугами или ребрами.
Связи между вершинами изображаются линиями. На  схеме метро вершины – станции, ребра – пути, соединяющие эти станции. Рассмотрим  такую  задачу.  Перед нами граф – «распечатанное письмо». Начертить  этот  граф,  не отрывая карандаша от бумаги и не  проводя по  одной  линии дважды.  Чтобы  решить эту  задачу нам  нужно  перенестись на  более чем 200 лет  назад  и  оказаться  вместе  с великим российским математиком, швейцарцем  по происхождению, Леонардом Эйлером в городе Кенигсберге (сейчас  этот  город  называется Калининград)   Бывший Кенигсберг   расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены.

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам, не проходя ни по одному из них дважды? Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.

Этот вопрос привлек внимание ученых разных стран. В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно).

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


Рисунок 1
На упрощённой схеме части города (графе) мостам соответствуют линии (рёбра графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:
Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа всегда чётно. Невозможно начертить граф, который имел бы нечётное число нечётных вершин.
Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

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

Граф кёнигсбергских мостов имел четыре нечётные вершины, следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
Решая задачу про кенигсбергские мосты, Эйлер установил, в частности, свойства графа:
1.Если все вершины графа четные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине.
2.Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение надо начинать от любой нечетной вершины, а закончить на другой нечетной вершине.
3.Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.
В задаче о кенигсбергских мостах все четыре вершины соответствующего графа нечетные, то есть нельзя пройти по всем мостам один раз и закончить путь там, где он был начат.

Следующая задача. В Санкт –Петербурге 342 моста. На слайде фрагмент карты города, на которой указаны 8 островов и 17 мостов. Требуется  разработать экскурсионный маршрут «Город  мостов и белых ночей » по этим местам.  Начинаться и заканчиваться он должен в одном и том же месте, и туристы не должны проезжать по одному мосту дважды.

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

И еще можно привести очень много различных примеров… 

  Решение задач с помощью графов «Один день из жизни Графа»

Рассмотрим решение задач с помощью графов из школьной жизни.

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


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


Количество рукопожатий равно количеству рёбер, т.е.3.

2)Встретились четверо:


Количество рёбер 6; возможно 6 рукопожатий.
3)Встретились пятеро:










В графе 10 рёбер; возможно 10 рукопожатий.
Ответ: 1)3; 2)6; 3)10.
По расписанию у нас шесть уроков: геометрия, история, информатика, география, русский язык и физика.
Задача 3.На уроке геометрии было предложено построить граф классификации геометрических объектов. Это оказалось легко сделать с помощью понятия граф.


Задача 4. А на уроке истории нужно было составить родословное дерево. Родословное дерево. Использует графы и дворянство. Например, в генеалогическом дереве, вершины – члены рода, а связывающие их отрезки – отношения родственности.
Всем известно, что слово «граф» означает дворянский титул, например граф Лев Николаевич Толстой. На рисунке еще один граф – часть генеалогического древа графа Л.Н. Толстого. Здесь вершины – предки писателя, а ребра показывают родственные связи между ними.
 

Задача 5. На уроке русского языка тема «Числительные» и учитель предложила нам составить опорный конспект.

Числительные в русском языке классифицируются по составу и по значению. По составу они делятся на простые, сложные и составные. Пример простых числительных: четыре, пять. Пример сложных числительных : шестьдесят, пятьсот. Пример составных числительных: 35, 154. По значению числительные делятся на порядковые и количественные. Пример порядковых числительных: второй, девятый. Пример количественных числительных: шесть, два.


После занятий мы все побежали в столовую, где был предложен комплексный обед. Я люблю борщ, а мой сосед по парте рассольник.

Задача 6. В столовой предлагают два первых блюда: борщ, рассольник, а также четыре вторых блюда: гуляш, котлеты, сосиски, пельмени. Укажите все обеды из двух блюд, которые может заказать посетитель. Проиллюстрируйте ответ, построив дерево возможных вариантов.
Решение.
Чтобы указать все обеды из двух блюд, будем рассуждать так.
Выберем одно первое блюдо (борщ) и будем добавлять к нему поочерёдно разные вторые
блюда, получим пары:
б - г, б – к, б – с, б – п. (4 пары).
Теперь в качестве первого блюда выберем рассольник и будем добавлять к нему поочерёдно разные вторые блюда:
р – г, р – к, р – с, р – п. (4пары).
Таким образом, всего есть 2 ∙ 4 = 8 вариантов обеда из двух блюд, которые может заказать посетитель.
Ответ: 6 сочетаний.

Вечером мама попросила меня сходить в магазин за хлебом. Система «Хлебный магазин» состоит из следующих элементов: хлеб, продавец, покупатель, прилавок, автомобиль, шофер, грузчик, деньги, чек. Вершинами графа являются перечисленные объекты, а дуги – отношения между ними. Возвращаясь, домой с магазина, я невольно поймал себя на мыслях о графах: везде и повсюду меня окружают Графы.  

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

В математике даже есть специальный раздел, который так и называется: «Теория графов». Графы представляют изучаемые факты в наглядной форме. Приёмы решения логических задач с использованием графов подкупают своей естественностью и простотой, избавляют от лишних рассуждений, во многих случаях сокращающих нагрузку на память.
Теория графов  стала в наши дни  одной из  наиболее  бурно развивающихся частей  комбинаторики.
   Это объясняется тем, что в виде графовых моделей описываются многие объекты и ситуации: коммуникационные сети, схемы электрических и электронных приборов, химические молекулы, отношения между людьми и многое другое.
Графовые задачи обладают рядом достоинств, позволяющих их использовать для развития воображения и улучшения логического мышления, применимы в решении многих геометрических задач.
                                           

                                        Литература 
1. Гарднер М. Математические головоломки и развлечения. – М. «Мир», 1971.
2.Гарднер М. Крестики-нолики. М., «Мир», 1988.
3.Графы // Квант. 1994. - №6.
4.Игнатьев Е.И. В царстве смекалки. Ростов-на-Дону, Ростовское книжное издательство, 1995.
5.Кордемский Б.А. Математические завлекали. – М.: Издательский дом Оникс: Альянс – В, 2000.
6.Перельман Я.И. Занимательные задачи и опыты. – М, «Детская литература», 1972.
7.Топология графов // Квант. – 2005. - №3.
8.Энциклопедия для детей. Том 11. Математика. Тема «Графы». – М.: Аванта, 1998.