IV Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
ЕГО СИЯТЕЛЬСТВО ГРАФ
Автор работы награжден дипломом победителя I степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
В данной работе речь идёт не о дворянском титуле, а о математическом понятии.
При решении занимательных задач по математике о фигурах, вычерчиваемых одним росчерком, возникает необходимость знакомства с понятием графа.
Приведём примеры таких задач:
1) Голодная лиса вышла из вырытой под деревом норы и начала бродить по лесу от дерева к дереву. Чёрной линией изображён путь лисы. Наконец она устала и легла отдохнуть под одним из деревьев. Где сейчас лиса, и под каким деревом её нора? Сколько решений имеет задача?
2) Начертите нарисованные фигуры одним росчерком
3
3) Через город Кёнигсберг протекает река, она делится на два рукава и огибает остров. В 18 веке в городе было 7 мостов, расположенных как показано на рисунке. Однажды житель города спросил у знакомого, сможет ли он пройти по всем мостам так, чтобы на каждом побывать один раз и вернуться к месту начала прогулки.
Первым человеком, которому удалось решить подобные задачи, был швейцарский математик Леонард Эйлер1. Ему принадлежит первая работа по теории графов.
Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. Однако дальнейшее развитие математики и особенно её приложений дало сильный толчок развитию теории графов. Уже в XIX столетии графы использовались при построении схем.
В настоящее время эта теория находит многочисленное применение в разнообразных практических вопросах: при установлении разного рода соответствий, при решении транспортных задач, задач о потоках в сети нефтепроводов, в программировании и теории игр, теории передачи сообщений. Теория графов теперь применяется и в таких областях, как экономика, психология и биология.
В этой работе будут подробнее рассмотрены графы, основные сведения и теоремы связанные с этим понятием. А также задачи, которые решаются с помощью графов.
Цель:показать применение теории графов для решения различных видов задач.
Задачи:
Изучить элементы теории графов.
Разобрать решение различных видов задач.
Узнать о применении графов в науке и в различных сферах деятельности.
Методы исследования:
Поиск и анализ информации в литературе.
Поиск и изучение информации в интернет – ресурсах.
Моделирование.
1 Эйлер — один из величайших математиков XVIII столетия, родившийся в 1707 г.,в Базеле. Является основоположник теории
4
Глава 1
§1
Определение графа
Фигура, образованная набором точек на плоскости и отрезков называется плоским графом или просто графом. Точки называются вершинами графа, а отрезки - рёбрами графа.
Вместо отрезков в качестве рёбер также рассматриваются кривые на плоскости.
Примеры графов могут служить схемы метрополитена, железных и шоссейных дорог, планы выставок и.т.д.
Исторически сложилось так, что теория графов зародилась в ходе решения головоломок 200 с лишним лет назад.
Одной из таких головоломок была задача о Кёнигсбергских мостах. Именно она привлекла внимание Леонарда Эйлера.
В г. Кёнигсбёрге было семь мостов через Прегель (рис. 3).
Можно ли, прогуливаясь по городу, пройти через каждый мост ровно по одному разу?
Эта задача связана с другими головоломками, суть которых в том, чтобы обвести контур фигуры одним росчерком. Именно такие контуры и называют уникурсальные графы.
Этой задаче Эйлер посвятил целое исследование, которое в 1736г. Было представлено в Петербургскую академию наук.
На рисунке 3 изображён граф, соответствующий задаче о кёнигсбергских мостах. Требуется доказать, что этот граф является уникурсальным. Для этого рассмотрим понятие индекса вершины - число рёбер графа, сходящихся в данной вершине, и докажем, что если граф уникурсальный, то он содержит не более двух вершин нечётного индекса.
Действительно, если граф уникурсален и его начало не совпадает с концом, то начало и конец являются единственными вершинами нечетного индекса. Остальные вершины имеют четный индекс, так как в каждую точку мы входим и выходим из нее. Если начало совпадает с концом, то вершин с нечетным индексом нет.
Приступим теперь к решению задачи. Определим четность вершин графа на рисунке 3. Вершина А имеет индекс 5, Б — 3, П — ЗиЛ — 3. Таким образом, мы имеем четыре вершины нечетного индекса, и, следовательно, данный граф не является уникурсальным. Отсюда получаем, что нельзя пройти во время прогулки по городу по всем семи мостам, проходя по каждому только один раз.
Решая задачу про Кенигсбергские мосты, Эйлер установил следующие свойства графа:
Если все вершины графа чётные, то можно одним
5
росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф.
Граф с двумя нечётными вершинами тоже можно начертить одним росчерком. Движение нужно начинать от любой нечётной вершины, а заканчивать на другой нечётной вершине.
Граф с более чем двумя нечётными вершинами, невозможно начертить одним росчерком.
Зная свойства графов, полученные Эйлером можно решить задачи, рассматриваемые во введении:
В задаче про лису две нечётные вершины, значит, нора лисы находится в одной из них, а сама лиса - во второй, или наоборот, т.е. задача имеет два решения.
Во второй задаче, подсчитав, сколько линий выходит из каждой вершины, тоже можно сделать вывод о возможности её решения.
В приложении 1 представлены задачи, которые можно решить, зная свойства графов.
§2
Теорема Эйлера
Другой задачей-головоломкой, связанной с графами и с именем Эйлера, была задача о трех домиках и трех колодцах.
Три соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу?
Для решения этой задачи воспользуемся теоремой, доказанной Леонардом Эйлером в 1752 г.
Если многоугольник разбит на конечное число многоугольников, то имеет место равенство
В-Р + Г=1,
где В — общее число вершин, Р — общее число ребер, Г — число многоугольников
Приступим теперь к решению задачи о трех домиках и трех колодцах.
Решение. Предположим, что это можно сделать. Отметим домики точками D1 D2 D3 а колодцы точками K1K2K3.
Каждую точку-домик соединим с каждой точкой-колодцем. Получим девять ребер, которые попарно не пересекаются.
Эти ребра образуют на плоскости многоугольник, разделенный на более мелкие многоугольники. Поэтому для этого разбиения должно выполняться соотношение
6
Эйлера В — Р + Г = 1. Добавим к рассматриваемым граням еще одну— внешнюю часть плоскости по отношению к исходному многоугольнику. Тогда соотношение Эйлера примет вид В — Р + Г -2, причем В = 6 и Р = 9. Следовательно, Г = 5. Каждая из пяти граней имеет, по крайней мере, четыре ребра, поскольку по условию задачи ни одна из дорожек не должна непосредственно соединять два дома или два колодца. Так как каждое ребро принадлежит ровно двум граням, то количество ребер должно быть не меньше 10, что противоречит условию, по которому их число равно 9. Полученное противоречие показывает, что ответ в задаче отрицателен: нельзя провести непересекающиеся дорожки от каждого домика к каждому колодцу
Проблема четырёх красок
Ещё одной проблемой, связанной с многоугольниками и графами, является проблема четырёх красок, имеющая почти 150-ти летнюю историю.
Задача заключается в том, чтобы раскрасить данную карту на плоскости так, чтобы пограничные страны были окрашены в разные цвета (не пограничные страны можно окрашивать одним цветом), использовав при этом наименьшее число красок.
На рисунке 8 изображена карта, для раскраски которой потребовалось три цвета. На рисунке 9 изображена карта, для раскраски которой трех цветов недостаточно и требуется четыре цвета.
В 1850 г. шотландский физик Фредерик Гутри обратил внимание на то, что задачи раскрашивания карт очень популярны среди студентов-математиков в Лондоне,
а сформулировал проблему четырех красок его брат Фрэнсис Гутри, который, раскрасив карту графств Англии четырьмя цветами, выдвинул гипотезу о том, что
этого количества цветов достаточно для раскраски любой карты. Он привлек к проблеме внимание своего преподавателя математики А. Де Моргана, а тот сообщил о ней своему другу В. Гамильтону и тем самым способствовал ее широкому распространению.
Однако годом рождения проблемы четырех красок считается 1878 г. Именно тогда на одном из заседаний Британского географического общества выдающийся
7
английский математик А. Кэли четко сформулировал поставленную задачу: «Доказать, что любую географическую карту на плоскости (или на глобусе) можно правильно закрасить четырьмя красками». Раскраска карты называется правильной, если любые две страны, имеющие на карте общую границу, окрашены в различные цвета. Именно с этого момента проблема привлекла к себе внимание многих крупных математиков.
В 1890 г. английский математик П. Хивуд доказал, что любую карту на плоскости можно раскрасить в пять цветов. Однако долгое время проблема четырех красок не поддавалась решению. В 1968 г. американские математики Оре и Стемпл показали, что любую карту, имеющую не более 40 стран, можно раскрасить в четыре цвета.
В настоящее время для решения этой проблемы преимущественно используют компьютеры, что связано с выполнением огромного количества вычислений. В 1976 г. американскими учеными К. Аппелем и В. Хаке-ном было получено первое машинное решение. С помощью машины они просматривали различные типы карт, и для каждого из них машина решала, может ли в данном типе найтись карта, которая не раскрашивается в четыре цвета. Учеными было просмотрено почти 2000 типов карт, и для всех был получен ответ; «Нет».
В приложении 2 представлены задачи, которые можно решить, зная о проблеме четырёх красок.
§4
Связные графы. Деревья
Решим задачу:
Может ли так случиться, что водной компании из шестичеловек каждый знаком только сдвумя другими?
Решение. Участника этой компании изобразим вершиной графа, а отношение знакомства между двумя участниками - ребром. Изобразим графы, которые могут соответствовать такой компании (рис. 12 и 13).
8
Итак, ситуация, рассмотренная в задаче, вполне возможна. Но случай, рассмотренный на рисунке 13, соответствует не одной, а двум компаниям, участники одной из них не знакомы с участниками другой
Про граф, изображенный на рисунке 12, говорят, что он связный, так как из каждой вершины по ребрам можно попасть в любую другую. Делаем вывод, что в этом случае каждый через своих знакомых может познакомиться со всеми остальными.
На рисунке 14 получились два простых цикла, не сцепленные между собой в вершинах. Такой граф называется несвязным.
Дадим теперь определения связности вершин в графе и связности графа.
Две вершины А и В графа называются связными, если в графе существует путь с концами А и В.
Две вершины графа называются несвязными, если в графе не существует ни одного пути, связывающего их.
Граф называется связным, если каждые две вершины его связные.
Граф называется несвязным, если хотя бы две вершины его несвязные.
Деревом называется всякий связный граф, не имеющий циклов (рис. 15).
Удобно считать что граф, состоящий из одной изолированной вершины, тоже является деревом.
Для каждой пары вершин дерева существует единственный соединяющий их путь.
Вершина дерева, степень которой равна единице, называется висячей вершиной (на рисунке 15 висячие вершины выделены закрашенными кружками).
9
Лесом называется несвязный граф, представляющий объединение деревьев (рис. 16).
В приложении 3 представлены задачи, которые можно решить, зная понятие связных графов и деревьев.
§5
Применение графов
Чем больше я изучал теорию графов, тем больше поражалась разнообразию применения этой теории.
Типичными графами на картах города являются схемы движения городского транспорта, изображения железных дорог, схемы авиалиний, которые часто
вывешивается в аэропортах. Графом является и система улиц города. Его вершины – площади и перекрестки, а ребра – улицы. Графы есть и на картах звездного неба.
С помощью графов часто упрощается решение задач, сформулированных в различных областях знаний: в автоматике, электронике, физике, химии. Помогают графы в решении математических и экономических задач.
10
Теория графов сейчас одна из самых развиваемых частей математики, так как современная жизнь требует появление новых профессий. Одна из них – специалист по логистике. (Приложение 3.) Менеджер по логистике занимается доставкой товаров, грузов, планирует транспортные маршруты, рассчитывает стоимость перевозок, организует хранение товаров, грузов и т.д. Одна из главных задач специалиста по логистике - анализ ситуации, поэтому он должен уметь хорошо считать, владеть теорией графов.
Инженер чертит схемы электрических цепей.
Химик рисует структурные формулы, чтобы показать, как в сложной молекуле с помощью валентных связей соединяются друг с другом атомы.
Историк прослеживает родословные связи по генеалогическому дереву.
Военачальник наносит на карту сеть коммуникаций, по которым из тыла к передовым частям доставляется подкрепление.
Социолог по сложнейшей диаграмме показывает, как подчиняются друг другу различные отделы одной огромной корпораций.
Графы применяются в различных отраслях науки. В последние десятилетия теория графов находит все новые области применения (физика, химия, генетика, психология, социология, экономика, лингвистика, электроника, теория планирования и управления). Именно запросы практики способствуют интенсивному развитию теории графов.
Графы и история.
Использует графы и история. Например, в генеалогическом дереве, вершины – члены рода, а связывающие их отрезки – отношения родственности.
Генеалогическое дерево А.С. Пушкина.
11
Графы и химия.
Теория графов в химии применяется для решения различных теоретических и прикладных задач. Применение графов теории базируется на построении и анализе различных классов химических и химико-технологических графов, которые называются также топология, т.е. модели, учитывающие только характер связи вершин. Ребра и вершины этих графов отображают химические и химико-технологические понятия, явления, процессы или объекты и соответственно качественные и количественные взаимосвязи либо определенные отношения между ними.
При графическом изображении формул веществ указывается последовательность расположения атомов в молекуле с помощью, так называемых валентных штрихов (термин «валентный штрих» предложил в 1858 г. А. Купер для обозначения химических сил сцепления атомов), иначе называемых валентной чертой (каждая валентная черта, или валентный штрих, эквивалентны одной паре электронов в ковалентных соединениях или одному электрону, участвующему в образовании ионной связи).
Химические графы дают возможность прогнозировать химические превращения, пояснять сущность и систематизировать некоторые основные понятия химии.
Молекулярные графы, применяемые в стереохимии и структурной топологии, химии кластеров, полимеров и др., представляют собой неориентированные графы, отображающие строение молекул. Вершины и ребра этих графов отвечают соответственно атомам и химическим связям между ними.
Молекулярные графы и деревья: а, б - мультиграфы этилена и формальдегида; в-молекулы изомеров пентана.
Графы и физика
Еще недавно одной из наиболее сложных и утомительных задач для радиолюбителей было конструирование печатных схем.
Печатной схемой называют пластинку из какого-либо диэлектрика (изолирующего материала), на которой в виде металлических полосок вытравлены дорожки. Пересекаться дорожки могут только в определенных точках, куда
12
устанавливаются необходимые элементы, их пересечение в других местах вызовет замыкание электрической цепи.
В ходе решения этой задачи необходимо вычертить плоский граф, с вершинами в указанных точках.
Изучая этот материал, я узнал области применения теории графов и сделал вывод, что этот раздел математики является одним из важнейших, который используется в нашей повседневной жизни часто незаметно для нас.
Глава 2
Личное исследование
К теме графы я пришёл, начиная, решать головоломки и занимательные задачи. А в процессе написания работы узнал, что некоторые логические игры тоже связанны с данной темой. Например, «крестики – нолики». В дальнейшем я буду вести своё обозначение для каждой из девяти клеток поля (рис. 17). Каждый ход я буду обозначать, используя специальные слова и обозначения, например «крестик поставлен в клетку 1» (кратко «XI»), «нолик поставлен в клетку 3» (кратко «03>) (рис. 18). Для того чтобы представить позицию в игре, удобно рассмотреть «игровое поле» со сделанными ходами, то есть с нанесенными на него крестиками и ноликами.
Однако эти обозначения и описания, которые хорошо представляют отдельные ситуации, отдельные позиции в игре, недостаточно эффективны, когда надо представить ход игры в целом. «Крестики и нолики» относятся к числу простейших детерминированных игр (то есть таких игр, исход в которых определяется в пользу начинающего, если он действует «правильно», в соответствии с точно определенным алгоритмом). Алгоритм этот представляет собой инструкцию как нужно отвечать на ту или иную инициативу соперника. В игре «Крестики и нолики» такой алгоритм описывается деревом.
Если игра начата ходами (Х7) и (04), то дерево, описывающее дальнейшую разумную игру крестиками, приводится на рисунке 19. Здесь вершины соответствуют очередным позициям игры, «сплошные» ребра соответствуют ходам крестиками, а «штриховые» — ноликами.
13
В ходе исследования я рассчитал, что если игра начата с ходов (Х1) и (Об), то «крестики» могут добиться победы независимо от ходов «ноликов». Я представлю алгоритмы нескольких вариантов игр в виде графа-дерева (рис. 20).
Также я рассчитал, что если игра начата ходами (Х2) и (05), то «нолики» добьются ничьей независимо от ходов «крестиков». Я также представил алгоритм нескольких вариантов игры в виде графа-дерева (рис. 21).
14
ничья
Заключение
Моё знакомство с графами произошло в процессе решения занимательных задач и головоломок. Данная работа позволила мне не только научиться решать такие задач, но и понять то, Что графы имеют широчайшее применение во многих науках и в обычной жизни. Например графы помогают при нахождении наилучших вариантов развозки товаров по магазинам, при составлении расписания, при нахождении кратчайшего пути и.т.д.
Графы находят своё применение в таких областях как:
Математика
Программирование
Физика
Химия
Биология
Комбинаторика
Теория вероятности
Экономика
Управление
Геодезия
Социология
Психология
Имея достаточную осведомлённость в какой-либо из этих областей, можно подробно рассмотреть применение в ней графов. В дальнейшем я буду рассматривать этот вопрос в физике.
15
Список литературы
Никольская И. Л. «Факультативный курс по математике» 7-9
Березина Л. Ю. «Графы и их применение»
Мельников О. И. «Занимательные задачи по теории графов»
Смирнова И. М., Смирнов В. А. «Геометрия» 7-9
Гардпер М. «Математические головоломки и развлечения»
Сайт «ru.wikipedia.org»
Сайт «referats.allbest.ru»
16
Приложение 1
1.Определите, какие графы (рис. 5) являются уникурсальными.
2. Возьмите карту Санкт-Петербурга и определите, можно ли, прогуливаясь по городу, обойти все Дворцовые мосты ровно по одному разу.
3.Докажите, что в любом графе сумма индексов всех его вершин — число четное, равное удвоенному числу ребер графа. Выведите из этого, что число вершин с нечетными индексами четно.
4. Сможет ли экскурсовод провести посетителей по выставке так, чтобы они побывали в каждом зале только один раз? Соответствующий граф приведен на рисунке 4. Вершины графа — это вход, выход, двери, соединяющие залы, перекрестки, а ребра — залы и коридоры. Где на выставке следовало бы сделать вход и выход, чтобы можно было провести экскурсию по всем залам, побывав в каждом из них только один раз?
Докажите, что во всяком графе, ребрами которого являются отрезки, найдутся по крайней мере две вершины одинакового индекса.
5.Нарисуйте одним росчерком фигуры, изображенные на рисунке 6
Приложение 2
1. Раскрасьте карту, изображенную на рисунке 10. Какое минимальное число красок для этого потребуется?
2.Докажите, что все возможные карты на плоскости, образованные окружностями, могут быть раскрашены в два цвета. Докажите, что если карту, заполняющую всю плоскость, можно раскрасить в два цвета, то она имеет вершины только четного индекса.
3.Используя то, что любую карту на плоскости можно раскрасить в четыре цвета, решите задачу известного астронома и геометра Августа Мебиуса, сформулированную им в 1840 г.: на плоскости нельзя начертить пять областей так, чтобы каждые две из них имели общую границу.
4.Докажите, что все возможные карты на плоскости, образованные прямыми, могут быть раскрашены в два цвета.
5.Сколько красок достаточно взять, чтобы раскрасить карту, образованную двумя концентрическими окружностями, имеющими п перегородок (рис. 11)?
Приложение 3
1.Нарисуйте граф с пятью вершинами, который не является связным.
2.Дорисуйте граф, изображённый на рисунке 14 так, чтобы он оказался связным.
3.Нарисуйте 5 связных графов.
4.Связный граф, не содержащий ни одной простой замкнутой ломаной, называется деревом. Нарисуйте графы, являющиеся деревьями.
5.Докажите, что в графе, являющемся деревом, любые две вершины можно соединить только одной ломаной.
МУНИЦИПАЛЬНОЕ БЮДЖЕТНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ОДИНЦОВСКАЯ СРЕДНЯЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ
ШКОЛА №1
(143000. Московская область, г.Одинцово, ул.Солнечная, д.14)
тел. 8(495)-593-69-24
КОНКУРСНАЯ РАБОТА
по математике
«ЕГО СИЯТЕЛЬСТВО ГРАФ»
Выполнили:
Чеботарёв Сергей Денисович, 7 класс
Московская область,
г.Одинцово,
ул.Комсомольская, д.3, кв.128
Бугулов Георгий Таймуразович, 7 класс
Московская область,
г.Одинцово,
ул.Союзная, д.2, кв.97
Руководитель
Бутникова Наталья Александровна
Учитель математики
Одинцовской средней общеобразовательной школы №1