XVIII Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Применение графов в современном мире
Автор работы награжден дипломом победителя II степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
В современном мире активно развиваются новые цифровые технологии: нейросети, блокчейн, поисковые системы, и прочее. Фундаментальный раздел математики – теория графов – находит своё применение всюду. Везде, где бы мы ни были, мы сталкиваемся с теорией графов. Заходя в метро, мы смотрим наилучший маршрут для себя на карте, с помощью навигатора ищем путь до Исаакиевского собора, рассчитываем маршрут, который будет наименее затратен в использовании бензина.
Цель работы: описание современных актуальных областей/задач применения теории графов.
Задачи работы:
Описать появление теории графов.
Дать общую информацию по теории графов: разновидности графов, их описание и примеры.
Рассмотреть задачи на графы.
Так как в работе рассматриваются теория графов я использовала источники, соответствующие этим темам. Один из них: Клауди Альсина «Карты метро и нейронные сети. Теория графов»[2]. В книге рассматривается зарождения теории графов с задачи о кенинсбергских мостах, рассказывается про разновидности графов (геометрические, полные, планарные и так далее). В первой главе в теме плоских графов автор описывает классическую задачу про колодцы и враждующие темы. Большой интерес вызывает третья глава, в которой К. Альсина описывает циклы, задачи оптимизации. Задача коммивояжера – классическая задача оптимизации в программировании. В рамках задачи коммивояжера рассмотрению подлежит глава 45 руководства А.Н. Швеца «Perl. Примеры программ»[2], в котором подробно описывается решение данной задачи разными методами. В частности методом имитации отжига. Возвращаясь к книге К. Альсины, особое внимание стоит уделить блоку «Графы и интернет»[1], где рассказывается про алгоритм PageRank, упорядочивающий результаты поиска.
ГЛАВА 1 Графы
Общие сведения про графы
«В математике, Граф – это абстрактное представление множества объектов и связей между ними»[3]. Графы используются повсюду: в сети «Интернет», в различных науках, в архитектуре и урбанистике. Самый простой пример графов – карта метро Москвы (рис. 1).
(рис. 1)
Теория графов появилась благодаря Леонарду Эйлеру, пытавшемуся решить задачу о калининградских (кёнингсбергских) мостах. «Она формулируется так: в прусском городе Кёнинсберге есть остров под названием Кнайпхоф, окруженный двумя рукавами реки Преголя. Через два рукава реки перекинуто семь мостов. Нужно определить, можно ли обойти мосты, пройдя по каждому ровно один раз»[5]. Схема моста не является Эйлеров циклом, поэтому пройти по каждому из ребер графа только один раз не получится (рис. 2).
(рис. 2)
Эйлеров цикл – путь, содержащий все ребра графа, которые не должны повторяться, а конечная и начальная вершины должны совпадать. Именно поэтому задачу о мостах Кёнинсберга решить невозможно, но именно она в 1726 году положила начало теории графов. Помимо Эйлеровых циклов существуют еще Гамильтоновы циклы, в которых нужно пройти ровно один раз не по ребрам, а по вершинам. Изобретены такие циклы были еще в 1759 году Уильямом Роуаном Гамильтоном. Математик придумал игру: 20 вершин додекаэдра были соответствовали 20 разным городам. «Путешественнику» надо было обойти все населенные пункты ровно один раз, и при этом вернуться в изначальный населенный пункт.
Графы можно различить на обыкновенные, мультиграфы и псевдографы. «В обыкновенном графе две вершины могут соединяться только одним ребром. Если они соединены более чем одним ребром, то такой граф называется мультиграфом. Если вершина мультиграфа может соединяться сама с собой, то такой граф называется псевдографом»[1](рис. 3). Также существуют геометрические, полные, и плоские графы.
(рис. 3)
Геометрические графы состоят из циклов (маршрут через все вершины, где начальная и конечная вершины совпадают). Геометрический граф является плоской фигурой из ребер и вершин (рис. 4).
(рис. 4)
Полные графы графы из n вершин, в котором любые случайно взятые вершины соединены ребром ( ) (рис. 5).
(рис. 5)
Формула числа ребер полного графа ̶ .«Плоским графом называется изображение графа на плоскости без самопересечений»[5].
Для полного плоского графа справедлива теорема Эйлера: «