Эйлеровы графы

СОДЕРЖАНИЕ

Аннотация..........................................................................................................2

Введение.............................................................................................................4

Глава 1. Основные понятия теории графов……………………………. 6

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

Понятие графа..…………………………………………………………9

Эйлеровы графы ……………………………………………………...11

Глава 2. Практическое применение знаний о теории графов при решении задач………………………………………………………………..……13

Задача о 4 красках …….……….…………………………………….13

Задача китайского почтальона ………………………………………15

Задача о 7 мостах Кёнигсберга ……………………………………...17

Типовые задачи по теории графов…………………………………...20

Заключение.......................................................................................................26

Список использованных источников ............................................................28

ВВЕДЕНИЕ

В последнее время графы и связанные с ними методы исследований органически пронизывают на разных уровнях едва ли не всю современную математику. Теория графов рассматривается как одна из ветвей топологии: непосредственное отношение она имеет также к алгебре и к теории чисел. Графы эффективно используются в теории планирования и управления, теории расписаний, социологии, математической лингвистике, экономике, биологии, медицине, географии. Широкое применение находят графы в таких областях, как программирование, теория конечных автоматов, электроника, в решении вероятностных и комбинаторных задач, нахождении максимального потока в сети, кратчайшего расстояния, максимального паросочетания, проверки планарности графа и др. Как особый класс можно выделить задачи оптимизации на графах. Математические развлечения и головоломки тоже являются частью теории графов, например, знаменитая проблема четырех красок, интригующая математиков по сей день. Теория графов быстро развивается, находит все новые приложения и ждет молодых исследователей.В настоящее время существует множество проблем, где требуется построить некоторые сложные системы с помощью определенного упорядочения их элементов. Сюда относятся календарное планирование промышленного производства, задачи теории сетевого планирования и управления, тактические и логические задачи, проблемы построения систем связи и исследования процессов передачи информации, выбор оптимальных маршрутов и потоков в сетях, методы построения электрических сетей, задачи идентификации в органической химии и способы переключения переключательных систем. Таким же является большой круг экономических задач, проблемы выбора структуры социальных групп и т.п. Таким образом, область возможных применений теории графов очень широка. Комбинаторные методы нахождения нужного упорядочения объектов существенно отличаются от классических методов анализа поведения систем с помощью уравнений. Кроме языка теории графов, задачи упорядочения объектов можно формулировать в терминах теории матриц с элементами ноль-один.Все вышеизложенное объясняет актуальность и значимость избранной темы курсовой работы.Цель курсовой работы: изучение графов, эйлеровых графов. Объектом исследования данной работы являются эйлеровы графы.Предметом исследования является теоретические материалы, посвященные теории графов. В ходе исследования нами были поставлены следующие задачи: Изучить теоретический материал, касающийся теории графов.Рассмотреть виды графов, их свойства. Раскрыть понятие эйлеровых графов.Ознакомиться с решением типовых задач по теории графов. Теоретическая основа работы представляет собой учебная литература и научные статьи, посвященные рассматриваемой теме.Общеметодологическую основу исследования составляет метод анализа, систематизации, а также метод дедукции.Выпускная квалификационная работа состоит из введения, двух глав, заключения, списка использованной литературы, приложения. Во введении приводится обоснование актуальности проблемы исследования, характеризуются его исходные параметры. В первой главе описываются теоретические основы теории графов. Во второй главе приводятся решения типовых задач по теории графов. В заключении представлены исчерпывающие выводы по результатам исследования.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Мациевский С.В. К истории теории графов. Зарождение / С.В. Мациевский, Г.В. Квитко // Вестник Балтийского федерального университета им. И. Канта. Серия: Физико-математические и технические науки. – 2021. – № 4. – С. 23-33.

Суртаева Ю.Н. История возникновения теории графов / Ю.Н. Суртаева // Информация и образование: границы коммуникаций. – 2011. – № 3 (11). – С. 304-305.

Омельченко А. В. Теория графов / А.В. Омельченко. – М.: МЦНМО, 2018. – 416 с.

Акимов О.Е. Дискретная математика: логика, группы, графы / О.Е. Акимов. – М.: Лаборатория Базовых Знаний, 2021. – 352 с.

Мотькина Н.Н. Методика преподавания элементов теории графов на факультативных занятиях по математике / Н.Н. Мотькина. – Белгород: НИУ «БелГУ», 2018. – 57 с.

Костюкова Н.И. Графы и их применение : учебное пособие / Костюкова Н.И. – Москва: Интернет-Университет Информационных Технологий (ИНТУИТ), Ай Пи Ар Медиа, 2024. – 147 c.

Соловьев А. Е. Специальная математика. Конспект лекций / А.Е. Соловьев. – Пермь: Пермский Государственный Технический Университет, 2001. – 110 с.

Ловас Л. Н. Прикладные задачи теории графов / Л. Н. Ловас. – Москва: Мир, 1998. – 658 с.

Школа Пифагора [Электронный ресурс]. – Режим доступа: http://xn----7sbbao2ali0aghq2c8b.xn--p1ai/load/mir_matematiki/teorija_grafov/zadacha_kitajskogo_pochtalona/119-1-0-2600?ysclid=lvhw7qvsak316187888. – 29.04.2024.

Decoder [Электронный ресурс]. – Режим доступа:http://www.decoder.ru/list/all/topic_117. – 29.04.2024.

Научные Статьи.Ру [Электронный ресурс]. – Режим доступа:https://nauchniestati.ru/spravka/zadacha-o-kyonigsbergskih-mostah/?ysclid=lvhxowj1ur466041751. – 29.04.2024.

Пихтилькова О.А.Теория конечных графов: методические указания / О.А. Пихтилькова, Т.М. Отрыванкина, Л.Б. Усова, Д.У. Шакирова; Оренбургский гос. ун-т. – Оренбург: ОГУ, 2018 – 99 с.

Родионов А.В. О решении задач с экономическим содержанием средствами теории графов / А.В. Родионов, Е.А. Ефремова // Сборник статей Международной научно-практической конференции «Наука и современность». Часть 2. – Уфа: РИО МЦИИ «ОМЕГА САЙНС», 2015.