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

Наш баннер

Мы будем благодарны, если Вы установите наш баннер!
Баннер сайта Обучонок
Код баннера:
<a href="https://obuchonok.ru/" target="_blank"> <img src="https://obuchonok.ru/banners/banob2.gif" width="88" height="31" alt="Обучонок. Исследовательские работы и проекты учащихся"></a>
Все баннера...

Тематика: 
Математика
Автор работы: 
Васильева  Елизавета  Денисовна
Руководитель проекта: 
Казина  Марина  Леонидовна
Учреждение: 
МАОУ Селятинская СОШ  №2
Класс: 
10

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

Подробнее о работе:


В рамках проведенного проекта по математике "Задачи о мостах. Понятие Эйлерова и Гамильтоновых графах" учащейся 10 класса школы был рассмотрен вклад Леонарда Эйлера в науку и проанализирована задача о Кёнигсбергских мостах, изучены способы ее решения. Также во время проведения своего исследования ученица ознакомилась с теоретическими понятиями об Эйлеровом цикле.

В рамках самостоятельной работы ученица 10 класса создала исследовательский проект на тему "Задачи о мостах. Понятие Эйлерова и Гамильтоновых графах", в котором представлены варианты решения задач по Леонарду Эйлеру, дано развернутое определение понятия графа, изложена теория графов и перечислены разновидности графов. Автором проекта были исследованы гамильтоновый граф, гамильтоновый цикл и описаны некоторые задачи, решаемые по теории Эйлерова и Гамильтоновых циклов.

Оглавление

Введение
1. Биография Леонардо Эйлера.
1.1. Вклад Леонарда Эйлера в науку.
1.2. Задача о Кёнигсбергских мостах
2. Теоретические понятия об Эйлерове цикле.
2.1. Решение задач по Леонарду Эйлеру.
2.2. Понятие графа. Теория графов. Разновидности графов
3. Гамильтоновый граф.
3.1. Гамильтоновый цикл.
3.2. Некоторые задачи,решаемые по теории Эйлерова и Гамильтоновых Циклов.
Заключение
Список используемой литературы

Введение


Всем известно, что слово «граф» означает дворянский титул, например Лев Николаевич Толстой. А вот в математике графом называют набор точек, некоторые из которых соединены линиями. Точки именуются вершинами графа, а отрезки рёбрами. Основы теории графов как математической науки заложил в 1736 году Леонард Эйлер, рассматривая задачу о Кёнигсбергских мостах. Данная тема является углублением и развитием в сфере геометрии.

Применение теории графов даёт возможность повысить уровень знаний в химии, компьютерной химии, хемоинформатике, программировании, экономике, логистике, схемотехнике, плате (печатной) или микросхеме.

Целью работы является изучение Эйлеровых и Гамильтоновых циклов и научиться применять их на практике.

Для реализации указанной цели были поставлены следующие задачи:

  1. Изучить историю возникновения теории графов, терминологию теории
  2. графов, изображение графов на плоскости;
  3. Проанализировать некоторые задачи теории графов;
  4. Применять теорию графов.

Объектом исследования является выявление на практике Эйлеровых и Гамильтоновых циклов.

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

Биография Леонардо Эйлера

Леонард Эйлер родился 4 апреля 1707 года в селении Рихен вблизи города Базеля, Швейцария. Начальное образование получил дома под руководством отца, затем продолжил обучение в гимназии Базеля. В 1723 г. Эйлер получил степень магистра искусств, а в 1727 г. защитил диссертацию о распространении звука. В 1727 г. Эйлер приехал в Петербург, где был назначен адъюнктом математики. В 1730 г. Эйлер получил место профессора кафедры физики, а в 1733 г.- кафедры математики. В 1741 г. Л. Эйлер переехал в Берлин, но поддерживал связь с Петербургской академией наук.

Эйлер высоко ценил русских ученых Семёна Кирилловича Котельникова – автора русского учебника механики, и М. В. Ломоносова. В 1766 г. Эйлер со своей семьёй возвращается в Петербург и приступает к активной деятельности в Академии наук. В этот период он справедливо считался первым математиком в мире и пользовался всеобщим уважением и почетом.

Умер Л. Эйлер 18 сентября 1783 г. в Петербурге.

Вклад Леонарда Эйлера в науку


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

Также Леонард Эйлер является основоположником теории специальных функций. В теории корабля Эйлер внёс вклад в теорию устойчивости. В алгебре Эйлеру принадлежит ряд работ. Он является основоположником теории специальных функций. Эйлер является создателем вариационного исчисления. Леонард Эйлер также проводил исследования по теории непрерывных дробей и других бесконечных процессов. Леонард Эйлер заложил основы нескольких математических дисциплин.

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

Семь мостов Кёнигсберга, или Задача о семи кёнигсбергских мостах — старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга , не проходя ни по одному из них дважды. Впервые была решена в 1736 году математиком Леонардом Эйлером доказавшим, что это невозможно, и изобретшим таким образом эйлеровы циклы.

графы 1

графы 2

Теоретические понятия об Эйлерове цикле

Эйлеров путь в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.

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

Эйлеров граф — граф, содержащий эйлеров цикл.

графы 3

Решение задач по Леонарду Эйлеру


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

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

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

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

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

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

Понятие графа. Теория графов. Разновидности графов

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Термин «граф» впервые ввел Сильвестр, Джеймс Джозеф в 1878 году.

графы 4

графы 5

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

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

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

В зависимости от задачи, одни изображения могут давать более наглядную картину, чем другие.

Разновидность графов

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

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

графы 6

Гамильтоновый цикл


Гамильтонов граф — в теории графов это граф, содер-жащий гамильтонову цепь или гамильтонов цикл.

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

графы 7

Некоторые задачи, решаемые по теории Эйлерова и Гамильтоновых циклов

Проблема семи мостов Кёнигсберга — один из первых результатов в теории графов, опубликован Эйлером в 1736.

Проблема четырёх красок — была сформулирована в 1852 году, но неклассическое доказательство получено лишь в 1976 году (достаточно 4-х красок для карты на сфере (плоскости).

Задача коммивояжёра — одна из наиболее известных NP-полных задач.

Задача о клике — ещё одна NP-полная задача.

Нахождение минимального стягивающего (остовного) дерева.

Изоморфизм графов — можно ли путём перенумерации вершин одного графа получить другой.

Планарность графа — можно ли изобразить граф на плоскости без пересечений рёбер (или с минимальным числом слоёв, что находит применение при трассировке межсоединений элементов печатных плат или микросхем).

графы 8

Заключение

Целью моей исследовательской работы было описание методов нахождения и построения эйлеровых и всех гамильтоновых циклов в графах, а также сравнительный анализ этих методов.

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

Почему я взяла именно эту тему?

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

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

Примеры решения задач.

В стране 30 озёр, соединённых между собой 40 каналами так, что от каждого озера можно доплыть до любого другого. Сколько в этой стране островов?

В выпуклом многоугольнике провели несколько диагоналей; никакие три из них не пересекаются в одной точке. Получился граф, вершинами которого служат вершины данного многоугольника и внутренние точки пересечения диагоналей, а рёбрами — стороны многоугольника и соответствующие отрезки диагоналей. а) Назовём вершины полученного графа внутренними, если они отличны от вершин многоугольника; аналогично, назовём рёбра внутренними, если они отличны от сторон многоугольника. Докажите, что число внутренних рёбер равно сумме числа проведённых диагоналей и удвоенного числа внутренних вершин. б) Найдите число рёбер этого графа, если n-угольник оказался разбит на a треугольников и b четырёхугольников. б) 1 2 ) n +b + 4 a (3 2

Список, используемой литературы

  1. Энциклопедия для детей Марии Аксёновой,Георгия Храмова
  2. Книга Л.Н. Ерганжиевой
  3. Книга И . Ф. Шарыгиной: «Наглядная геометрия»
  4. Книга О.С. Шейниной, Г.М. Соловьёвой


Если страница Вам понравилась, поделитесь в социальных сетях:

Партнеры и статистика