ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ

При решении задач, теория графов стала в данный момент простым, общедоступным и сильным средством решения вопросов, которые в свою очередь затрагивают множество проблем. [1, 2] Графы очень мощный инструмент. Графы можно использовать в постройке схем дорог и электрических цепей, в географических картах и визуализации молекул химических соединений, зависимость между людьми и группами людей [3, 4]. За последние 40 лет теория графов превратилась в 1 из важнейших и развивающихся разделов математики [4]. Это сказывается запросами быстро расширяющейся области компьютерных приложений. Теория графов пользуется успехом при создании интегральных схем и при исследовании машин (в том числе и ЭВМ), логических цепочек, программ, а также в таких отраслях как экономика и статистика, химия и биология, и теория расписаний. В соответствии с этим актуальность темы обусловлена с одной стороны популярностью графов и связанных с ними методики исследований, а с другой, не разработанная, цельная система ее реализации.

Решение многих задач требует долгих и сложных вычислений, а часто и полученные вычисления не приносят пользу. В этом и состоит проблема исследования. Возникает вопрос: нельзя ли для их решения найти простое, разумное решение. Упрощается ли решение задач, в том случае, если применять графы?

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

Задача коммивояжёра относится к задачам, решаемым с помощью графов. Задача коммивояжера является 1 из интересных задач теории комбинаторики. Она была поставлена в 1934 году, и ее пытались решить множество математиков того времени. Коммивояжер (бродячий торговец) должен пойти из 1-ое города, посетить по разу в неизвестном порядке города 2,1,3...n и возвратиться в 1 город. Расстояния между населенными пунктами известны. В каком порядке нужно ходить в города, чтобы путь (тур) коммивояжера был наикратчайшим? [1].

Методика ее решения является жадный алгоритм "иди в ближний (в который еще не входил) город".

"Жадным" данный алгоритм назван потому, что на последних шагах приходится беспощадно расплачиваться за жадность.

Пускай коммивояжер стартует из города 1. Алгоритм "иди в ближний город" выведет его в город 2, затем 3, затем 4; на последнем шаге придется отплатить за жадность, идя обратно по долгой диагонали ромба. Как результат этого, получится не кратчайший, а долгий путь. [2]

Еще один из ярких примеров задач, решаемых с помощью графов – это задача о Кенигсбергских мостах. Город Кенигсберг расположен на берегах реки Прегель и 2 островах. Разные части города были соединены 7 мостами. По воскресеньям мещане совершали прогулки по городу. Вопрос: возможно ли совершить прогулку таким образом, чтобы, выйдя из дома, вернуться, пройдя точь-в-точь 1 раз по любому мосту. [4].

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

Задача о минимальном остовном дереве относятся к ряду задач, которые в реальной жизни имеют вполне полезное и разумное применение. Задача заключается в следующем: Существует множество вершин, и существуют ребра между определенными вершинами, а также дана величина данных ребер. Необходимо найти минимально короткий путь из одной вершины в другую. Задания похожего типа используются в ЕГЭ по информатике. Не стоит забывать и о начальнике транспортной компании, который распределяет как нужно отвести грузы компании как можно более экономичней.

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

Как я говорил ранее, теория графов широко применяется в ЭВМ, и в теории создания ИИ. Допустим нам необходимо решить квадратное уравнение, и допустим, что ИИ будет решать это уравнение через дискриминант, спустя некоторое время действия ИИ для решения уравнения будет сводиться к формуле Виета.

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

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

Графы используются для расположения на печатных платах электронных элементов.

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

Также возможно в будущем теории графов будет активно применяется в медицине, где только по симптомам тот же ИИ будет определять диагноз и выписывать лечение.

Не стоит забывать о транспортных сетях, уже придуманы системы такси, которые работают намного быстрее из-за алгоритмов прокладывания маршрута.

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

А также многочисленные сайты знакомств, используют 2-3 параметра для нахождения друга или партнера.

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

В дискретных устройствах присутствует топология, основанная на графах. Это позволяет уменьшить количество вычислений и находить лучшие и самые приемлемые решения.

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

Список литературы:

1. lib-5.ru/urok3/urok-269782.php
2. for-teacher.ru/edu/matematika/doc-eshinnu.html
3. infourok.ru/prakticheskoe_primenenie_teorii_grafov-367166.htm
4. school-science.ru/7/7/39366