XII Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Задачи о мостах. Понятие Эйлерова и Гамильтоновых графах.
Автор работы награжден дипломом победителя III степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
Всем известно, что слово «граф» означает дворянский титул, например Лев Николаевич Толстой. А вот в математике графом называют набор точек, некоторые из которых соединены линиями. Точки именуются вершинами графа, а отрезки рёбрами. Основы теории графов как математической науки заложил в 1736 году Леонард Эйлер, рассматривая задачу о Кёнигсбергских мостах. Данная тема является углублением и развитием в сфере геометрии.
Применение теории графов даёт возможность повысить уровень знаний в химии, компьютерной химии, хемоинформатике, программировании , экономике, логистике, схемотехнике, плате (печатной) или микросхеме.
Целью работы является изучение Эйлеровых и Гамильтоновых циклов и научиться применять их на практике.
Для реализации указанной цели были поставлены следующие задачи:
Изучить историю возникновения теории графов, терминологию теории графов, изображение графов на плоскости;
Проанализировать некоторые задачи теории графов;
3.Применять теорию графов.
Объектом исследования является выявление на практике Эйлеровых и Гамильтоновых циклов.
Предметом исследования выступает возможность открыть ряд математических проблем, нерешенных на сегодняшний день, с помощью Эйлеровых и Гамильтоновых циклов.
Биография Леонардо Эйлера.
Леонард Эйлер родился 4 апреля 1707 года в селении Рихен вблизи города Базеля, Швейцария. Начальное образование получил дома под руководством отца, затем продолжил обучение в гимназии Базеля. В 1723 г. Эйлер получил степень магистра искусств, а в 1727 г. защитил диссертацию о распространении звука. В 1727 г. Эйлер приехал в Петербург , где был назначен адъюнктом математики. В 1730 г. Эйлер получил место профессора кафедры физики, а в 1733 г.- кафедры математики. В 1741 г. Л. Эйлер переехал в Берлин, но поддерживал связь с Петербургской академией наук.
Эйлер высоко ценил русских ученых Семёна Кирилловича Котельникова – автора русского учебника механики, и М. В. Ломоносова. В 1766 г. Эйлер со своей семьёй возвращается в Петербург и приступает к активной деятельности в Академии наук . В этот период он справедливо считался первым математиком в мире и пользовался всеобщим уважением и почетом.
Умер Л. Эйлер 18 сентября 1783 г. в Петербурге.
1.1Вклад Леонарда Эйлера в науку.
Необыкновенно широк был круг знаний Леонарда Эйлера, охватывающий все разделы современной математики и механики. Леонард был первым , кто пояснил динамику точки при помощи математического анализа. Эйлер открыл пути решения многим дальнейшим исследованиям. Он значительно продвинул теорию Луны. Огромный цикл работ был посвящён математической физике. Эйлер является создателем вариационного исчисления, заложил основы теории уравнений с частными производными.
Также Леонард Эйлер является основоположником теории специальных функций. В теории корабля Эйлер внёс вклад в теорию устойчивости.
В алгебре Эйлеру принадлежит ряд работ. Он является основоположником теории специальных функций. Эйлер является создателем вариационного исчисления. Леонард Эйлер также проводил исследования по теории непрерывных дробей и других бесконечных процессов.
Леонард Эйлер заложил основы нескольких математических дисциплин.
… Творчество Эйлера изумительно и в науке беспримерно…
А. Н. Крылов.
1.2. Задача о Кёнигсбергских мостах.
Семь мостов Кёнигсберга, или Задача о семи кёнигсбергских мостах — старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга , не проходя ни по одному из них дважды. Впервые была решена в 1736 году математиком Леонардом Эйлером доказавшим, что это невозможно, и изобретшим таким образом эйлеровы циклы.
Глава II
Теоретические понятия об Эйлерове цикле.
Эйлеров путь в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.
Эйлеров цикл — эйлеров путь, являющийся циклом, то есть замкнутый путь, проходящий через каждое ребро графа ровно по одному разу.
Эйлеров граф — граф, содержащий эйлеров цикл.
2.1 Решение задач по Леонарду Эйлеру.
На упрощённой схеме города мостам соответствуют линии (ребра графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:
Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
Если все вершины графа чётные, то можно начертить этот граф без отрыва карандаша от бумаги, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
Если ровно две вершины графа нечётные, то можно начертить этот граф без отрыва карандаша от бумаги, при этом нужно начинать с одной из нечётных вершин и завершить его в другой нечётной вершине.
Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
Граф кёнигсбергских мостов имел четыре нечётные вершины (то есть все) — следовательно, невозможно пройти по всем мостам, не проходя ни по одному
Понятие графа. Теория графов. Разновидности графов.
Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Термин «граф» впервые ввел Сильвестр, Джеймс Джозеф в 1878 году.
При изображении графов на рисунках чаще всего используется следующая система обозначений: вершины графа изображаются точками или, при конкретизации смысла вершины, прямоугольниками, овалами и др., где внутри фигуры раскрывается смысл вершины (. Если между вершинами существует ребро, то соответствующие точки (фигуры) соединяются линией или дугой. В случае ориентированного графа дуги заменяют стрелками, они явно указывают направленность ребра. Иногда рядом с ребром размещают поясняющие надписи, раскрывающие смысл ребра, например, в графах переходов конечных автоматов. Различают планарные и не планарные графы. Планарный граф— это граф, который можно изобразить на рисунке (плоскости) без пересечения рёбер (простейшие — треугольник или пара связанных вершин), иначе граф не планарный. В том случае, если граф не содержит циклов (содержащих, по крайней мере, один путь однократного обхода рёбер и вершин с возвратом в исходную вершину), его принято называть «деревом». Важные виды деревьев в теории графов — бинарные деревья, где каждая вершина имеет одно входящее ребро и ровно два выходящих, или является конечной — не имеющей выходящих рёбер и содержит одну корневую вершину, в которую нет входящего ребра.
В зависимости от задачи, одни изображения могут давать более наглядную картину, чем другие.
Разновидность графов.
Изоморфные и плоские(найти замкнутый путь, проходящий по рёбрам и позволяющий побывать в каждой его вершине по одному разу;
Графы игр(шахматы)
Направленные графы
Орграфы(графы, в которых все рёбра имеют направления)
Глава III. Гамильтоновый цикл.
Название «гамильтонов цикл» произошло от задачи «Кругосветное путешествие» предложенной ирландским математиком Вильямом Гамильтоном в 1859 году. Нужно было, выйдя из исходной вершины графа, обойти все его вершины и вернуться в исходную точку.
3.1 Гамильтоновый цикл.
Гамильтонов граф — в теории графов это граф, содер-жащий гамильтонову цепь или гамильтонов цикл.
Гамильтонов путь (или гамильтонова цепь) — путь, содержащий каждую вершину графа ровно один раз.Гамильтонов путьначальная и конечная вершины которого совпадают, называется гамильтоновым циклом. Гамильтонов цикл является простым остовным циклом.
3.2 Некоторые задачи, решаемые по теории Эйлерова и Гамильтоновых циклов.
Проблема семи мостов Кёнигсберга — один из первых результатов в теории графов, опубликован Эйлером в 1736.
Проблема четырёх красок— была сформулирована в 1852 году, но неклассическое доказательство получено лишь в 1976 году (достаточно 4-х красок для карты на сфере (плоскости).
Задача коммивояжёра— одна из наиболее известных NP-полных задач.
Задача о клике— ещё одна NP-полная задача.
Нахождение минимального стягивающего (остовного) дерева.
Изоморфизм графов — можно ли путём перенумерации вершин одного графа получить другой.
Планарность графа — можно ли изобразить граф на плоскости без пересечений рёбер (или с минимальным числом слоёв, что находит применение при трассировке межсоединений элементов печатных плат или микросхем).
Заключение.
Целью моей исследовательской работы было описание методов нахождения и построения эйлеровых и всех гамильтоновых циклов в графах, а также сравнительный анализ этих методов.
Другая цель решаемая в данной работе — это рассмотрение задач по данной теме.
Выявлены закономерности существования Эйлеровых и Гамильтоновых циклов.
Приведены примеры задач , с использованием теории циклов.
Сформулированы критерии существования циклов.
Список, используемой литературы.
Энциклопедия для детей Марии Аксёновой,Георгия Храмова;
Книга Л.Н. Ерганжиевой;
Книга И . Ф. Шарыгиной: «Наглядная геометрия»;
Книга О.С. Шейниной, Г.М. Соловьёвой;
Интернет-ресурс: www. Math.ru