Введение

Наборы вершин, соединенных ребрами. Область дискретной математики.

В математике теория графов — это изучение графов, которые являются математическими структурами, используемыми для моделирования попарных отношений между объектами. Граф в данном контексте состоит из вершин (также называемых узлами или точками), соединенных ребрами (также называемыми дугами, связями или линиями). Различают неориентированные графы, где ребра связывают две вершины симметрично, и ориентированные графы, где ребра связывают две вершины асимметрично. Графы являются одним из основных объектов изучения в дискретной математике.

Определения

Определения в теории графов могут различаться. Ниже представлены некоторые из наиболее фундаментальных способов определения графов и связанных с ними математических структур.

Приложения

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

Информатика

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

Лингвистика

Методы теории графов в различных формах оказались особенно полезными в лингвистике, поскольку естественный язык часто хорошо поддается дискретному представлению. Традиционно синтаксис и композиционная семантика опираются на структуры, основанные на деревьях, выразительная сила которых заключается в принципе композиционности, моделируемом в виде иерархического графа. Более современные подходы, такие как грамматика с управляемой головной фразой, моделируют синтаксис естественного языка с использованием типизированных структур признаков, которые представляют собой направленные ациклические графы. В лексической семантике, особенно в контексте компьютерной обработки, моделирование значения слова упрощается, когда слово рассматривается в связи с другими словами; поэтому семантические сети играют важную роль в вычислительной лингвистике. Кроме того, другие методы, используемые в фонологии (например, оптимальностьная теория, применяющая решетчатые графы) и морфологии (например, морфология конечных автоматов, использующая конечные автоматы преобразования), широко распространены при анализе языка как графа. Действительно, полезность этой области математики для лингвистики привела к созданию таких организаций, как TextGraphs, а также различных "сетевых" проектов, таких как WordNet, VerbNet и другие.

Физика и химия

Теория графов также используется для изучения молекул в химии и физике. В физике конденсированного состояния трехмерная структура сложных смоделированных атомных структур может быть количественно исследована путем сбора статистики о графовых свойствах, связанных с топологией атомов. Кроме того, "диаграммы Фейнмана и правила вычислений суммируют квантовую теорию поля в форме, тесно связанной с экспериментальными данными, которые необходимо понять". В химии граф представляет собой естественную модель молекулы, где вершины соответствуют атомам, а ребра – связям. Этот подход особенно широко используется в компьютерной обработке молекулярных структур, от химических редакторов до поиска в базах данных. В статистической физике графы могут представлять локальные связи между взаимодействующими частями системы, а также динамику физического процесса в таких системах. Аналогично, в вычислительной нейронауке графы могут использоваться для представления функциональных связей между областями мозга, которые взаимодействуют, порождая различные когнитивные процессы, где вершины представляют различные области мозга, а ребра – связи между ними. Теория графов играет важную роль в электрическом моделировании электрических цепей, где веса соотносятся с сопротивлением участков проводов для определения электрических свойств сетевых структур. Графы также используются для представления микроскопических каналов пористых сред, в которых вершины представляют поры, а ребра – меньшие каналы, соединяющие поры. Теория химических графов использует молекулярный граф как средство моделирования молекул. Графы и сети являются отличными моделями для изучения и понимания фазовых переходов и критических явлений. Удаление узлов или ребер приводит к критическому переходу, при котором сеть распадается на небольшие кластеры, что изучается как фазовый переход. Этот распад исследуется с помощью теории перколяции.

Социальные науки

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

Биология

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

Математика

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

Другие темы

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

Представительство

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

Визуально: рисунок графика

Графы обычно визуализируются путем изображения точки или круга для каждой вершины и проведения линии между двумя вершинами, если они соединены ребром. Если граф ориентированный, направление указывается стрелкой. Если граф взвешенный, вес добавляется к ребру, отображаемому стрелкой. Визуальное представление графа не следует путать с самим графом (абстрактной, не визуальной структурой), поскольку существует множество способов построения визуализации графа. Важно лишь то, какие вершины связаны с какими другими и каким количеством ребер, а не конкретная компоновка. На практике часто бывает сложно определить, представляют ли два изображения один и тот же граф. В зависимости от области применения некоторые схемы могут быть более подходящими и понятными, чем другие. Пионерская работа У. Т. Тютте оказала значительное влияние на область визуализации графов. Среди прочих достижений, он ввел использование методов линейной алгебры для получения визуализаций графов. Визуализация графов также охватывает задачи, связанные с числом пересечений и его различными обобщениями. Число пересечений графа – это минимальное количество пересечений ребер, которое должна содержать визуализация графа на плоскости. Для планарного графа число пересечений по определению равно нулю. Также изучаются визуализации на поверхностях, отличных от плоскости. Существуют и другие методы визуализации графа, не основанные на вершинах и ребрах, включая упаковки окружностей, графы пересечений и другие визуализации матрицы смежности.

Таблица: Графические структуры данных

Табличное представление хорошо подходит для вычислительных приложений. Существуют различные способы хранения графов в компьютерной системе. Используемая структура данных зависит как от структуры графа, так и от алгоритма, используемого для работы с графом. Теоретически можно различать структуры списков и матрицы, но в конкретных приложениях лучшая структура часто является комбинацией обоих. Структуры списков часто предпочтительнее для разреженных графов, поскольку они имеют меньшие требования к памяти. Матричные структуры, с другой стороны, обеспечивают более быстрый доступ для некоторых приложений, но могут потреблять огромное количество памяти. Реализация эффективных структур разреженных матриц для современных параллельных компьютерных архитектур является предметом текущих исследований. Структуры списков включают в себя список ребер, массив пар вершин и список смежности, в котором отдельно перечисляются соседи каждой вершины: аналогично списку ребер, каждая вершина имеет список смежных с ней вершин. Матричные структуры включают матрицу инцидентности, матрицу из нулей и единиц, строки которой представляют вершины, а столбцы – ребра, и матрицу смежности, в которой как строки, так и столбцы индексируются вершинами. В обоих случаях единица указывает на два смежных объекта, а ноль – на два несмежных объекта. Матрица степеней указывает степень вершин. Матрица Лапласа – это модифицированная форма матрицы смежности, которая включает информацию о степенях вершин и полезна в некоторых вычислениях, таких как теорема Кирхгофа о количестве остовных деревьев графа. Матрица расстояний, как и матрица смежности, имеет строки и столбцы, индексированные вершинами, но вместо нуля или единицы в каждой ячейке содержит длину кратчайшего пути между двумя вершинами.

Перечисление

Существует обширная литература, посвященная графическому перечислению: задаче подсчета графов, удовлетворяющих заданным условиям. Часть этих работ представлена в книге Харари и Палмера (1973).

Присоединение и объединение

Теории моделирования ограничений рассматривают семейства ориентированных графов, связанных частичным порядком. В этих приложениях графы упорядочены по степени детализации: более ограниченные графы – более конкретные и, следовательно, содержащие больше информации – подчиняются более общим. Операции над графами включают определение направления отношения подчинения между двумя графами, если оно существует, и вычисление унификации графов. Унификация двух графов-аргументов определяется как наиболее общий граф (или его вычисление), который совместим с (то есть содержит всю информацию из) входных данных, если такой граф существует; существуют эффективные алгоритмы унификации. Для строго композиционных систем ограничений унификация графов является достаточной функцией проверки выполнимости и комбинации. Хорошо известные области применения включают автоматическое доказательство теорем и моделирование развертывания лингвистической структуры.

Проблемы покрытия

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