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

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

Рисунок графика .

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

Определения

Дополнительная информация: Глоссарий теории графов.

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

График

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

В одном ограниченном, но очень распространенном смысле этого термина: граф — это упорядоченная пара $G=(V,E)$ включающий:

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

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

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

В более общем смысле термина, допускающего наличие нескольких ребер, граф — это упорядоченная тройка $G=(V,E,\phi )$ включающий:

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

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

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

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

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

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

Ориентированный граф

Основная статья: Ориентированный граф

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

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

В одном ограниченном, но очень распространенном смысле этого термина: — ориентированный граф это упорядоченная пара $G=(V,E)$ включающий:

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

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

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

В более общем смысле термина, допускающего наличие нескольких ребер, — ориентированный граф это упорядоченная тройка $G=(V,E,\phi )$ включающий:

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

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

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

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

Приложения

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

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

Информатика

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

Лингвистика

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

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

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

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

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

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

Биология

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

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

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

Математика

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

Другие темы

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

История

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

Статья Леонарда Эйлера о семи мостах Кенигсберга , опубликованная в 1736 году, считается первой статьей в истории теории графов. Эта статья, как и статья, написанная Вандермондом по проблеме коня , продолжила анализ ситуации, начатый Лейбницем . Формула Эйлера, связывающая количество ребер, вершин и граней выпуклого многогранника, была изучена и обобщена Коши . и Л'Юилье , и представляет собой начало раздела математики, известного как топология .

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

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

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

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

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

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

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

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

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

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

Визуализация: рисование графика

Основная статья: Рисование графика

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

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

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

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

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

Таблица: Структуры данных графа

Основная статья: График (абстрактный тип данных)

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

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

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

Проблемы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основная статья: Раскраска графа

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

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

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

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

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

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

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

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

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

• Теорема о максимальном расходе и минимальном сокращении

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

• Проблема с охраной музея

Освещение проблем

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

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

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

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

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

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

Классы графов

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

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

См. также

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

Связанные темы

• Алгебраическая теория графов
• График цитирования
• Концептуальный график
• Структура данных
• Структура данных с непересекающимся множеством
• Двухфазная эволюция
• Существенный граф
• Экзистенциальный граф
• Графовая алгебра
• Автоморфизм графа
• Раскраска графа
• База данных графов
• Структура данных графа
• Рисование графика
• Уравнение графика
• Переписывание графа
• Проблема сэндвича с графом
• Свойство графа
• Граф пересечений
• Рыцарский тур
• Логический график
• Петля
• Теория сетей
• Нулевой график
• Проблемы с движением гальки
• Теория перколяции
• Идеальный график
• Квантовый граф
• Случайные регулярные графики
• Семантические сети
• Спектральная теория графов
• Сильно регулярные графы
• Симметричные графы
• Транзитивная редукция
• Древовидная структура данных

Алгоритмы

• Алгоритм Беллмана – Форда
• Алгоритм Блуберри
• Поиск в ширину
• Поиск в глубину
• Алгоритм Дейкстры
• Алгоритм Эдмондса – Карпа
• Алгоритм Флойда – Уоршалла
• Алгоритм Форда – Фулкерсона
• Алгоритм Хопкрофта – Карпа
• Венгерский алгоритм
• Алгоритм Косараджу
• Алгоритм Краскала
• Алгоритм ближайшего соседа
• Сетевой симплексный алгоритм
• Алгоритмы проверки планарности
• Алгоритм Прима
• Алгоритм максимального потока push-relabel
• Алгоритм сильно связанных компонентов Тарьяна
• Топологическая сортировка

Подрайоны

• Алгебраическая теория графов
• Геометрическая теория графов
• Экстремальная теория графов
• Вероятностная теория графов
• Топологическая теория графов

Связанные области математики

• Комбинаторика
• Теория групп
• Теория узлов
• Теория Рэмси

Обобщения

• Гиперграф
• Абстрактный симплициальный комплекс

Выдающиеся теоретики графов

• Алон, осторожно
• Берже, Клод
• Буллобас, Бела
• Бонди, Адриан Джон
• Брайтуэлл, Грэм
• Чудновская Мария,
• Чанг, Фан
• Дирак, Габриэль Эндрю
• Дейкстра, Эдсгер В.
• Эрдос, Пол
• Эйлер, Леонард
• Фаудри, Ральф
• Флейшнер, Герберт
• Голумбик, Мартин
• Грэм, Рональд
• Ура, Фрэнк
• Хивуд, Перси Джон
• Больной, Антон
• Кениг, Денес
• Ловаш, Ласло
• Мурти, USR
• Он не спас, Ярослав
• Реньи, Альфред
• Рингель, Герхард
• Робертсон, Нил
• Сеймур, Пол
• Судаков, Бенни
• Семереди, Эндре
• Томас, Робин
• Томассен, Карстен
• Туран, Павел
• Тутте, WT
• Уитни, Хасслер

Ссылки

• Бендер, Эдвард А.; Уильямсон, С. Гилл (2010). Списки, решения и графики. С введением в вероятность .
• Берже, Клод (1958). Теория графиков и их приложений . Париж: Дюнод. Английское издание, Wiley, 1961 г.; Метуэн и компания, Нью-Йорк, 1962 г.; Россия, Москва 1961; Испанский, Мексика, 1962 год; Румынский, Бухарест, 1969 г.; Китай, Шанхай, 1963 год; Второе издание первого английского издания 1962 года, Дувр, Нью-Йорк, 2001 год.
• Биггс, Н.; Ллойд, Э.; Уилсон, Р. (1986). Теория графов, 1736–1936 гг . Издательство Оксфордского университета.
• Бонди, Дж.А.; Мурти, USR (2008). Теория графов . Спрингер. ISBN  978-1-84628-969-9 .
• Боллобас, Бела; Риордан, ОМ (2003). Математические результаты о безмасштабных случайных графах в «Справочнике по графам и сетям» (С. Борнхольдт и Х.Г. Шустер (редакторы)) (1-е изд.). Вайнхайм: Wiley VCH.
• Чартранд, Гэри (1985). Введение в теорию графов . Дувр. ISBN  0-486-24775-9 .
• Део, Нарсингх (1974). Теория графов с приложениями к инженерии и информатике (PDF) . Энглвуд, Нью-Джерси: Прентис-Холл. ISBN  0-13-363473-6 . Архивировано (PDF) из оригинала 17 мая 2019 г.
• Гиббонс, Алан (1985). Алгоритмическая теория графов . Издательство Кембриджского университета .
• Голумбик, Мартин (1980). Алгоритмическая теория графов и совершенные графы . Академическая пресса .
• Харари, Фрэнк (1969). Теория графов . Ридинг, Массачусетс: Аддисон-Уэсли.
• Харари, Фрэнк; Палмер, Эдгар М. (1973). Графическое перечисление . Нью-Йорк, Нью-Йорк: Академическая пресса.
• Махадев, NVR; Пелед, Ури Н. (1995). Пороговые графики и связанные темы . Северная Голландия .
• Ньюман, Марк (2010). Сети: Введение . Издательство Оксфордского университета.
• Кепнер, Джереми; Гилберт, Джон (2011). Графовые алгоритмы на языке линейной алгебры . Филадельфия, Пенсильвания: СИАМ. ISBN  978-0-898719-90-1 .

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

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

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

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