Теория графов

Область дискретной математики

Рисунок графа с 6 вершинами и 7 ребрами .

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

Определения

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

График

Граф с тремя вершинами и тремя ребрами.

В одном ограниченном, но очень общем смысле этого термина ^{[1] [2]} граф — это упорядоченная пара, включающая : ${\displaystyle G=(V,E)}$

• ${\displaystyle V}$, набор вершин (также называемых узлами или точками ) ;
• ${\displaystyle E\subseteq \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}}$, набор ребер (также называемых связями или линиями ), которые представляют собой неупорядоченные пары вершин (то есть ребро связано с двумя различными вершинами).

Во избежание двусмысленности этот тип объекта можно назвать просто неориентированным простым графом .

В ребре вершины и называются конечными точками ребра. Говорят, что ребро соединяется с и инцидентно и с . Вершина может существовать в графе и не принадлежать ребру. Согласно этому определению, множественные ребра , в которых два или более ребер соединяют одни и те же вершины, не допускаются. ${\displaystyle \{x,y\}}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$

Пример простого неориентированного графа с 3 вершинами, 3 ребрами и 4 петлями.

Примеры нахождения степени вершин.

В еще одном общем смысле термина, допускающем множественные ребра, ^{[3] [4]} граф представляет собой упорядоченную тройку, включающую : ${\displaystyle G=(V,E,\phi )}$

• ${\displaystyle V}$, набор вершин (также называемых узлами или точками ) ;
• ${\displaystyle E}$, набор рёбер ( также называемых связями или линиями );
• ${\displaystyle \phi :E\to \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}}$, функция инцидентности , отображающая каждое ребро в неупорядоченную пару вершин (то есть ребро связано с двумя различными вершинами).

Во избежание двусмысленности этот тип объекта можно назвать именно неориентированным мультиграфом .

Петля — это ребро, соединяющее вершину с собой. Графы, как определено в двух определениях выше, не могут иметь петель, поскольку петля, соединяющая вершину с собой, является ребром (для неориентированного простого графа) или инцидентна (для неориентированного мультиграфа), который не находится в . Чтобы разрешить петли, определения должны быть расширены. Для неориентированных простых графов определение должно быть изменено на . Для неориентированных мультиграфов определение должно быть изменено на . Чтобы избежать неоднозначности, эти типы объектов можно называть неориентированными простыми графами, разрешающими петли , и неориентированными мультиграфами, разрешающими петли (иногда также неориентированными псевдографами ), соответственно. ${\displaystyle x}$ ${\displaystyle \{x,x\}=\{x\}}$ ${\displaystyle \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}}$ ${\displaystyle E}$ ${\displaystyle E\subseteq \{\{x,y\}\mid x,y\in V\}}$ ${\displaystyle \phi }$ ${\displaystyle \phi :E\to \{\{x,y\}\mid x,y\in V\}}$

${\displaystyle V}$и обычно считаются конечными, и многие из известных результатов не верны (или довольно отличны) для бесконечных графов, поскольку многие аргументы не работают в бесконечном случае . Более того, часто предполагается, что непустое множество, но допускается пустое множество. Порядок графа равен , его число вершин. Размер графа равен , его число ребер. Степень или валентность вершины — это число ребер, инцидентных ей, где цикл учитывается дважды. Степень графа — это максимальная из степеней его вершин. ${\displaystyle E}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle |V|}$ ${\displaystyle |E|}$

В неориентированном простом графе порядка n максимальная степень каждой вершины равна n − 1 , а максимальный размер графа равен ⁠н ( н − 1)/2⁠ .

Ребра неориентированного простого графа, допускающего петли, индуцируют симметричное однородное отношение на вершинах , которое называется отношением смежности . В частности, для каждого ребра его конечные точки и называются смежными друг с другом, что обозначается . ${\displaystyle G}$ ${\displaystyle \sim }$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle (x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\sim y}$

Направленный граф

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

Ориентированный граф или орграф — это граф, в котором ребра имеют ориентацию.

В одном ограниченном, но очень распространенном смысле этого термина ^[5] ориентированный граф представляет собой упорядоченную пару, состоящую из: ${\displaystyle G=(V,E)}$

• ${\displaystyle V}$, набор вершин (также называемых узлами или точками ) ;
• ${\displaystyle E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}}$, набор ребер (также называемых направленными ребрами , направленными связями , направленными линиями , стрелками или дугами ), которые представляют собой упорядоченные пары вершин (то есть ребро связано с двумя различными вершинами).

Чтобы избежать двусмысленности, этот тип объекта можно назвать именно направленным простым графом . В теории множеств и теории графов обозначает множество из n - кортежей элементов , то есть упорядоченные последовательности элементов, которые не обязательно различны. ${\displaystyle V^{n}}$ ${\displaystyle V,}$ ${\displaystyle n}$

В ребре, направленном от к , вершины и называются конечными точками ребра, хвостом ребра и головой ребра. Говорят, что ребро соединяет и и инцидентно и . Вершина может существовать в графе и не принадлежать ребру. Ребро называется инвертированным ребром . Множественные ребра , недопустимые в соответствии с приведенным выше определением, — это два или более ребер с одинаковым хвостом и головой . ${\displaystyle (x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle (y,x)}$ ${\displaystyle (x,y)}$

В еще одном общем смысле термина, допускающем множественные ребра, ^[5] ориентированный граф представляет собой упорядоченную тройку, включающую: ${\displaystyle G=(V,E,\phi )}$

• ${\displaystyle V}$, набор вершин (также называемых узлами или точками ) ;
• ${\displaystyle E}$, набор ребер (также называемых направленными ребрами , направленными связями , направленными линиями , стрелками или дугами );
• ${\displaystyle \phi :E\to \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}}$, функция инцидентности , отображающая каждое ребро в упорядоченную пару вершин (то есть ребро связано с двумя различными вершинами).

Во избежание двусмысленности этот тип объекта можно назвать именно направленным мультиграфом .

Петля — это ребро, соединяющее вершину с собой. Направленные графы, как определено в двух определениях выше, не могут иметь петель, поскольку петля, соединяющая вершину с собой, является ребром (для направленного простого графа) или инцидентна (для направленного мультиграфа), которое не находится в . Поэтому для разрешения петель определения должны быть расширены. Для направленных простых графов определение должно быть изменено на . Для направленных мультиграфов определение должно быть изменено на . Чтобы избежать неоднозначности, эти типы объектов можно называть именно направленным простым графом, разрешающим петли , и направленным мультиграфом, разрешающим петли (или колчаном ) соответственно. ${\displaystyle x}$ ${\displaystyle (x,x)}$ ${\displaystyle \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}}$ ${\displaystyle E}$ ${\displaystyle E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\right\}}$ ${\displaystyle \phi }$ ${\displaystyle \phi :E\to \left\{(x,y)\mid (x,y)\in V^{2}\right\}}$

Ребра ориентированного простого графа, допускающего петли, являются однородным отношением ~ на вершинах , которое называется отношением смежности . В частности, для каждого ребра его конечные точки и называются смежными друг с другом, что обозначается ~ . ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle (x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$

Приложения

Сетевой график, сформированный редакторами Википедии (ребра), вносящими вклад в различные языковые версии Википедии (вершины) в течение одного месяца летом 2013 года. ^[6]

Графы могут использоваться для моделирования многих типов отношений и процессов в физических, биологических, ^{[7] [8]} социальных и информационных системах. ^[9] Многие практические проблемы могут быть представлены графами. Подчеркивая их применение к системам реального мира, термин « сеть» иногда определяется как граф, в котором атрибуты (например, имена) связаны с вершинами и ребрами, а субъект, который выражает и понимает системы реального мира как сеть, называется сетевой наукой .

Информатика

В компьютерной науке « причинно-следственные » и «непричинно-следственные» связанные структуры представляют собой графы, которые используются для представления сетей связи, организации данных, вычислительных устройств, потока вычислений и т. д. Например, структура ссылок веб -сайта может быть представлена ​​направленным графом, в котором вершины представляют веб-страницы, а направленные ребра представляют ссылки с одной страницы на другую. Подобный подход может быть применен к проблемам в социальных сетях, ^[10] путешествиях, биологии, проектировании компьютерных чипов, картировании прогрессирования нейродегенеративных заболеваний ^{[11] [12]} и многих других областях. Поэтому разработка алгоритмов для обработки графов представляет большой интерес в компьютерной науке. Преобразование графов часто формализуется и представляется системами переписывания графов . Дополнением к системам преобразования графов , фокусирующимся на манипуляции графами в памяти на основе правил, являются графовые базы данных , ориентированные на транзакционно -безопасное, постоянное хранение и запрос структурированных графом данных .

Лингвистика

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

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

Теория графов также используется для изучения молекул в химии и физике . В физике конденсированного состояния трехмерная структура сложных моделируемых атомных структур может быть изучена количественно путем сбора статистики по свойствам теории графов, связанным с топологией атомов. Кроме того, « графы Фейнмана и правила расчета суммируют квантовую теорию поля в форме, тесно связанной с экспериментальными числами, которые нужно понять». ^[13] В химии граф создает естественную модель для молекулы, где вершины представляют атомы , а ребра — связи . Этот подход особенно используется в компьютерной обработке молекулярных структур, начиная от химических редакторов и заканчивая поиском в базах данных. В статистической физике графы могут представлять локальные связи между взаимодействующими частями системы, а также динамику физического процесса в таких системах. Аналогично, в вычислительной нейронауке графы могут использоваться для представления функциональных связей между областями мозга, которые взаимодействуют, вызывая различные когнитивные процессы, где вершины представляют различные области мозга, а ребра — связи между этими областями. Теория графов играет важную роль в электрическом моделировании электрических сетей, здесь веса связаны с сопротивлением сегментов проводов для получения электрических свойств сетевых структур. ^[14] Графы также используются для представления микромасштабных каналов пористых сред , в которых вершины представляют поры, а ребра представляют меньшие каналы, соединяющие поры. Теория химических графов использует молекулярный граф как средство для моделирования молекул. Графы и сети являются прекрасными моделями для изучения и понимания фазовых переходов и критических явлений. Удаление узлов или ребер приводит к критическому переходу, где сеть распадается на небольшие кластеры, что изучается как фазовый переход. Этот распад изучается с помощью теории перколяции . ^[15]

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

Теория графов в социологии: Социограмма Морено (1953). ^[16]

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

Биология

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

Графы также широко используются в молекулярной биологии и геномике для моделирования и анализа наборов данных со сложными взаимосвязями. Например, графические методы часто используются для «кластеризации» клеток в типы клеток при анализе транскриптома отдельных клеток . Другое применение — моделирование генов или белков в пути и изучение взаимосвязей между ними, таких как метаболические пути и сети регуляции генов. ^[18] Эволюционные деревья, экологические сети и иерархическая кластеризация шаблонов экспрессии генов также представлены в виде графовых структур.

Теория графов также используется в коннектомике ; ^[19] нервную систему можно рассматривать как граф, где узлами являются нейроны, а ребрами — связи между ними.

Математика

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

Другие темы

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

История

Проблема Кенигсбергского моста

Статья Леонарда Эйлера о семи мостах Кёнигсберга , опубликованная в 1736 году, считается первой статьей в истории теории графов. ^[20] Эта статья, как и статья Вандермонда о задаче о рыцаре , продолжила анализ situs, начатый Лейбницем . Формула Эйлера, связывающая число ребер, вершин и граней выпуклого многогранника, была изучена и обобщена Коши ^[21] и Люилье ^[22] и представляет собой начало раздела математики, известного как топология .

Более чем через столетие после статьи Эйлера о мостах Кенигсберга и в то время, когда Листинг вводил концепцию топологии, Кэли был приведён интересом к конкретным аналитическим формам, возникающим из дифференциального исчисления, для изучения определённого класса графов, деревьев . ^[23] Это исследование имело множество последствий для теоретической химии . Методы, которые он использовал, в основном касались перечисления графов с определёнными свойствами. Затем из результатов Кэли и фундаментальных результатов, опубликованных Полиа между 1935 и 1937 годами, возникла перечислительная теория графов. Они были обобщены Де Брейном в 1959 году. Кэли связал свои результаты о деревьях с современными исследованиями химического состава. ^[24] Слияние идей из математики с идеями из химии положило начало тому, что стало частью стандартной терминологии теории графов.

В частности, термин «граф» был введен Сильвестром в статье, опубликованной в 1878 году в журнале Nature , где он проводит аналогию между «квантовыми инвариантами» и «ковариантами» алгебры и молекулярных диаграмм: ^[25]

«[…] Таким образом, каждый инвариант и ковариант становится выразимым с помощью графика , в точности идентичного диаграмме Кекуле или хемикографу. […] Я даю правило для геометрического умножения графов, т. е. для построения графа как произведения инвариантов или ковариантов, отдельные графики которых даны. […]» (курсив как в оригинале).

Первый учебник по теории графов был написан Денесом Кёнигом и опубликован в 1936 году. ^[26] Другая книга Фрэнка Харари , опубликованная в 1969 году, «во всем мире считалась окончательным учебником по этому предмету», ^[27] и позволила математикам, химикам, инженерам-электрикам и социальным ученым общаться друг с другом. Харари пожертвовал все гонорары на финансирование премии Полиа . ^[28]

Одной из самых известных и стимулирующих проблем в теории графов является проблема четырех красок : «Верно ли, что любая карта, нарисованная на плоскости, может иметь свои области, раскрашенные четырьмя цветами, таким образом, что любые две области, имеющие общую границу, имеют разные цвета?» Эта проблема была впервые поставлена ​​Фрэнсисом Гатри в 1852 году, и ее первое письменное упоминание содержится в письме Де Моргана, адресованном Гамильтону в том же году. Было предложено много неверных доказательств, включая доказательства Кэли, Кемпе и других. Изучение и обобщение этой проблемы Тейтом , Хивудом , Рамсеем и Хадвигером привело к изучению раскрасок графов, вложенных в поверхности с произвольным родом . Переформулировка Тейта породила новый класс проблем, проблемы факторизации , в частности, изученные Петерсеном и Кёнигом . Работы Рамсея по раскраскам и, в частности, результаты, полученные Тураном в 1941 году, были у истоков другого раздела теории графов, экстремальной теории графов .

Задача о четырёх красках оставалась нерешённой более столетия. В 1969 году Генрих Хейш опубликовал метод решения задачи с использованием компьютеров. ^[29] Компьютерное доказательство, созданное в 1976 году Кеннетом Аппелем и Вольфгангом Хакеном , в основном использует понятие «разрядки», разработанное Хейшем. ^{[30] [31]} Доказательство включало проверку свойств 1936 конфигураций с помощью компьютера и не было полностью принято в то время из-за своей сложности. Более простое доказательство, учитывающее только 633 конфигурации, было дано двадцать лет спустя Робертсоном , Сеймуром , Сандерсом и Томасом . ^[32]

Автономное развитие топологии с 1860 по 1930 год оплодотворило теорию графов через работы Джордана , Куратовского и Уитни . Другим важным фактором совместного развития теории графов и топологии стало использование методов современной алгебры. Первый пример такого использования можно найти в работе физика Густава Кирхгофа , который в 1845 году опубликовал свои законы Кирхгофа для расчета напряжения и тока в электрических цепях .

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

Представление

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

Визуально: Графическое изображение

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

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

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

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

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

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

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

Структуры списков включают список ребер , массив пар вершин и список смежности , в котором отдельно перечислены соседи каждой вершины: Подобно списку ребер, каждая вершина имеет список вершин, с которыми она смежна.

Матричные структуры включают матрицу инцидентности , матрицу из нулей и единиц, строки которой представляют вершины, а столбцы — ребра, и матрицу смежности , в которой и строки, и столбцы индексируются вершинами. В обоих случаях 1 указывает на два смежных объекта, а 0 — на два несмежных объекта. Матрица степеней указывает на степень вершин. Матрица Лапласа — это модифицированная форма матрицы смежности, которая включает информацию о степенях вершин и полезна в некоторых вычислениях, таких как теорема Кирхгофа о количестве остовных деревьев графа. Матрица расстояний , как и матрица смежности, имеет и строки, и столбцы, индексированные вершинами, но вместо того, чтобы содержать 0 или 1 в каждой ячейке, она содержит длину кратчайшего пути между двумя вершинами.

Проблемы

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

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

Подграфы, индуцированные подграфы и миноры

Распространенной проблемой, называемой проблемой изоморфизма подграфов , является нахождение фиксированного графа как подграфа в заданном графе. Одна из причин, по которой стоит интересоваться таким вопросом, заключается в том, что многие свойства графа являются наследственными для подграфов, что означает, что граф обладает свойством тогда и только тогда, когда все подграфы также обладают им. К сожалению, нахождение максимальных подграфов определенного вида часто является NP-полной задачей . Например:

• Нахождение наибольшего полного подграфа называется задачей клики (NP-полной).

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

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

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

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

• Граф называется планарным, если он не содержит в качестве минора ни полный двудольный граф K _3,3 (см. задачу о трёх коттеджах ), ни полный граф K ₅ .

Похожая проблема, проблема subdivision containment, заключается в нахождении фиксированного графа как subdivision данного графа. Subdivision или гомеоморфизм графа — это любой граф, полученный путем subdivision некоторых (или ни одного) ребер. Subdivision containment связан со свойствами графа, такими как планарность . Например, теорема Куратовского гласит:

• Граф является планарным , если он не содержит в качестве подразделения ни полный двудольный граф K _3,3 , ни полный граф K ₅ .

Еще одной проблемой в сдерживании подразделения является гипотеза Кельманса–Сеймура :

• Каждый 5-вершинно-связный граф, не являющийся планарным, содержит подразделение 5-вершинного полного графа K ₅ .

Другой класс проблем связан с тем, в какой степени различные виды и обобщения графов определяются их подграфами с удаленными точками . Например:

• Гипотеза реконструкции

Раскраска графа

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

• Теорема о четырех красках
• Теорема о сильном совершенном графе
• Гипотеза Эрдеша – Фабера – Ловаса
• Гипотеза о полной раскраске , также называемая гипотезой Бехзада (нерешенная )
• Гипотеза о раскраске списков (нерешенная)
• Гипотеза Хадвигера (теория графов) (нерешенная)

Подчинение и объединение

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

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

Проблемы с маршрутом

• Задача о гамильтоновом пути
• Минимальное остовное дерево
• Задача проверки маршрута (также называемая «задача китайского почтальона»)
• Семь мостов Кёнигсберга
• Задача о кратчайшем пути
• дерево Штейнера
• Задача о трех коттеджах
• Задача коммивояжера (NP-трудная)

Сетевой поток

Существует множество проблем, возникающих, в частности, в приложениях, связанных с различными представлениями о потоках в сетях , например:

• Теорема о максимальном потоке и минимальном разрезе

Проблемы с видимостью

• Проблема музейного охранника

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

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

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

Проблемы разложения

Разложение, определяемое как разбиение множества ребер графа (с необходимым количеством вершин, сопровождающих ребра каждой части разбиения), имеет широкий спектр вопросов. Часто проблема состоит в разложении графа на подграфы, изоморфные фиксированному графу; например, разложение полного графа на гамильтоновы циклы. Другие проблемы указывают семейство графов, на которые должен быть разложен заданный граф, например, семейство циклов, или разложение полного графа K _n на n − 1 указанных деревьев, имеющих, соответственно, 1, 2, 3, ..., n − 1 ребро.

Некоторые конкретные проблемы декомпозиции, которые были изучены, включают:

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

Графические классы

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

• Перечисление членов класса
• Характеристика класса с точки зрения запрещенных подструктур
• Установление отношений между классами (например, подразумевает ли одно свойство графов другое)
• Поиск эффективных алгоритмов для определения принадлежности к классу
• Поиск представлений для членов класса

Смотрите также

• Галерея именованных графиков
• Глоссарий теории графов
• Список тем по теории графов
• Список нерешенных проблем теории графов
• Публикации по теории графов
• Графический алгоритм
• Теоретики графов

Подрайоны

• Алгебраическая теория графов
• Геометрическая теория графов
• Теория экстремальных графов
• Теория вероятностных графов
• Топологическая теория графов
• Графическое изображение

Примечания

1. Бендер и Уильямсон 2010, стр. 148.
2. См., например, Иянага и Кавада, 69 J , с. 234 или Биггс, с. 4.
3. Бендер и Уильямсон 2010, стр. 149.
4. См., например, Грэм и др., стр. 5.
5. Bender & Williamson 2010, стр. 161.
6. Хейл, Скотт А. (2014). «Многоязычие и редактирование Википедии». Труды конференции ACM 2014 года по веб-науке . С. 99–108. arXiv : 1312.0976 . Bibcode :2013arXiv1312.0976H. doi :10.1145/2615569.2615684. ISBN 9781450326223. S2CID  14027025.
7. Mashaghi, A.; et al. (2004). «Исследование сети белкового комплекса». European Physical Journal B. 41 ( 1): 113–121. arXiv : cond-mat/0304207 . Bibcode : 2004EPJB...41..113M. doi : 10.1140/epjb/e2004-00301-0. S2CID  9233932.
8. Шах, Прейя; Ашурван, Ариан; Михаил, Фади; Пайнс, Адам; Кини, Лохит; Охсель, Келли; Дас, Сандхицу Р.; Стайн, Джоэл М.; Шинохара, Рассел Т. (2019-07-01). «Характеристика роли структурного коннектома в динамике приступов». Мозг . 142 (7): 1955–1972. doi :10.1093/brain/awz125. ISSN  0006-8950. PMC 6598625 . PMID  31099821. 
9. Адали, Тулай; Ортега, Антонио (май 2018 г.). «Применение теории графов [сканирование выпуска]» . Труды IEEE . 106 (5): 784–786. doi :10.1109/JPROC.2018.2820300. ISSN  0018-9219.
10. Гранджин, Мартин (2016). «Анализ социальной сети Twitter: картирование сообщества цифровых гуманитарных наук» (PDF) . Cogent Arts & Humanities . 3 (1): 1171458. doi : 10.1080/23311983.2016.1171458 . S2CID  114999767.
11. Веккьо, Ф (2017).Архитектура «Маленького мира» в связях мозга и объеме гиппокампа при болезни Альцгеймера: исследование с помощью теории графов на основе данных ЭЭГ». Визуализация мозга и поведение . 11 (2): 473–485. doi :10.1007/s11682-016-9528-3. PMID  26960946. S2CID  3987492.
12. Vecchio, F (2013). «Связь мозговых сетей, оцененная с использованием теории графов при лобно-височной деменции». Неврология . 81 (2): 134–143. doi :10.1212/WNL.0b013e31829a33f8. PMID  23719145. S2CID  28334693.
13. Бьёркен, Дж. Д.; Дрелл, С. Д. (1965). Релятивистские квантовые поля . Нью-Йорк: McGraw-Hill. стр. viii.
14. Кумар, Анкуш; Кулкарни, ГУ (2016-01-04). «Оценка прозрачных электродов на основе проводящей сети с геометрических соображений». Журнал прикладной физики . 119 (1): 015102. Bibcode : 2016JAP...119a5102K. doi : 10.1063/1.4939280. ISSN  0021-8979.
15. Ньюман, Марк (2010). Сети: Введение (PDF) . Oxford University Press. Архивировано из оригинала (PDF) 2020-07-28 . Получено 2019-10-30 .
16. Гранжан, Мартин (2015). «Анализ и визуализация социальных сетей: пересмотр социограмм Морено». Переработанная сеть, строго основанная на Морено (1934), Кто выживет .
17. Розен, Кеннет Х. (2011-06-14). Дискретная математика и ее приложения (7-е изд.). Нью-Йорк: McGraw-Hill. ISBN 978-0-07-338309-5.
18. Келли, С.; Блэк, Майкл (2020-07-09). "graphsim: пакет R для моделирования данных экспрессии генов из графовых структур биологических путей" (PDF) . Журнал программного обеспечения с открытым исходным кодом . 5 (51). Открытый журнал: 2161. Bibcode :2020JOSS....5.2161K. bioRxiv 10.1101/2020.03.02.972471 . doi : 10.21105/joss.02161 . ISSN  2475-9066. S2CID  214722561. 
19. Шах, Прейя; Ашурван, Ариан; Михаил, Фади; Пайнс, Адам; Кини, Лохит; Охсель, Келли; Дас, Сандхицу Р.; Стайн, Джоэл М.; Шинохара, Рассел Т. (2019-07-01). «Характеристика роли структурного коннектома в динамике приступов». Мозг . 142 (7): 1955–1972. doi :10.1093/brain/awz125. ISSN  0006-8950. PMC 6598625 . PMID  31099821. 
20. Биггс, Н.; Ллойд, Э.; Уилсон, Р. (1986), Теория графов, 1736-1936 , Oxford University Press
21. Коши, AL (1813), «Recherche sur les Polyèdres - Premier Mémoire», Journal de l'École Polytechnique , 9 (Cahier 16): 66–86.
22. L'Huillier, S.-A.-J. (1812–1813), «Mémoire sur la polyèdrométrie», Annales de Mathématiques , 3 : 169–189.
23. Кэли, А. (1857), «О теории аналитических форм, называемых деревьями» , Philosophical Magazine , Серия IV, 13 (85): 172–176, doi :10.1017/CBO9780511703690.046, ISBN 9780511703690
24. Кэли, А. (1875), «Ueber die Analytischen Figen, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen», Berichte der Deutschen Chemischen Gesellschaft , 8 (2): 1056–1059, doi : 10.1002 /cber.18750080252.
25. Сильвестр, Джеймс Джозеф (1878). «Химия и алгебра». Nature . 17 (432): 284. Bibcode : 1878Natur..17..284S. doi : 10.1038/017284a0 .
26. Tutte, WT (2001), Теория графов, Cambridge University Press, стр. 30, ISBN 978-0-521-79489-3, получено 2016-03-14
27. Гарднер, Мартин (1992), Фрактальная музыка, гиперкарты и многое другое…Математические развлечения из Scientific American , WH Freeman and Company, стр. 203
28. Общество промышленной и прикладной математики (2002), "Премия Джорджа Полиа", Взгляд назад, Взгляд вперед: История SIAM (PDF) , стр. 26, архивировано из оригинала (PDF) 2016-03-05 , извлечено 2016-03-14
29. Генрих Хеш: Untersuchungen zum Vierfarbenproblem. Мангейм: Библиографический институт, 1969.
30. Аппель, К.; Хакен, В. (1977), «Каждая плоская карта может быть раскрашена четырьмя красками. Часть I. Разрядка» (PDF) , Illinois J. Math. , 21 (3): 429–490, doi : 10.1215/ijm/1256049011 .
31. Аппель, К.; Хакен, В. (1977), «Каждая плоская карта может быть раскрашена четырьмя красками. Часть II. Приводимость», Illinois J. Math. , 21 (3): 491–567, doi : 10.1215/ijm/1256049012 .
32. Робертсон, Н.; Сандерс, Д.; Сеймур, П.; Томас, Р. (1997), «Теорема о четырех красках», Журнал комбинаторной теории, Серия B , 70 : 2–44, doi : 10.1006/jctb.1997.1750 .
33. Кепнер, Джереми; Гилберт, Джон (2011). Графовые алгоритмы на языке линейной алгебры. SIAM. стр. 1171458. ISBN 978-0-898719-90-1.

Ссылки

• Бендер, Эдвард А.; Уильямсон, С. Гилл (2010). Списки, решения и графики. С введением в вероятность.
• Берже, Клод (1958). Теория графиков и их приложений . Париж: Дюнод.Английское издание, Wiley 1961; Methuen & Co, Нью-Йорк 1962; русское издание, Москва 1961; испанское издание, Мексика 1962; румынское издание, Бухарест 1969; китайское издание, Шанхай 1963; второе издание первого английского издания 1962 года, Дувр, Нью-Йорк 2001.
• Биггс, Н.; Ллойд, Э.; Уилсон, Р. (1986). Теория графов, 1736–1936 . Oxford University Press.
• Бонди, JA; Мурти, USR (2008). Теория графов . Springer. ISBN 978-1-84628-969-9.
• Bollobás, Béla; Riordan, OM (2003). Математические результаты по безмасштабным случайным графам в "Handbook of Graphs and Networks" (S. Bornholdt и HG Schuster (ред.)) (1-е изд.). Weinheim: Wiley VCH.
• Chartrand, Gary (1985). Введение в теорию графов . Довер. ISBN 0-486-24775-9.
• Део, Нарсингх (1974). Теория графов с приложениями к инженерии и информатике (PDF) . Энглвуд, Нью-Джерси: Prentice-Hall. ISBN 0-13-363473-6. Архивировано (PDF) из оригинала 2019-05-17.
• Гиббонс, Алан (1985). Алгоритмическая теория графов . Cambridge University Press .
• Голумбик, Мартин (1980). Алгоритмическая теория графов и совершенные графы . Academic Press .
• Харари, Фрэнк (1969). Теория графов . Рединг, Массачусетс: Addison-Wesley.
• Харари, Фрэнк; Палмер, Эдгар М. (1973). Графическое перечисление . Нью-Йорк, Нью-Йорк: Academic Press.
• Махадев, НВР; Пелед, Ури Н. (1995). Пороговые графики и смежные темы . Северная Голландия .
• Ньюман, Марк (2010). Сети: Введение . Oxford University Press.
• Кепнер, Джереми; Гилберт, Джон (2011). Графовые алгоритмы на языке линейной алгебры. Филадельфия, Пенсильвания: SIAM. ISBN 978-0-898719-90-1.

Внешние ссылки

• «Теория графов», Энциклопедия математики , EMS Press , 2001 [1994]
• Учебник по теории графов Архивировано 16.01.2012 на Wayback Machine
• База данных небольших связанных графов с возможностью поиска
• Галерея изображений: графики на Wayback Machine (архивировано 6 февраля 2006 г.)
• Краткий аннотированный список ресурсов по теории графов для исследователей
• rocs — IDE для теории графов
• Социальная жизнь маршрутизаторов — нетехническая статья, в которой обсуждаются графы людей и компьютеров.
• Программное обеспечение для теории графов — инструменты для преподавания и изучения теории графов
• Онлайн-книги и библиотечные ресурсы в вашей библиотеке и в других библиотеках по теории графов
• Список графовых алгоритмов, архивированных 13 июля 2019 г. на Wayback Machine со ссылками и реализациями графовых библиотек.

Онлайн-учебники

• Фазовые переходы в задачах комбинаторной оптимизации, раздел 3: Введение в графы (2006) Хартманна и Вайгта
• Орграфы: Теория, алгоритмы и приложения 2007 г. Йорген Банг-Йенсен и Грегори Гутин
• Теория графов, Райнхард Дистель