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

Обзорная статья: Теория графов

Примене́ние тео́рии гра́фов — использование теории графов как математического орудия в различных дисциплинах.

Отец теории графов Леонард Эйлер

Уже в XIX веке графы применялись при проектировании электрических цепей и молекулярных схем; математические развлечения и головоломки — тоже часть теории графов.

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

Несмотря на разнообразные, усложнённые, малопонятные и специализированные термины многие модельные (схемные, структурные) и конфигурационные проблемы переформулируются на языке теории графов, что позволяет значительно проще выявить их концептуальные трудности. В разных областях знаний понятие «граф» может встречаться под следующими названиями:

• структура (гражданское строительство);
• сеть (электротехника);
• социограмма (социология и экономика);
• молекулярная структура (химия);
• навигационная карта (картография);
• распределительная сеть (энергетика)

и так далее.

Некоторые задачи теории графов

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

Наиболее известные задачи

• Задача о кёнигсбергских мостах. Пройти по всем мостам центра старого Кёнигсберга по одному разу. Решена Леонардом Эйлером в публикации, датированной 1736 годом, это первый результат теории графов (первая теорема в той же публикации — сумма степеней вершин графа равна удвоенному числу его рёбер).

Иногда эту задачу переносят на систему мостов других городов. Например, была опубликована задача о 17 мостах устья Невы города Ленинграда 1940 года.

• Проблема четырёх красок — можно ли любую карту окрасить в четыре цвета так, чтобы смежные страны имели различные цвета? Сформулирована в 1852 году, в 1977 году опубликовано (анонсировано в 1976) первое общепринятое положительное доказательство с использованием компьютера.

• Задача о домино. Все 28 костей игры в домино должны соединиться в непрерывную (простую) цепь так, чтобы граничащие половинки двух камней имели одно и то же число. Так как наличие дублей задачу не усложняет, задача о домино ставится также для 21 кости (без дублей) без потери общности.

• Задача о лабиринте. Войти в произвольный лабиринт и пройти по всем его коридорам.

• Задача о трёх домах и трёх колодцах. Проложить непересекающиеся дорожки от каждого из трёх домов к каждому из трёх колодцев. Эта задача, как и задача о кёнигсбергских мостах, решения не имеет.

• Задача о ходе коня. Обойти конём шахматную доску, посетив каждую клетку ровно один раз с возвратом на исходную клетку.

• Задача о назначениях. Пусть компании требуется несколько различных видов работ, причём каждый сотрудник подходит только для некоторых из них и может выполнять не более одной работы за раз. Как следует распределять задания, чтобы выполнять максимальное количество заданий одновременно? Решить задачу помогает двудольный граф, в котором вершины одной доли — сотрудники, другой — рабочие места, и каждое ребро — подходящее назначение на работу.

Задачи комбинаторной оптимизации

По книге «Комбинаторная оптимизация».

• Задача о кратчайшем пути. Дан (ориентированный) граф и каждый вес его ребра (дуги) представляет время, необходимое для её прохождения. Найти кратчайший путь (по времени) между заданными вершинами.

• Задача о минимальном остовном дереве. Пусть нужно соединить несколько компьютеров в фиксированных местах, чтобы сформировать компьютерную сеть, и известна стоимость создания прямого соединения между любой парой компьютеров. Какие прямые соединения следует построить, чтобы стоимость сети была минимальна?

• Задача Штейнера о минимальном дереве. Пусть имеется произвольное подмножество вершин связного взвешенного графа. Найти подграф-дерево с минимальной суммой весов рёбер, содержащее все вершины заданного подмножества.

• Задача коммивояжёра (TSP). Пусть продавцу нужно посетить несколько городов в течение следующего месяца. Весовые коэффициенты представляют затраты на поездки между каждой парой городов. Как упорядочить визиты так, чтобы свести к минимуму общую стоимость поездки? Другими словами, нужно найти гамильтонов цикл, общий вес рёбер которого минимален.

• Задача о максимальном потоке. Пусть вода перекачивается по сети трубопроводов от источника к стоку. Графовая модель — сеть, где каждый вес дуги — верхняя граница потока через соответствующий трубопровод. Найти максимальный поток от источника к стоку.

• Задача о китайском почтальоне. Найти минимальный по весу цикл по всем рёбрам в заданном взвешенном графе, где веса рёбер зависит от приложения (например, расстояние, время, стоимость и т. д.).

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

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

• Задача реконструкции РНК. По неупорядоченным фрагментам одной и той же РНК реконструировать эту РНК-цепочку или полное множество подходящих РНК-цепочек.

• Задача реконструкции строки цифр. Пусть для данной строки цифр $f_{i}$ — число цифр $i$ в строке, $f_{ij}$ — число подстрок $ij$ в строке. Сколько существует различных строк, отвечающих данным $f_{i}$ и $f_{ij},$ $i,j=1,2,\dots ,n,$ $f_{ii}=0$?

Менее известные задачи

• Задача изоморфности графов. Разработать общий алгоритм для определения изоморфизма графа или, в качестве альтернативы, доказать, что такого алгоритма не существует.

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

• Задача о подмножестве системы независимости с максимальным весом. Пусть для каждого ребра графа задан неотрицательный вес. Найти подмножество системы независимости с максимальной суммой весов его рёбер.

• Задача о паросочетании с максимальным весом. Частный случай предыдущей задачи.

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

• Задача о минимизации. Определить в графе минимальное число вершин, разделяющих любую пару вершин.

• Задача гомеоморфизма подграфов. Определить, содержит ли первый граф подграф, гомеоморфный второму графу.

• Задача о клике — ещё одна NP-полная задача.

• Планарность графа — можно ли изобразить граф на плоскости без пересечений рёбер (или с минимальным числом слоёв, что находит применение при трассировке межсоединений элементов печатных плат или микросхем).

Классификации применений теории графов

• Классификация применений теории графов по степени отношения к математике:

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

• Классификация применений теории графов по степени материальности взаимодействия:

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

• Классификация применений теории графов по видам применяемых графов:

• простые графы, то есть не мультиграфы, орграфы или псевдографы;
• мультиграфы и псевдографы, но не орграфы;
• простые орграфы;
• (псевдо)орграфы.

• Классификация применений теории графов по видам атрибутов применяемых графов:

• рёбра и вершины применяемого графа не имеют атрибутов;
• рёбра применяемого графа имеют атрибуты, вершины не имеют;
• вершины применяемого графа имеют атрибуты, рёбра не имеют;
• и рёбра, и вершины применяемого графа имеют атрибуты.

• Классификация применений теории графов по областям применения.

Классификация проводится по оглавлению второй части книги.

• Приложения к экономике и исследованию операций.
• Комбинаторные задачи.
• Головоломки и игры.
• Паросочетания.
• Технические приложения.
• Естественные науки.
• Задачи изучения человека и общества.
• Дополнительные приложения.
• Потоки в сетях.

• Классификация применений теории графов по областям применения.

Классификация проводится по имеющейся научной литературе. Список некоторых областей применения теории графов со ссылками на литературу:

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

Некоторые применения теории графов

Перед приложением математической силы к задачам реального мира необходимо построить математическую модель задачи. Графы — удивительно универсальный инструмент математического моделирования. Ниже представлены несколько применений теории графов, отличных от задач теории графов, по книге «Теория графов и её приложения».

• Комбинаторная оптимизация. 1) Вес ребра — один из наиболее часто используемых атрибутов графов, особенно при комбинаторной оптимизации. Например, вес ребра может представлять:

• транспортные расходы;
• время в пути;
• пространственное расстояние;
• потери мощности;
• верхние границы потока;
• входы и выходы для переходов в конечном автомате.

2) Существует проблемы, решаемые заданием атрибутов вершин в графовой модели. Например, вес вершины может представлять:

• стоимость производства;
• интервал времени в теории расписаний;
• состояние марковского процесса;
• состояние узла в сети соединений.

Модели на простых графах

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

• Социология. В социальной сети знакомств вершины — люди, а рёбра указывают на то, что соответствующие пары людей знают друг друга. Включение концепции самопознания требует в модели циклы самопознания, которым в графе соответствуют петли.

• География. В географической модели вершины графа могут представлять страны (области, штаты), а рёбра — общую границу.

• Геометрия. Конфигурация вершин и рёбер любого многогранника в трёхмерном пространстве образует простой граф, который называется его 1-скелетом. 1-скелеты платоновых тел — регулярные графы.

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

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

• Физическая химия. Углеводород — химическая молекула, состоящая из атомов водорода и углерода. Он насыщен, если в нем содержится максимальное число атомов водорода для его атомов углерода. Насыщение происходит, когда присутствуют только простые связи, то есть когда структурная модель углеводорода — простой граф. Атом водорода имеет один электрон всегда 1-валентен в молекуле. Атом углерода 4-валентный и имеет четыре электрона на своей внешней оболочке. Насыщенные углеводороды бутан и изобутан имеют одинаковую химическую формулу ${\ce {C4H10}}$, но их графы неизоморфны, поэтому они изомеры.

• Информатика. Для сети из $n$ компьютеров существует ${n \choose 2}={\frac {n^{2}-n}{2}}$ возможных пар компьютеров, которые могут быть напрямую соединены. Если все пары связаны, то $n$ компьютеров подключены, но многие из связей не нужны. Если компьютеры соединены минимальным количеством рёбер, то эти рёбра образуют дерево и количество рёбер в дереве на единицу меньше, чем количество вершин.

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

• Теория алгоритмов. Пусть некоторый распределенный алгоритм работает в сети межсоединений с архитектурой — массивом $8\times 8\times 32$. И пусть доступная сеть соединений — 13-мерный граф гиперкуба $Q_{13}$. Если 13-мерный граф гиперкуба содержит подграф — сетку размером $8\times 8\times 32$, то алгоритм можно напрямую перенести в этот гиперкуб.

• Информатика. Величины k вершинной k-связности и рёберной k-связности используются в количественной модели живучести сети, которая представляет собой способность сети сохранять соединения между своими узлами после удаления некоторых рёбер или узлов.

• Информатика. В сети связи ошибка — разрушение (удаление) вершины или ребра из моделирующего графа. Таким образом, чем выше связность вершин и рёбер, тем надежнее сеть. Чем меньше соединений используется для подключения, тем дешевле сеть. Получаем следующую задачу оптимизации: при k меньшем n найти k-связный n-вершинный граф, имеющий наименьшее число рёбер.

• Теория кодирования. Космический аппарат передаёт некоторое закодированное числами изображение, где числа — значения темноты для точек изображения. Преимущество кодирования изображения кодом Грея заключается в том, что если ошибка из-за «космического шума» приводит к неправильному прочтению одной двоичной цифры в числе, то интерпретация этого числа слабо отклонится от истинного значения темноты. Код Грея порядка $n$ соответствует гамильтонову циклу в графе гиперкуба $Q_{n}$.

• Проектирование вычислительных машин. Один из методов миниатюризации непланарной электронной сети — нанесение изоляции между плоскими слоями неизолированных проводников, которые соединяют узлы. Размер и стоимость чипа уменьшаются при минимизации количества слоев. Простой подход к проектированию многослойных схем заключается в использовании «совмещённых чертежей отрезков» остовных подграфов, которые индуцируют рёберное разбиение. Это означает, что узлы в каждом слое находятся в одном и том же положении на плоскости, и каждый слой рисуется рёбрами-отрезками.

• Теория связи. Минимум радиолокационных станций, необходимых для наблюдения за несколькими стратегическими объектами — число доминирования соответствующего графа.

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

• Информатика. Рассмотрите задачу размещения ферзей на шахматной доске: каждая клетка доски либо занята ферзём, либо достигается ферзём за один ход. Определение минимального числа ферзей эквивалентно нахождению числа доминирования графа с 64 вершинами, где рёбра соответствует ходам ферзей.

• Модели на корневых деревьях.

• Базы данных. Многие информационные структуры информатики основаны на деревьях. Каталоги и подкаталоги (или папки и подпапки), содержащие файлы пользователя компьютера, обычно представляются операционной системой в виде вершин корневого дерева.

• Базы данных. Двоичные деревья поиска хранят специально упорядоченные данные для эффективного поиска. В частности, если $n$ вершин двоичного дерева поиска используются соответствующим образом для хранения ключей $n$ элементов данных, то поиск может быть завершён за время выполнения $O(\log(n))$.

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

• Базы данных. Корневые деревья используются для хранения информации, организованной по категориям и подкатегориям. Десятичная классификация Дьюи для библиотек является одним из таких примеров.

• Лингвистика. Корневое дерево можно использовать для синтаксического анализа предложения на естественном языке.

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

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

• Теория кодирования. Двоичное дерево можно использовать для построения префиксного кода для заданного набора символов. Для этого конечные вершины двоичного дерева помечаются данными символами, рёбра — 0 и 1 слева направо, тогда кодовое слово будет составлено из меток рёбер на пути от корня к символу.

• Модели на раскрашенных графах.

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

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

• Исследование операций. Пусть верины графа — учебные курсы в университете, ребро соединяет два курса тогда и только тогда, когда хотя бы один студент записался на оба курса. Такие курсы не могут проходить одновременно. Тогда хроматическое число графа — минимальное число разнесённых по времени академических часов в расписании занятий, при котором у студентов не возникнет конфликт учебных курсов.

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

• Исследование операций. Пусть верины графа — учебные курсы в университете, ребро соединяет два курса тогда и только тогда, когда хотя бы три студента записались на оба курса. Такие курсы не могут проходить одновременно. Но число разнесённых по времени академических часов в расписании занятий меньше хроматического числа графа, при котором у студентов не возникнет конфликт учебных курсов. Тогда приходится планировать так, чтобы свести к минимуму количество конфликтов. Если рёбрам графа присваивается вес в зависимости от степени нежелательности конфликта, например, ребро связывает учебные курсы одного и того же преподавателя, то надо найти раскраску с общим наименьшим весом рёбер с одноцветными концами.

• Проектирование вычислительных машин. Несколько электронных устройств находятся на печатной плате. Соединительные провода, выходящие из устройств, должны быть окрашены по-разному, чтобы их можно было различить. Наименьшее количество требуемых цветов — ребёрное хроматическое число моделирующей сети.

Модели на мультиграфах и псевдографах

• География. В географической модели вершины мультиграфа могут представлять страны (области, штаты), а рёбра — дороги, пересекающие общую границу.

• Химия. Молекулы непредельных углеводородов имеют кратные связи для некоторых пар своих атомов, поэтому они моделируются мультиграфами. Атом углерода имеет валентность 4 и моделируется вершиной мультиграфа степени 4, атом водорода имеет валентность 1 и моделируется вершиной степени 1

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

• Проектирование вычислительных машин. Графы случайного обмена служат моделями для параллельных архитектур, подходящих для выполнения различных распределённых алгоритмов, включая перетасовку карт и быстрое преобразование Фурье. Вершины псевдографа случайного обмена $SE_{n}$ являются битовыми строками длины $n$.

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

• Транспорт. Каждые выходные частная школа перевозит n детей на m автобусных остановок. Родители встречают своих детей на автобусных остановках. Школе принадлежит k автобусов с разной вместимостью. Как построить маршруты автобусов с минимальной общей стоимостью? Вершины графа — школа и остановки, вес рёбер — расстояния между ними. В каждый автобус можно посадить несколько групп детей, выходящих на разных остановах, так, чтобы не превысить вместимость автобуса. Стоимость автобусного маршрута равна стоимости гамильтонова цикла минимального веса. Таким образом, задача состоит в том, чтобы разбить m автобусных остановок на k подмножеств так, чтобы сумма стоимости маршрутов всех автобусов была минимальна.

• Исследование операций. В университете есть несколько преподавателей для чтения нескольких учебных курсов. Требуется рассчитать минимальное количество академических часов в расписании занятий, необходимых для планирования всех курсов, чтобы одновременно не преподавались два раздела одного и того же курса. Строим двудольный граф на долях преподавателей и учебных курсов, рёбра соединяют преподавателей с их курсами (преподаватель может читать разные курсы, и один курс могут читать разные преподаватели). Подбор преподавателей для курсов можно осуществить за некоторый промежуток времени. Если цвет рёбра — академический час в дневном расписании, то окраска рёбер двудольного графа — возможное расписание для разделов курсов. Минимальная окраска рёбер использует наименьшее количество академических часов.

Модели на простых орграфах

• Картография. Карту улиц города можно представить в виде смешанного графа следующим образом. Вершины этого графа — объекты города, а ориентированные и простые рёбра — соответственно улицы с односторонним и двусторонним движением.

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

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

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

• Программирование. Компьютерная программа — набор блоков программирования с соответствующим потоком управления. Орграф — естественная модель для этой декомпозиции: вершина — блок программирования связан, и если управление по последней инструкции одного блока передаётся первой инструкции другого блока, то рисуется дуга из первого блока во второй. Блок-схемы обычно не имеют кратных дуг.

• Электротехника. Определить электрический ток в каждой ветви электрической цепи, используя Закон Ома, первое правило Кирхгофа и второе правило Кирхгофа. Эффективная стратегия решения — с помощью остовного дерева найти минимальный набор контуров орграфа, соответствующих уравнений которых достаточно для решения задачи. Фундаментальный базис циклов — основа для пространства циклов, поэтому его соответствующие уравнения составят полный набор линейных алгебраических уравнений и задача будет решена.

• Программирование. Пусть на одной машине обрабатывается n заданий. Известно время, необходимое для обработки любого задания после любого другого. Как упорядочить задания, чтобы минимизировать общее время? Рисуем орграф с n вершинами — заданиями и с соответствующими весами дуг. Тогда искомую последовательность заданий даёт гамильтонов путь с минимальным весом.

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

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

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

• Экономика. Модель орграфа используется при планировании крупных сложных проектов для достижения двух целей: запланировать мероприятия так, чтобы время завершения проекта было минимально; определить мероприятия, задержка которых приведет к задержке проекта. Если продолжительность каждого мероприятия известна, то для решения этих проблем используют метод критического пути (CPM).

Модели на (псевдо)орграфах

• Цепь Маркова. В марковском процессе вероятность перехода из одного состояния в другое зависит только от текущего состояния. В графовой модели цепи Маркова каждая дуга помечена вероятностью перехода из состояния в начальной вершине в состояние в концевой вершине, и сумма вероятностей на исходящих дугах из каждой вершины равна 1. Диаграмма Маркова — пример взвешенного графа.

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

• Теория игр. Пусть игрок, начиная с 3 долларов, играет в следующую игру. Бросаются две монеты. Если выпадет два орла, то игрок выиграет 3 доллара, иначе потеряет 1 доллар. Игрок играет до тех пор, пока либо не потеряет все деньги, либо будет иметь не менее 5 долларов. Графовая модель — граф цепи Маркова.

• Применение эйлерова цикла и задачи о китайском почтальоне.

• Теория кодирования. Пусть вращающийся барабан имеет 16 различных секторов. Присвоим 0 или 1 каждому сектору, поместив проводящий материал в некоторые сектора и непроводящий в другие. Затем неподвижными датчиками «считываем» 4-битную строку, соответствующую четырем секторам, попавшим на датчики. Если 16-битовая строка секторов барабана — (2, 4)-последовательность де Брёйна, то положение барабана можно определить по 4-битной подстроке, которую улавливают датчики. Это более экономично, чем 4-битный код в каждом секторе. (2, 4)-последовательность де Брёйна строится с помощью (2, 4)-орграфа де Брёйна.

• Городское хозяйство. Орграф — сеть улиц с односторонним движением, жирные дуги — улицы, которые необходимо подмести, вес ребра — время прохождения улицы без подметания, а время, необходимое для подметания улицы, вдвое больше. Какой маршрут минимизирует общее время для подметания всех необходимых улиц, начиная и заканчивая заданной вершиной?

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

• Социология. Пусть некоторые пары в отделе из шести человек должны встретиться конфиденциально в одном и том же конференц-зале. Можно ли организовать конференции из двух человек так, чтобы один из участников каждой конференции (кроме последней) также участвовал в следующей, но никто не участвовал в трёх последовательных конференциях?

• Генетика. В цепи РНК (рибонуклеиновой кислоты) каждое звено представляет собой один из четырёх возможных нуклеотидов. При попытке идентифицировать цепь РНК в неизвестном образце существующая технология не позволяет напрямую идентифицировать длинные цепи. Существует метод фрагментации и субфрагментации длинной цепи РНК на идентифицируемые подцепи. Стратегия Хатчинсона состоит в том, чтобы построить орграф Эйлера, дуги которого помечены фрагментами, так что каждый эйлеров путь соответствует цепочке РНК.

• Комбинаторика. Обобщая предыдущее применение в генетике, РНК можно представить как строку номеров нуклеотидов. Пусть для данной строки цифр $f_{i}$ — число цифр $i$ в строке, $f_{ij}$ — число подстрок $ij$ в строке. Тогда информация, заложенная в РНК, зависит только от чисел $f_{i}$ и $f_{ij}$, $i,j=1,2,\dots ,n$, $f_{ii}=0$. Для реконструкции строки строим орграф по матрице смежности $(f_{ij})$, где вместо $f_{ii}=0$ стоят $f_{i}$. Тогда все различные эйлеровы пути дадут все возможные подходящие строки.

Некоторые алгоритмы теории графов

Алгоритмы представлены в сжатом формате, без подробностей компьютерной реализации. Имеется множество проектов, предлагающих преобразовать алгоритмы в компьютерные программы, по книге «Теория графов и её приложения».

• Рекурсивная графическая последовательность. Рекурсивный алгоритм, который определяет, является ли невозрастающая последовательность последовательностью степеней вершин некоторого графа.
• Определение изоморфизма графов полным перебором. Два графа изоморфны, если их наборы вершин можно упорядочить так, чтобы их матрицы смежности были идентичны.
• Прямой левый обход дерева (NLR). Сначала обходим левое поддерево, вносим в список каждую вершину только при появлении её впервые.
• Обратный левый обход дерева (LRN). Сначала обходим левое поддерево, вносим в список каждую вершину только при появлении её в последний раз.
• Центрированный левый обход дерева (LNR). Сначала обходим левое поддерево, вносим в список каждую вершину, имеющую левое поддерево, только при её появлении во второй раз, остальные вершины вносим в список при их появлении в первый раз.
• Поиск в двоичном дереве поиска. На каждой итерации исключаем либо левое, либо правое поддерево из остальной части поиска в зависимости от того, что целевой ключ соответственно больше или меньше ключа в текущей вершине.
• Добавление в двоичное дерево поиска. С итеративной точки зрения двоичный поиск выполняется до тех пор, пока он не завершится на конечной вершине. Затем новый ключ присваивается новой вершине, которая становится левым или правым поддеревом этой конечной вершины в зависимости от сравнения нового ключа с ключом конечной вершины.
• Алгоритм Хаффмана. В префиксном коде, который использует более короткие кодовые слова для кодирования более часто встречающихся символов, сообщения обычно требуют меньше битов, чем в коде, который этого не делает. Алгоритм Хаффмана строит именно такой эффективный префиксный код, объединяя в исходном лесу два дерева наименьшего веса в новое дерево.
• Добавление в дерево приоритетов. Сначала добавляют новую вершину на первое свободное место в дереве приоритетов, а затем перемещают её вверх к корню, пока её приоритет не станет меньше или равен приоритету родительской вершины.
• Удаление из дерева приоритетов. Сначала удаляемая вершина заменяется вершиной, занимающей крайнее правое место на нижнем уровне дерева приоритетов. Затем эта вершина итеративно стекает вниз, меняясь местами с потомком, имеющим больший приоритет, пока её приоритет не превысит приоритеты обоих потомков.
• Кодирование Прюфера. Последовательность Прюфера длиной $n-2$ строится из данного дерева с $n$ вершинами, занумерованными числами $1,2,\dots ,n$, путём удаления вершин, пока не останется $2$ вершины.
• Декодирование Прюфера. Закодированное дерево восстанавливается по последовательности Прюфера $p_{1},p_{2},\dots ,p_{n-2}$ и списку номеров вершин дерева $1,2,\dots ,n$.
• Построение остовного дерева. Начиная с заданной вершины графа строится остовное дерево с корнем в заданной вершине, используя любую схему поиска новых вершин дерева, смежных со старыми вершинами.
• Построение остовного леса. Начиная с заданной вершины каждой компоненты несвязного графа строится остовное дерево текущей компоненты с корнем в заданной вершине, используя любую схему поиска новых вершин дерева, смежных со старыми вершинами.
• Поиск в глубину (DFS). Начиная с заданной вершины графа строится дерево поиска следующим образом. На графе выбирается новая вершина, смежная с самой последней обнаруженной вершиной уже построенного дерева. Если это невозможно, происходит возвращение к предыдущей обнаруженной вершине и попытка повторяется. В итоге поиск продвигается вглубь графа (отсюда и название «в глубину»).
• Поиск в ширину (BFS). Начиная с заданной вершины графа строится дерево поиска следующим образом. Поиск «разветвляется» от заданной вершины и увеличивает дерево, выбирая смежные ребра с вершинами дерева, расположенными как можно ближе к заданной вершине. В итоге поиск продвигается по ширине графа слоями, равноудалёнными от заданной вершины (отсюда и название «в ширину»).
• Минимальное остовное дерево Прима. Ищется остовное дерево связного взвешенного графа с минимальной суммой весов рёбер. Начинаем с любой вершины графа и на каждой итерации строим дерево Прима добавлением новой вершины, соединённой с деревом ребром с минимальным весом.
• Кратчайший путь Дейкстры. Ищутся кратчайшие пути от заданной вершины взвешенного графа сразу до всех других вершин. Начинаем с заданной вершины графа и на каждой итерации добавляем к обработанным вершинам новую, соединённую ребром с одной из обработанных вершин и наиболее близкую к заданной вершине.
• Применение поиска в глубину.

• Поиск мостов. На заданном связном графе ищутся мосты с помощью первого прохода поиска в глубину до первого возврата и стягивания всех рёбер цикла в одну вершину.
• Топологическая сортировка. На заданном бесконтурном орграфе производится нумерация вершин, начиная с максимального номера, с помощью первого прохода поиска в глубину до первого возврата и нумерации последней вершины пути текущим максимальным номером с удалением этой вершины из последующих поисков.
• Поиск точек сочленения. На заданном связном графе ищутся точки сочленения с помощью поиска в глубину, специальной нумерации вершин дерева поиска в глубину и сравнения этих номеров.
• Поиск блоков. Для заданного связного графа ищутся все его блоки. Предыдущий алгоритм используется как подпрограмма.
• Алгоритм Тарри выхода из лабиринта. Никогда не возвращайтесь, если есть альтернатива, и никогда не проходите второй раз в том же направлении. Другими словами, всегда проходите по новому пути, прежде возвратиться, что делает этот алгоритм разновидностью поиска в глубину.
• Алгоритм ближайшего соседа в задаче коммивояжёра. Самая простая эвристика TSP — ближайший сосед. Это жадный алгоритм: выбирается самый дешёвый способ отправиться куда-нибудь ещё. Другими словами, алгоритм ближайшего соседа — обход по глубине, при котором выбираются рёбра наименьшего веса.
• Алгоритм поиска компонент сильной связности. Алгоритм, использующий поиск в глубину в комбинации с двумя стеками. Стратегия поиска взаимно достижимых вершин состоит в том, чтобы отслеживать, как дуги, не принадлежащие дереву, соединяют его вершины.

• Жадный алгоритм решения задачи о подмножестве системы независимости с максимальном весом. Пусть для каждого ребра графа задан неотрицательный вес, и задана система независимости графа. Перебираем все рёбра графа, начиная с максимального веса, и строим из них подмножество системы независимости с максимальной суммой весов рёбер.
• Жадный алгоритм решения задачи о паросочетании с максимальном весом. Частный случай предыдущего алгоритма.
• Построение оптимального $k$-связного графа с $n$ вершинами. Фрэнк Харари разработал процедуру построения $k$-связного графа Харари $H_{k,n}$ на $n$ вершинах, имеющего минимальное количество $\left\lceil {\frac {kn}{2}}\right\rceil$ ребер для $k\geqslant 2$. Построение графа Харари $H_{k,n}$ начинается с $n$-циклического графа, вершины которого последовательно пронумерованы числами $0,1,2,\dots ,n-1$ по часовой стрелке по периметру. Построение $H_{k,n}$ зависит от соотношения $k$ и $n$ и распадается на три случая.
• Построение эйлерова цикла. В связном графе, все вершины которого имеют чётную степень, выбираем любую вершину и считаем её эйлеровым циклом. На каждой итерации добавляем любой цикл из новых рёбер, имеющий с текущим эйлеровым циклом общую вершину.
• Построение (2, n)-последовательности де Брёйна. Строим (2, n)-орграф де Брёйна. Выбираем в этом орграфе вершину и строим ориентированный эйлеров цикл орграфа, начиная с выбранной вершины. Последовательно, начиная с выбранной вершины, обходим эйлеров цикл и собираем однобитовые метки дуг графа в последовательность де Брёйна.
• Построение цикла почтальона. Прослеживаем рёбра по кратчайшим путям взвешенного связного графа между вершинами нечётной степени. Если все рёбра пути между двумя вершинами нечётной степени дублируются, то степени этих двух вершин становятся чётными, а чётность степени каждой внутренней вершины пути остаётся неизменной.
• Алгоритм минимального остовного дерева и его удвоения в задаче коммивояжёра. Находим минимальное остовное дерево. Удваиваем каждое ребро дерева, получаем эйлеров граф. Строим эйлеров цикл. Строим гамильтонов цикл из эйлерова цикла, используя при обрыве эйлерова цикла короткие пути.
• Алгоритм минимального остовного дерева и паросочетаний в задаче коммивояжёра. Находим минимальное остовное дерево. Строим эйлеров граф, добавляя к остовному дереву рёбра из некоторого паросочетания. Строим эйлеров цикл. Строим гамильтонов цикл из эйлерова цикла, используя при обрыве эйлерова цикла короткие пути.
• Простая проверка планарности двусвязного графа. Алгоритм требует $O(n^{2})$ вычислительных шагов. Сначала рисуем любой цикл двусвязного графа. Затем добавляем циклы до тех пор, пока граф не будет построен (планарный) или рёбрам придётся пересечься (непланарный).
• Жадная раскраска вершин. Последовательный алгоритм, который быстро проходит вершины графа в некоторой заданной последовательности и назначает каждой вершине первый доступный цвет. Эта раскраска вряд ли будет минимальной, и маловероятно, что какой-либо алгоритм с полиномиальным временем может выполнить это, поскольку задача вычисления хроматического числа графа NP-полная.
• Жадная раскраска вершин с наибольшей степенью. На каждом шаге среди неокрашенных вершин с максимальной степенью выбирается та, которая имеет наибольшее число смежных вершин разных цветов.
• Жадная раскраска рёбер. Аналогична жадной раскраске вершин.
• Жадная раскраска рёбер максимального паросочетания. На каждом шаге среди неокрашенных рёбер ищется максимальное паросочетание и затем все его рёбра раскрашиваются одним цветом.
• Алгоритм Уоршелла поиска транзитивного замыкания. Пусть дан орграф. Вычислительно эффективный алгоритм строит последовательность орграфов таких, что предыдущий орграф — подграф следующего орграфа, а последний орграф — транзитивное замыкание исходного. Следующий орграф получается из предыдущего добавлением дуги при её отсутствии, если есть путь длиной 2 из начальной вершины новой дуги к конечной.
• Алгоритм Кана топологической сортировки. Это простой алгоритм построения линейного расширения частично упорядоченного множества. Идея состоит в том, чтобы всегда выбирать минимальный элемент на каждом шаге алгоритма.
• Вычисление самого раннего времени события. На каждой итерации во взвешенном ациклическом орграфе крупного сложного проекта выбирается вершина, в которую не входит ни одна дуга, и значения самого раннего времени её последующих вершин соответственно обновляются. Затем эта вершина удаляется из орграфа, и начинается следующая итерация. Алгоритм вычисляет самые длинные пути от начальной вершины до каждой другой.
• Вычисление самого позднего времени события. Аналогичен расчету самого раннего времени события, но выполняется после вычисление самого раннего времени события в обратном направлении от вершины орграфа конца проекта, которая инициализируется самым ранним временем события.

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

Источники

• Басакер Р., Саати Т. Конечные графы и сети / Пер. с английского В. Н. Буркова, С. Е. Ловецкого, В. Б. Соколова. Под ред А. И. Теймана. М.: Наука, 1974. 366 с., ил.
• Берж К. Теория графов и её применения / Пер. с французского А. А. Зыкова. М.: Изд-во иностранной литературы, 1962. 319 с., ил.
• Виленкин Н. Я., Шибасов Л. П., Шибасова З. Ф. За страницами учебника математики. М.: Просвещение, 1996. 320 с., ил. ISBN 5-09-006575-6.
• Деза М. М., Сикирич М. Д. Геометрия химических графов: полициклы и биполициклы. М.—Ижевск: Изд-во Института компьютерных исследований, 2013. 384 с., ил. ISBN 978-5-4344-0130-2.
• Дистель Р. Теория графов / Пер. с англ. Новосибирск: Изд-во Института математики, 2002. 225 с., ил. ISBN 5-86134-101-Х.
• Евстигнеев В. А. Применение теории графов в программировании / Под ред. А. П. Ершова. М.: Наука, 1985. 352 с., ил.
• Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов / Под ред. А. П. Ершова. М.: Наука, 1990. 383 с., ил. ISBN 5-02-013992-0.
• Каменецкий И. С., Маршак Б. И., Шер Я. А. Анализ археологических источников: Возможности формализованного подхода. Изд. 2-е. М.: ИА РАН, 2013. 182 с.: ил. ISBN 978-5-94375-153-0.
• Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ. 2-е изд. : Пер. с англ. М.: Издательский дом «Вильямс», 2009. 1290 с., ил. ISBN 978-5-8459-0857-5 (рус.). ISBN 0-07-013151-1 (англ.).
• Кристофдес Н. Теория графов. Алгоритмический подход. Пер. с англ. Э. В. Вершкова и И. В. Коновальцева. Под. ред. Г. П. Гаврилова. М.: Мир, 1978. 432 с., ил.
• Курейчик В. М., Глушань В. М., Щербаков Л. И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990. 214 с., ил. ISBN 5-256-00748-3.
• Лубенцова В. С. Математические модели и методы в логистике / Под ред. В. П. Радченко. Самара: Изд-во Самарского государственного технического университета, 2008. 157 с.: ил. ISBN 978-5-7964-1140-7.
• Маджидов Т. И., Баскин И. И., Антипин И. С., Варнек А. А. Введение в хемоинформатику. Части 1—4. Казань: Изд-во Казанского университета, 2013—2016.
• Мелихов А. Н. Ориентированные графы и конечные автоматы. М.: Наука, 1971. 416 с., ил.
• Одним росчерком. Вычерчивание фигур одной непрерывной линией / Сост. Я. И. Перельман. Л.: Дом занимательной науки, 1940. С 17 рис.
• Оре О. Графы и их применение / Пер. с англ. Л. И. Головиной. Под ред. И. М. Яглома. М.: Мир, 1965. 174 с.: ил.
• Оре О. Теория графов. 2-е изд. стереотип. / Пер. с англ. И. Н. Врублевской. Под ред. Н. Н. Воробьева. М.: Наука, 1980. 336 с.: ил.
• Паниотто В. И. Структура межличностных отношений : методика и математические методы исследования. Киев: Наукова думка, 1975. 124 с., ил.
• Перельман Я. И. Живая математика. Математические рассказы и головоломки. Изд. 8, перераб. и доп. / Под ред. и с доп. В. Г. Болтянского. М.: Наука, 1967. 160 с. с илл.
• Теория графов и сетей при моделировании процессов УВД : Учеб. пособие / Сост. В. А. Карнаухов. Ульяновск: УВАУ ГА(И), 2009. 63 с.
• Фляйшнер Г. Эйлеровы графы и смежные вопросы / Пер. с англ. В. А. Евстигнеева, А. В. Косточки и Л. С. Мельникова. Под ред. Л. С. Мельникова. М.: Мир, 2002. 335 с.: ил. ISBN 5-03-003115-4 (рус.). ISBN 0-444-88395-9 (англ.). [Fleischner H. Eulerian Graphs and Related Topics. P. 1, V. 1. Amsterdam: North-Holland, 1990.]
• Фомин Г. П. Математические методы и модели в коммерческой деятельности: учебник. 3-е изд., перераб. и доп. М.: Финансы и статистика; ИНФРА-М, 2009. 637 с.: ил. ISBN 978-5-279-03353-9 (Финансы и статистика). ISBN 978-5-16-003660-1 (ИНФРА-М).
• Харари Фрэнк. Теория графов / Пер. с англ. В. П. Козырева. Под ред. Г. П. Гаврилова. Изд-е 2-е. М.: Едиториал УРСС, 2003. 296 с.: ил. ISBN 5-354-00301-6.
• Харари Ф., Палмер Э. Перечисление графов / Пер. с англ. Г. П. Гаврилова. М.: Мир, 1977. 324 с.: ил.
• Химические приложения топологии и теории графов / Пер. с англ. Под ред. Р. Кинга. М.: Мир, 1987. 560 с.: ил.
• Шалыто А. А. Алгоритмизация и программирование задач логического управления. СПб.: СПбГУ ИТМО, 1998. 56 с., ил.
• Яблонский Г. С., Быков В. И., Горбань А. Н. Кинетические модели каталитических реакций. Новосибирск: Наука, 1983. 253 с.: ил. ISBN 5-354-00301-6.
• Chemical graph theory : introduction and fundamentals / edited by D. Bonchev and D. Rouvray. New York: Abacus Press, 1991. ISBN 0-85626-454-7.
• Gross J. L., Yellen J. Graph theory and its applications. Second edition. Boca Raton–London–New York: Chapman & Hall/CRC, 2006.
• Gross J. L., Yellen J. Handbook of graph theory. CRC Press, 2004. ISBN 978-1-58488-090-5. P. 35.
• Dénes König. Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe. Leipzig: Akademische Verlagsgesellschaft M. B. H., 1936.
• Dénes König. Theory of finite and infinite graphs. Boston: Birkhäuser, 1990.
• Nils J. Nilsson. Artificial intelligence and a new synthesis. San Francisco, California: Morgan Kaufmann Publishes, Inc., 1998. 535 p. ISBN 1-55860-467-7 (cloth). ISBN 1-55860-535-5 (paper).