Примене́ние тео́рии гра́фов — использование теории графов как математического орудия в различных дисциплинах.
Уже в XIX веке графы применялись при проектировании электрических цепей и молекулярных схем; математические развлечения и головоломки — тоже часть теории графов.
Теория графов, как математическое орудие, приложима как к наукам о поведении (теории информации, кибернетике, теории игр, теории систем, транспортным сетям), так и к чисто абстрактным дисциплинам (теории множеств, теории матриц, теории групп и так далее).
Несмотря на разнообразные, усложнённые, малопонятные и специализированные термины многие модельные (схемные, структурные) и конфигурационные проблемы переформулируются на языке теории графов, что позволяет значительно проще выявить их концептуальные трудности. В разных областях знаний понятие «граф» может встречаться под следующими названиями: структура (гражданское строительство); сеть (электротехника); социограмма (социология и экономика); молекулярная структура (химия); навигационная карта (картография); распределительная сеть (энергетика) и так далее.
Некоторые задачи теории графов К теории графов также относится целый ряд математических проблем, не решённых на сегодняшний день.
Наиболее известные задачи Задача о кёнигсбергских мостах. Пройти по всем мостам центра старого Кёнигсберга по одному разу. Решена Леонардом Эйлером в публикации, датированной 1736 годом, это первый результат теории графов (первая теорема в той же публикации — сумма степеней вершин графа равна удвоенному числу его рёбер).
Иногда эту задачу переносят на систему мостов других городов. Например, была опубликована задача о 17 мостах устья Невы города Ленинграда 1940 года.
Проблема четырёх красок — можно ли любую карту окрасить в четыре цвета так, чтобы смежные страны имели различные цвета? Сформулирована в 1852 году, в 1977 году опубликовано (анонсировано в 1976) первое общепринятое положительное доказательство с использованием компьютера. Задача о домино. Все 28 костей игры в домино должны соединиться в непрерывную (простую) цепь так, чтобы граничащие половинки двух камней имели одно и то же число. Так как наличие дублей задачу не усложняет, задача о домино ставится также для 21 кости (без дублей) без потери общности. Задача о лабиринте. Войти в произвольный лабиринт и пройти по всем его коридорам. Задача о трёх домах и трёх колодцах. Проложить непересекающиеся дорожки от каждого из трёх домов к каждому из трёх колодцев. Эта задача, как и задача о кёнигсбергских мостах, решения не имеет. Задача о ходе коня. Обойти конём шахматную доску, посетив каждую клетку ровно один раз с возвратом на исходную клетку. Задача о назначениях. Пусть компании требуется несколько различных видов работ, причём каждый сотрудник подходит только для некоторых из них и может выполнять не более одной работы за раз. Как следует распределять задания, чтобы выполнять максимальное количество заданий одновременно? Решить задачу помогает двудольный граф, в котором вершины одной доли — сотрудники, другой — рабочие места, и каждое ребро — подходящее назначение на работу.
Задачи комбинаторной оптимизации По книге «Комбинаторная оптимизация». Задача о кратчайшем пути. Дан (ориентированный) граф и каждый вес его ребра (дуги) представляет время, необходимое для её прохождения. Найти кратчайший путь (по времени) между заданными вершинами. Задача о минимальном остовном дереве. Пусть нужно соединить несколько компьютеров в фиксированных местах, чтобы сформировать компьютерную сеть, и известна стоимость создания прямого соединения между любой парой компьютеров. Какие прямые соединения следует построить, чтобы стоимость сети была минимальна? Задача Штейнера о минимальном дереве. Пусть имеется произвольное подмножество вершин связного взвешенного графа. Найти подграф-дерево с минимальной суммой весов рёбер, содержащее все вершины заданного подмножества. Задача коммивояжёра (TSP). Пусть продавцу нужно посетить несколько городов в течение следующего месяца. Весовые коэффициенты представляют затраты на поездки между каждой парой городов. Как упорядочить визиты так, чтобы свести к минимуму общую стоимость поездки? Другими словами, нужно найти гамильтонов цикл, общий вес рёбер которого минимален. Задача о максимальном потоке. Пусть вода перекачивается по сети трубопроводов от источника к стоку. Графовая модель — сеть, где каждый вес дуги — верхняя граница потока через соответствующий трубопровод. Найти максимальный поток от источника к стоку. Задача о китайском почтальоне. Найти минимальный по весу цикл по всем рёбрам в заданном взвешенном графе, где веса рёбер зависит от приложения (например, расстояние, время, стоимость и т. д.). Задача о китайском почтальоне (орграф). При выполнении поток компьютерной программы перемещается между различными состояниями, и переходы из одного состояния в другое зависят от входных данных. При тестировании программного обеспечения хотелось бы генерировать входные данные так, чтобы были протестированы все возможные переходы. Поток выполнения программы моделируется орграфом, где вершины — состояния программы, дуги — переходы, и каждой из дуг присваивается метка вызова соответствующего перехода. Тогда задача нахождения последовательности входных данных, вызывающей все переходы и минимизирующей общее их число, эквивалентна нахождению ориентированного пути китайского почтальона минимальной длины.
Задача реконструкции РНК. По неупорядоченным фрагментам одной и той же РНК реконструировать эту РНК-цепочку или полное множество подходящих РНК-цепочек. Задача реконструкции строки цифр. Пусть для данной строки цифр — число цифр в строке, — число подстрок в строке. Сколько существует различных строк, отвечающих данным и ?
Менее известные задачи Задача изоморфности графов. Разработать общий алгоритм для определения изоморфизма графа или, в качестве альтернативы, доказать, что такого алгоритма не существует. . Могут ли два неизоморфных простых графа с тремя или более вершинами и без меток на вершинах иметь одинаковый список подграфов, каждый из которых получен удалением одной вершины? Задача о подмножестве с максимальным весом. Пусть для каждого ребра графа задан неотрицательный вес. Найти подмножество системы независимости с максимальной суммой весов его рёбер. Задача о паросочетании с максимальным весом. Частный случай предыдущей задачи. Задача о максимизации. Определить в графе максимальное число вершинно независимых путей, соединяющих любую пару вершин. Задача о минимизации. Определить в графе минимальное число вершин, разделяющих любую пару вершин. Задача гомеоморфизма подграфов. Определить, содержит ли первый граф подграф, гомеоморфный второму графу. Задача о клике — ещё одна NP-полная задача. Планарность графа — можно ли изобразить граф на плоскости без пересечений рёбер (или с минимальным числом слоёв, что находит применение при трассировке межсоединений элементов печатных плат или микросхем).
Классификации применений теории графов
Классификация применений теории графов по степени отношения к математике: математические области: теория групп, теория матриц, численный анализ, теория вероятностей, топология, комбинаторный анализ и математическая модель для бинарных отношений; нематематические области: физика, химия, теория связи, проектирование вычислительных машин, электротехника, машиностроение, архитектура, исследование операций, генетика, психология, социология, экономика, антропология и лингвистика.
Классификация применений теории графов по степени материальности взаимодействия: более материальные взаимодействия представляют, в частности, физические сети (например, электрические цепи), дороги, органические молекулы; менее материальные взаимодействия представляют, в частности, экосистемы, социологические отношения, базы данных, поток управления в компьютерной программе.
Классификация применений теории графов по видам применяемых графов: простые графы, то есть не мультиграфы, орграфы или псевдографы; мультиграфы и псевдографы, но не орграфы; простые орграфы; (псевдо)орграфы.
Классификация применений теории графов по видам атрибутов применяемых графов: рёбра и вершины применяемого графа не имеют атрибутов; рёбра применяемого графа имеют атрибуты, вершины не имеют; вершины применяемого графа имеют атрибуты, рёбра не имеют; и рёбра, и вершины применяемого графа имеют атрибуты.
Классификация применений теории графов по областям применения. Классификация проводится по оглавлению второй части книги. Приложения к экономике и исследованию операций. Комбинаторные задачи. Головоломки и игры. Паросочетания. Технические приложения. Естественные науки. Задачи изучения человека и общества. Дополнительные приложения. Потоки в сетях.
Классификация применений теории графов по областям применения. Классификация проводится по имеющейся научной литературе. Список некоторых областей применения теории графов со ссылками на литературу: археология; блок-схемы; искусственный интеллект; конечные автоматы; логистика; программирование; социология; схемотехника; теория алгоритмов; управление воздушным движением; хемоинформатика; химическая кинетика (например, правило фаз); химия (компьютерная химия); экономика.
Некоторые применения теории графов Перед приложением математической силы к задачам реального мира необходимо построить математическую модель задачи. Графы — удивительно универсальный инструмент математического моделирования. Ниже представлены несколько применений теории графов, отличных от задач теории графов, по книге «Теория графов и её приложения».
Комбинаторная оптимизация. 1) Вес ребра — один из наиболее часто используемых атрибутов графов, особенно при комбинаторной оптимизации. Например, вес ребра может представлять: транспортные расходы; время в пути; пространственное расстояние; потери мощности; верхние границы потока; входы и выходы для переходов в конечном автомате. 2) Существует проблемы, решаемые заданием атрибутов вершин в графовой модели. Например, вес вершины может представлять: стоимость производства; интервал времени в теории расписаний; состояние марковского процесса; состояние узла в сети соединений.
Модели на простых графах Археология. Пусть коллекция артефактов найдена на месте города, который существовал с 1000 года до нашей эры по 1000 год нашей эры. Тогда можно построить граф с вершинами — артефактами, и вершины смежны, когда соответствующие артефакты из одной могилы. Предположим, что артефакты, найденные в одной могиле, имеют перекрывающиеся промежутки времени использования. Если построить интервальный граф, то имеет место распределение подинтервалов исходного интервала (-1000, 1000) (возможно масштабирование), согласующееся с археологической находкой. Социология. В социальной сети знакомств вершины — люди, а рёбра указывают на то, что соответствующие пары людей знают друг друга. Включение концепции самопознания требует в модели циклы самопознания, которым в графе соответствуют петли. География. В географической модели вершины графа могут представлять страны (области, штаты), а рёбра — общую границу. Геометрия. Конфигурация вершин и рёбер любого многогранника в трёхмерном пространстве образует простой граф, который называется его . 1-скелеты платоновых тел — регулярные графы. Проектирование вычислительных машин. Некоторое число процессоров соединяются вместе на одном чипе для многопроцессорного компьютера, который может выполнять параллельные алгоритмы. В графовой модели для такой сети взаимосвязей вершина — отдельный процессор, ребро — прямая связь между двумя процессорами. Спецификация параллельных архитектур иллюстрирует некоторые взаимодействия между теорией графов и абстрактной алгеброй.