Применение теории графов

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

ГРАФЫ И ХИМИЯ
За последние десятилетия в теоретиче­ской химии широкое распространение получи­ли представления топологии и теории графов. Они полезны при поиске количественных соот­ношений «структура - свойство» и «структура-активность», а также в решении теоретико-графовых и комбинаторно-алгебраических за­дач, возникающих в ходе сбора, хранения и об­работки информации по структуре и свойствам веществ.
Графы служат, прежде всего, средством изображения молекул. При топологическом описании молекулы её изображают в виде мо­лекулярного графа, где вершины соответ­ствуют атомам, а рёбра - химическим связям (теоретико-графовая модель молекулы). Обыч­но в таком представлении рассматривают толь­ко скелетные атомы, например, углеводороды со «стёртыми» атомами водорода.

ГРАФЫ И БИОЛОГИЯ
Элементы теории графов используются и в экологии. Природные сообщества обладают сложным строением: несколькими уровнями, между которыми существуют разнообразные трофические (пищевые) и топические (не связные с цепью питания) связи. Структура трофической пирамиды может быть весьма различной, в зависимости от климата, почвы, ландшафта и других факторов.
При анализе биологических сообществ, принято строить пищевые или трофические сети, т.е. графы, вершины которых соответствуют видам, входящим в сообщество, а ребра указывают трофические связи между видами. Обычно такие графы – ориентированные: направление дуги между двумя вершинами указывает на тот из видов, который является потребителем другого, т.е. направление дуги совпадает с направлением потока вещества или биомассы в системе. Например трофическая сеть широколиственного леса.

ГРАФЫ И ИНФОРМАЦИЯ
Двоичные деревья играют весьма важную роль в теории информации. Предположим, что определенное число сообщений требуется закодировать в виде конечных последовательностей различной длины, состоящих из нулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана.
Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо "да", либо "нет". Утвердительному и отрицательному ответу соответствуют два ребра, выходящие из вершины. "Опрос" завершается, когда удается установить то, что требовалось.
Таким образом, если кому-то понадобится взять интервью у различных людей, и ответ на очередной вопрос будет зависеть от заранее неизвестного ответа на предыдущий вопрос, то план такого интервью можно представить в виде двоичного дерева.

ГРАФЫ И ФИЗИКА
Еще недавно одной из наиболее сложных и утомительных задач для радиолюбителей было конструирование печатных схем.
Печатной схемой называют пластинку из какого-либо диэлектрика (изолирующего материала), на которой в виде металлических полосок вытравлены дорожки. Пересекаться дорожки могут только в определенных точках, куда устанавливаются необходимые элементы (диоды, триоды, резисторы и другие), их пересечение в других местах вызовет замыкание электрической цепи.
В ходе решения этой задачи необходимо вычертить плоский граф, с вершинами в указанных точках.

ГРАФЫ И ТРАНСПОРТ
Теория графов находит широкое применение в транспортных и коммуникационных системах. Приведём пример, связанный с компанией Uber. Одна из важнейших её задач - это способность эффективно сочетать водителей с пользователями. Проблема начинается с местоположения.
Серверная часть должна обрабатывать миллионы пользовательских запросов, отправляя каждый из запросов одному или нескольким водителям поблизости. Хоть проще и иногда даже рациональнее отправлять запрос пользователя всем водителями, находящимся поблизости, всё же потребуется предварительная обработка.

ГРАФЫ И ТРАНСПОРТ
Кроме обработки входящих запросов и нахождения области местоположения на основе координат пользователя, а затем нахождения водителей с ближайшими координатами, нам также нужно найти правильного водителя для поездки. Чтобы избежать обработки геопространственных запросов (получение близлежащих автомобилей путем сравнения их текущих координат с координатами пользователя), предположим, у нас уже есть сегмент карты с пользователем и несколькими автомобилями поблизости.
Возможные пути от автомобиля к пользователю обозначены желтым. Задача заключается в том, чтобы рассчитать минимальное расстояние между автомобилем и пользователем, другими словами, найти кратчайший путь между ними.

ГРАФЫ И ТРАНСПОРТ
Представим этот сегмент в виде графа.
Это неориентированный взвешенный граф. Чтобы найти кратчайший маршрут между вершинами B (автомобиль) и А (пользователь), мы должны найти маршрут между ними, состоящий из ребер с возможно минимальными значениями.

ГРАФЫ И ТРАНСПОРТ
Алгоритм действий
Отметим все вершины непосёщенными.
Присвоим каждой вершине значение расстояния до неё. Первой вершине присвоим ноль.
Для текущей вершины рассмотрим непосещённые соседние вершины и вычислим расстояния до каждой с учётом текущей вершины. Сравним новое вычисленное расстояние с текущим назначенным значением и выберем меньшее.
Когда мы закончим рассматривать всех соседей текущей вершины, отметим текущую вершину как посещенную и удалим её из непосещённых вершин.
Если вершина назначения была отмечена как посещённая, остановимся. Алгоритм завершен.
В противном случае выберем непосещённую вершину, отмеченную наименьшим предварительным расстоянием, установим её в качестве новой текущей вершины и вернёмся к шагу 3.