ХХV РАЙОННЫЙ КОНКУРС ТВОРЧЕСКИХ ИССЛЕДОВАТЕЛЬСКИХ РАБОТ ШКОЛЬНИКОВ     СЕКЦИЯ МАТЕМАТИКИ     «ГРАФ ГОРОДА БАРАБИНСК»                                           2022 год

 

СОДЕРЖАНИЕ

ВВЕДЕНИЕ………………………………………………………………….…3

I.ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

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

1.2  Виды графов……………………… …….…………………………….. ...…..6

1.3  Некоторые задачи теории графов …………………………………………..7

II. ПРАКТИЧЕСКАЯ ЧАСТЬ

2.1 Применение графов в различных сферах деятельности ….………..…..…11

2.2  Моделирование графа с учетом ветвей дорог города Барабинск..………12

ЗАКЛЮЧЕНИЕ………………………………………………………………...14

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

ПРИЛОЖЕНИЯ……………………………………………………………..…16

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

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

В этом году я была участником дистанционной олимпиады.  В ней была предложена такая задача: «Почтальон Печкин разнёс почту во все дома деревни, после чего зашёл к дяде Фёдору выпить молока. На рисунке показаны все тропинки, которые проходил Печкин, причём как оказалось, ни одной из них он не проходил дважды. Каким маршрутом шёл почтальон Печкин? В каком доме живёт дядя Фёдор?» (Приложение 2)

Разбирая решение этой задачи, я задалась вопросом: «Можно ли решить эти задачи не перебором, а другим, более быстрым, способом?». Я обратилась к своему учителю, и  мне объяснили, что решить эту задачу я могу, изучив теорию графов. Но прежде, чем найти ответ на свой вопрос, я увидела, что теория графов помогает упростить решение многих задач. Графы заинтересовали меня своей возможностью помогать в решении различных головоломок, математических, логических, а также жизненных задач.

Гипотеза: знания о теории графов помогают решать разные задачи быстрым способом.

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

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

Цель исследования: проверить, можно ли построить маршрут движения учащихся между школами города Барабинск, не проходя по одной и той же дороге дважды.

Задачи исследования:

1.       Изучить основные понятия теории графов и виды графов.

2.       Рассмотреть способы решения задач с помощью графов.

3.       Показать применение теории графов в различных областях жизни человека.

4.       Построить модель графа, взяв за его вершины расположение школ города Барабинск, а за ребра дороги города.

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

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

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

 

 

 

 

 

 

 

 

 

 

I.ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

 

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

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

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

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

1)           Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа всегда четно. Невозможно начертить граф, который имел бы нечётное число нечётных вершин.

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

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

Термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Широкое развитие теория графов получила в 50-х  годах 20 века в связи со становлением кибернетики и развитием вычислительной техники. Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. С дворянским титулом «граф» их связывает общее происхождение от латинского слова «графио» - пишу.

1.2     Виды графов

  В математике определение графа дается так: «графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами».

Графы бывают разные по виду и носят свои названия (Приложение 4). Схема графа, состоящая из «изолированных» вершин, называется нулевым графом. Графы, в которых не построены все возможные ребра, называются неполными графами. Графы, в которых построены все возможные ребра, называются  полными графами.  Если на ребрах графа нанесены стрелочки, указывающие направление ребер, то такой граф называют направленным (ориентированным).

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

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

Две вершины А и В графа называются связными, если в графе существует путь с концами А и В. Граф называется связным, если каждые две вершины его связные. Две вершины графа называются несвязными, если в графе не существует ни одного пути, связывающего их. Граф называется несвязным, если хотя бы две вершины его не­связные.

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

Деревом называется любой связный граф, не имеющий циклов. Циклом называется путь, в котором совпадают начало с концом. Если все вершины цикла разные, то такой цикл называется элементарным (или простым) циклом. Если же цикл включает в себя все ребра графа по одному разу, то такой цикл называется Эйлеровой линией. Путем в графе от одной вершины к другой называется такая последовательность ребер, по которой можно проложить маршрут между этими вершинами. При этом никакое ребро маршрута не должно встречаться более одного раза. Вершина, от которой проложен маршрут, называется началом пути, вершина в конце маршрута — конец пути. Висячей вершиной называется вершина, из которой выходит ровно одно ребро.

1.3  Некоторые задачи теории графов

Эйлеров путь -  путь в графе, проходящий через каждое ребро ровно один раз.

Закономерность 1.

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

Закономерность 2.

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

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

1)    преобразовать рисунок в граф (определить его вершины и рёбра);

2)    определить степень каждой вершины;

3)    посчитать количество нечётных вершин;

4)    сделать выводы:

         а) заданный обход возможен, если все вершины чётные (его можно начать  с любой вершины); две вершины нечётные (его нужно начать с одной из нечётных вершин);

     б) заданный обход невозможен, если нечётных вершин больше двух;

5)  указать начало и конец пути.  

Я, изучив эти выводы, решила проверить их на примерах задач из раздела теории графов. (Приложение 5)

Решение задач о вычерчивании фигур одним росчерком

Задача №1

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

Решение: 1) Можно, т. к. только 2 нечетные вершины. 2) Нельзя, т. к. 4 нечетные вершины.

Задача №2

Говорят, что Магомет вместо подписи (он был неграмотен) описывал одним росчерком состоящий из двух рогов луны знак, представленный на рисунке. Возможно ли это?

Решение: Да, т.к. в этом случае вершин четный порядок.

Задача №3 (Муха в банке)

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

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

Задачи с лабиринтами

Кроме задач вида «одним росчерком» полученным способом можно решать задачи с лабиринтом. Слово «лабиринт» (греческое) означает «ходы в подземельях». Решению задачи о лабиринтах предпосылаются исторические справки – чтобы показать интерес к этой задаче и дать наглядное представление о существовавших и существующих лабиринтах. Задача о прохождении лабиринта приобретает практический интерес, поскольку устройство линий электропередач, канализации, сетей дорог, каналов и т.д. – все это более или менее сложные лабиринты. Начало решению вопроса о существовании безвыходных лабиринтов положено Эйлером.

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

ü    МЕТОД ПРОБ И ОШИБОК. Выбирайте любой путь, а если он заведет вас в тупик, то возвращайтесь назад и начинайте все сначала.

ü    МЕТОД ЗАЧЕРКИВАНИЯ ТУПИКОВ. Начнем последовательно зачеркивать тупики, т.е. маршруты, не имеющие ответвлений и заканчивающиеся перегородкой. Незачеркнутая часть коридоров будет выходом или маршрутом от входа к выходу или к центру.

ü    ПРАВИЛО ОДНОЙ РУКИ. Оно состоит в том, что по лабиринту надо двигаться, не отрывая одной руки от стены.

Рассмотрим задачу общего вида: Можно ли обойти все данные комнаты, пройдя через каждую дверь ровно один раз и выйти на улицу через комнату 1 или 10? С какой комнаты надо начинать? (Приложение 6)

Решение: Пусть комнаты – вершины графа, а двери – ребра.  Проверим степени вершин: Только две вершины имеют нечетную степень. Начать движение можно из комнаты 10, а закончить в комнате 8, либо наоборот. Но, чтобы выйти на улицу (из комнаты 10), надо начинать из комнаты 8.  В этом случае пройдём все двери один раз и попадём в комнату 10, но окажемся внутри комнаты, а не снаружи. Аналогично рассуждая, можно решать любые задачи с лабиринтами, входами и выходами, подземельями и т.п.

Логические задачи

Задача №1

Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано? (Приложение 7)

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

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

Задача №2

В деревне 10 домов, и из каждого выходит по 7 тропинок, идущих к другим домам. Сколько всего тропинок приходит между домами?

    Решение: Пусть дома- вершины графа, тропинки- рёбра. По условию из каждого дома (вершины) выходит 7 тропинок (рёбер), тогда степень каждой вершины 7, сумма степеней вершин 7×10=70, а число рёбер 70 : 2= 35. Таким образом,  между домами проходит 35 тропинок.

 Задача №3

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

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

Задача №4

В небольшом городке живут пять друзей: Иванов, Петренко, Сидорчук, Гришин и Капустин. Их профессии: один из них маляр, другой- мельник, третий- плотник, четвертый-почтальон, а пятый- парикмахер. Петренко и Гришин никогда не держали в руках малярной кисти. Иванов и Гришин собираются посетить мельницу, на которой работает их товарищ. Петренко и Капустин живут в одном доме с почтальоном. Сидорчук был недавно в ЗАГСе одним из свидетелей, когда Петренко и дочь парикмахера сочетались  законным браком. Иванов и Петренко каждое воскресенье играют в городки с плотником и маляром. Гришин и Капустин по субботам встречаются  в парикмахерской, где работает их друг. Почтальон предпочитает бриться сам. Кто есть кто? Решение задачи см. в Приложении 7.

 

II. ПРАКТИЧЕСКАЯ ЧАСТЬ

2.1  Применение графов в различных сферах деятельности

Чем больше я изучал теорию графов, тем больше поражалась разнообразию применения этой теории.

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

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

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

Инженер чертит схемы электрических цепей.

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

Историк прослеживает родословные связи по генеалогическому дереву.

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

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

  Графы применяются в различных отраслях науки. В последние десятилетия теория графов находит все новые области применения (физика, химия, генетика, психология, социология, экономика, лингвистика, электроника, теория планирования и управления). Именно запросы практики способствуют интенсивному развитию теории графов.

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

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

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

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

2.2  Моделирование графа с учетом ветвей дорог города Барабинск

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

 

моего графа стали школы: СОШ №1; СОШ №2; СОШ №3;СОШ №92; СОШ №93; Школа-интернат № 18 ОАО РЖД; СОШ №47. Ребрами послужили дороги улиц города. (Приложение 11)

На карте я отметила школы точками красным цветом, а по зеленым цветом провела примерный путь движения по улицам города между школами. Затем я применила общий метод решения задачи по Эйлеру для определения существования маршрута движения учащихся между школами города Барабинск, не проходя по одной и той же дороге дважды. (Приложение 12)

Я преобразовала рисунок в граф и определила степень каждой вершины.  У меня оказалось нечетных вершин. Приходим к выводу, что из 7 вершин графа две имеют нечетную степень, а остальные четную. Таким образом, можно сказать, что существует маршрут движения учащихся между школами города Барабинск, не проходя по одной и той же дороге дважды. Его нужно начать с одной из нечётных вершин, то есть либо из школы №3, либо из школы №47. (Приложение 13)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

 

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

1. Альхова З.Н., Макеева А.В. Внеклассная работа по математике. – Саратов: «Лицей», 2002 г.

2. Перельман Я.И. Одним росчерком. – Ленинград, 1940г.

3. Башмаков М. И. Математика в кармане «Кенгуру». -  М.: Дрофа, 2010г.

4. Игнатьев Е. И. Математическая смекалка. -  М.: «Омега», 1994г.

5. Подготовка школьников к олимпиадам по математике. 5-6 классы./сост. Григорьева Г.И. – М. : «Глобус», 2009 г.

6. Т. Варга Математика 2. Плоскость и пространство. Деревья и графы. Комбинаторика и вероятность: (Математические игры и опыты). Пер. с нем. – М.: Педагогика, 1978.– 112 с. с ил.

7.  Л. Ю. Березина Графы и их применение: Пособие для учителей. – М.: Просвещение, 1979. – 143 с. с ил.

8. Н.Я. Виленкин, В.И.Жохов идр.,Учебник « Математика-6»,- М.: Мнемозина, 2015г., с.210-211.

9. Интернет ресурсы:  https://ru.wikipedia.org/wiki/%

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЯ

Приложение 1

Задача о вычерчивании конверта

Приложение 2

Задача о маршруте почтальона

 

       Приложение 3

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

 

 

Приложение 4

Виды графов

 

 

 

нулевой граф                 неполный граф                полный граф

 

           

         направленный граф                 эйлеров граф (уникурсальный)

                              

                      связный граф                       несвязный граф

Приложение 5

Решение задач о вычерчивании фигур одним росчерком

   

                   Задача №1                        Задача №2                 Задача №3

 

Приложение 6

Задача о лабиринте

 

 

 

 

Приложение 7

Логические задачи

                        

 

 

 

 

 

 

 

 

         Задача №1                                          Задача №2

  

        Задача №3                                               Задача №4

Приложение 8

Генеалогическое дерево А.С. Пушкина

 

Приложение 9

Графы и химия

 

 

 

 

 

   Приложение 10

Графы и физика

 

 

 

 

 

 

Приложение 11

Карта города Барабинск

Приложение 12

Нахождение вершин графа и возможных ребер

Приложение 13

Модель графа с использованием карты города Барабинск

  

 

Скачано с www.znanio.ru