Графы (проект + презентация)
проект по алгебре (6 класс) на тему

МОУ гимназия, г. Нижневартовска

Проектно-исследовательская работа по математике

ГРАФЫ И ИХ ПРИМЕНЕНИЕ В ПОВСЕДНЕВНОЙ ЖИЗНИ

Выполнили: Харисов Данил

                    Миллер Настя

Научный руководитель:

Павлова Ирина Сергеевна

Нижневартовск, 2010

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. История возникновения графов
2. Задача о Кёнигсбергских мостах.
3. Задачи, решаемые с помощью графов
4. Одним росчерком
5. Применение графов в повседневной жизни

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ВВЕДЕНИЕ

Актуальность.

Объект исследования: Графы.

Предмет исследования: применение графов при решении математических и логических задач.

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

Методология исследования:

• Изучить определение и свойства графа.
• Изучить историю возникновения графов.
• Исследовать роль графов в нашей жизни.
• Научиться применять теорию графов при решении математических и логических задач.

Гипотеза:

1. История возникновения графов.

Эйлер вычислял без всякого видимого усилия,

как человек дышит или как орел парит над землей.

Доминик Араго

Родоначальником теории графов считается Леонард Эйлер (российский и швейцарский математик, внёсший значительный вклад в развитие математики, а также механики, физики, астрономии и ряда прикладных наук). В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

Семь мостов Кенигсберга существовали в Кенигсберге (нынешнем Калининграде) в XVI   XX веках. Взаимное расположение мостов натолкнуло математика Леонарда Эйлера на размышления, приведшие к возникновению теории графов. Возникший в XIII веке город Кенигсберг (ныне Калининград) состоял из трёх формально независимых городских поселений и ещё нескольких «слобод» и «посёлков». Расположены они были на островах и берегах реки Прегель (ныне Преголя), делящей город на четыре главные части: Альтштадт, Кнайпхоф, Ломзе и Форштадт. Для связи между городскими частями уже в XIV веке стали строить мосты. В связи с постоянной военной опасностью со стороны соседних Польши и Литвы, а также по причине междоусобиц между Кёнигсбергскими городами (в 1454—1455 году между городами даже произошла война, вызванная тем, что Кнайпхоф перешёл на сторону Польши, а Альтштадт и Лёбенихт остались верны Тевтонскому ордену) в Средние века кёнигсбергские мосты имели оборонные качества. Перед каждым из мостов была построена оборонительная башня с закрывающимися подъёмными или двустворчатыми воротами из дуба и с железной кованой обивкой. Да и сами мосты приобретали характер оборонительных сооружений. Опоры некоторых мостов имели пятиугольную форму, типичную для бастионов. Внутри этих опор располагались казематы. Из опор можно было вести огонь через амбразуры. Мосты были местом шествий, религиозных и праздничных процессий, а в годы так называемого «Первого русского времени» (1758   1762 годы), когда во время Семилетней войны Кенигсберг ненадолго вошёл в состав Российской империи, по мостам проходили православные крестные ходы. Один раз такой крестный ход даже был посвящен православному празднику Водосвятия реки Прегель, вызвавшему неподдельный интерес у жителей Кенигсберга.

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

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

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

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

• Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

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

2. Задача о Кёнигсбергских мостах.

Через город Калининград, раньше он назывался Кенигсберг, протекает река Преголя. Она делится на два рукава и огибает остров. В XVIII веке в городе было семь мостов, расположенных так, как показано на рис. 1.

                              Рис. 1                                                                                       Рис. 2.

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

Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют графом. Точки А, В, С, D называют вершинами графа, а линии, которые соединяют вершины - ребрами графа. На рис. 34 из вершин В, С, D выходят по 3 ребра, а из вершины А -5 ребер. Вершины, из которых выходит нечетное число ребер, называют нечетными вершинами, а вершины, из которых выходит четное количество ребер, - четными.

Решая задачу про кенигсбергские мосты, Эйлер установил, в частности, свойства графа:

• Если все вершины графа четные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине.
• Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение надо начинать от любой нечетной вершины, а заканчивать на другой нечетной вершине.
• Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.

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

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

Задача №1.

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

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

Решение:

Построим граф (рис. 3.). Сыграно 7 игр.

На рис. 3.  граф имеет 8 ребер, следовательно, осталось провести 8 игр.

Рис.3

Ответ: проведено 7 игр, осталось провести 8 игр.

Задача №2

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

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

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

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

Удастся ли распределить роли так, чтобы исполнители были довольны?

Решение:

Построим граф для ситуации, описанной в задаче (рис. 4.).

         А                     Б                   В                   Г                        Д

Ляпкин-Тяпкин Хлестаков Осип Земляника Городничий
                                                       Рис. 4.

Граф с 10 вершинами и 10 ребрами. Надо выбрать из десяти пять ребер, не имеющих общих вершин: Дима - Осип, Вова -Земляника, Гена - Ляпкин-Тяпкин. Остается два случая: Алик -Хлестаков, Боря - Городничий или Алик - Городничий, Боря -Хлестаков. Как показывает граф, других решений нет.

Задача №3

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

Решение:

      1        2        

5. 4

Рис. 5.

Задача №4.

Головоломка Сэма Лойда

Во дворе, который окружен высоким забором, находятся три домика: красный, желтый и синий. В заборе есть три калитки: красная, желтая и синяя. От красного домика проведите дорожку к красной калитке, от желтого домика - к желтой калитке, от синего - к синей так, чтобы эти дорожки не пересекались.

Решение:

Решение задачи приведено на рис.6.

               Рис. 6.

Задача №5.

Головоломка Генри Э. Дьюдени

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

Рис. 7

Решение:

Задача №6.

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

Ответ: пистолет - в синей, сумочка - в красной, кукла - в зеленой, машинка - в желтой коробках.

Задача №7.

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

1. Володя и член культсектора живут в одном доме, и они вместе с Олей втроем ездят в школу на автобусе;
2. на классном собрании было решено в спортсектор избрать мальчика;
3. член учебного сектора и Сережа вместе ходят на теннисный корт;
4. член спортсектора и Володя - большие друзья;
5. Оля сидит за одной партой с членом учебного сектора.

Решение:

Составим граф из множества ребят и множества секторов.

      Володя                        Толя                     Оля                       Сережа

     шефский                культмассовый         спортивный           учебный

Ответ: Оля - шефский сектор, Володя - учебный сектор, Толя - культмассовый, Сережа - спортивный сектор.

Задача №8.

Сварливые coceдu

Жители пяти домов поссорились друг с другом и, чтобы не встречаться у колодцев, решили, что хозяин каждого дома будет ходить к «своему» колодцу по «своей» тропинке. Удастся ли им это сделать?

Решение:

Рис. 8.

Задача №9.

Муха в банке.

Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все 12 ребер куба, не проходя дважды по одному ребру? Подпрыгивать и перелетать с места на место не разрешается.

Решение.

Ребра и вершины куба образуют граф, все 8 вершин которого имеют кратность 3, и, следовательно, требуемый обход невозможен.

4. Одним росчерком.

Задача №1

Какие буквы русского алфавита можно нарисовать одним росчерком?

Ответ: Б, В, Г, 3, И, Л, М, О, П, Р, С, Ф, Ъ, Ь, Я.

Задача №2

Четыре острова соединены между собой и с берегами реки 14 мостами так, как это показано на рис. 9 (а). Можно ли за одну прогулку обойти все эти мосты, побывав на каждом из них один раз? Если это возможно, то начертите один из маршрутов. Нарисуйте соответствующий граф.

а)                                                     б)                                                  

Рис.9.

Решение:

Имеются две нечетные вершины (В и С) (рис.9(б)). Следовательно, за одну прогулку можно обойти все мосты, побывав на каждом из них один раз. При этом прогулку надо начинать с острова В и заканчивать на острове С или наоборот.

• Число нечетных вершин графа всегда
  четное.
• Если в графе имеются нечетные вершины, то наименьшее число росчерков, которыми можно нарисовать граф, равно поло-
  вине числа нечетных вершин этого графа.

Например, если фигура имеет четыре нечетные вершины, то ее можно начертить, самое меньшее, двумя росчерками (рис. 10).

 2 нечетные вершины – 1 росчерк

Рис. 10.

5. Применение графов в повседневной жизни.

Теория графов находит применение в жизни. С их помощью упрощается решение математических задач, головоломок, задач на смекалку.

• Лабиринт - это граф. А исследовать его - это найти путь в этом графе.
• Типичными графами на географических картах изображения железных дорог.
• Графы есть и на картах звездного неба.
• Графом является и система улиц города. Его вершины – площади и перекрестки, а ребра – улицы.

ЗАКЛЮЧЕНИЕ

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

В математике даже есть специальный раздел, который так и называется: «Теория графов».

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

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

Также было показано практическое применение графов на конкретных примерах, используемые в повседневной жизни. Были решены математические и логические задачи с применением графов.

  Таким образом, выдвинутая гипотеза нашла в работе свое подтверждение, а  все поставленные цели и задачи достигнуты.

СПИСОК ЛИТЕРАТУРЫ

1. «Россыпи головоломок». Ст. Барр М., «Мир», 1987 г.
2. Твое свободное время. Занимательные задачи, опыт, игры. М., «Детская литература»,1975
3. Графы и их применение, О. Оре, Москва, 1979г.
4. Интернет
5. Внеклассная работа по математике, З. Н. Альхова, А.В. Макеева, Саратов., 2003 г.