Теория графов - Graph theory

А Рисование графа.

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

Обратитесь к глоссарий теории графов для основных определений в теории графов.

Определения

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

График

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

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

• ${displaystyle V}$, а набор из вершины (также называемый узлы или же точки);
• ${displaystyle Esubseteq {{x, y} mid x, yin V; {extrm {and}}; xeq y}}$, а набор из края (также называемый ссылки или же линии), которые неупорядоченные пары вершин (т. е. ребро связано с двумя различными вершинами).

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

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

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

• ${displaystyle V}$, а набор из вершины (также называемый узлы или же точки);
• ${displaystyle E}$, а набор из края (также называемый ссылки или же линии);
• ${displaystyle phi: E o {{x, y} mid x, yin V; {extrm {and}}; xeq y}}$, функция инцидентности отображение каждого края на неупорядоченная пара вершин (то есть ребро связано с двумя различными вершинами).

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

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

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

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

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

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

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

А ориентированный граф или же диграф это граф, в котором ребра ориентированы.

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

• ${displaystyle V}$, а набор из вершины (также называемый узлы или же точки);
• ${displaystyle Esubseteq left {(x, y) mid (x, y) in V ^ {2}; {extrm {and}}; xeq yight}}$, а набор из края (также называемый направленные края, направленные ссылки, направленные линии, стрелки или же дуги) которые заказанные пары вершин (т. е. ребро связано с двумя различными вершинами).

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

В краю ${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 o left {(x, y) mid (x, y) in V ^ {2}; {extrm {and}}; xeq yight}}$, функция инцидентности отображение каждого края на упорядоченная пара вершин (то есть ребро связано с двумя различными вершинами).

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

А петля это ребро, соединяющее вершину с самой собой. Направленные графы, как определено в двух определениях выше, не могут иметь циклов, потому что цикл, соединяющий вершину ${displaystyle x}$ самому себе является ребром (для ориентированного простого графа) или инцидентно (для ориентированного мультиграфа) ${displaystyle (x, x)}$ которого нет в ${displaystyle left {(x, y) mid (x, y) в V ^ {2}; {extrm {и}}; xeq yight}}$. Поэтому, чтобы разрешить циклы, определения должны быть расширены. Для ориентированных простых графов определение ${displaystyle E}$ следует изменить на ${displaystyle Esubseteq left {(x, y) mid (x, y) in V ^ {2} ight}}$. Для направленных мультиграфов определение ${displaystyle phi}$ следует изменить на ${displaystyle phi: E o left {(x, y) mid (x, y) in V ^ {2} ight}}$. Во избежание двусмысленности эти типы объектов можно назвать именно ориентированный простой граф, разрешающий петли и направленные мультиграфические разрешающие петли (или колчан ) соответственно.

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

Приложения

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

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

Информатика

В Информатика, графы используются для представления сетей связи, организации данных, вычислительных устройств, потока вычислений и т. д. Например, структура ссылок интернет сайт может быть представлен ориентированным графом, в котором вершины представляют веб-страницы, а ориентированные ребра представляют ссылки с одной страницы на другую. Аналогичный подход можно применить к проблемам в социальных сетях,^[9] путешествия, биология, дизайн компьютерных микросхем, картографирование прогрессирования нейродегенеративных заболеваний,^[10][11] и многие другие области. Развитие алгоритмы поэтому обработка графов представляет большой интерес в информатике. В преобразование графиков часто формализуется и представлена системы перезаписи графов. В дополнение к преобразование графа системы, ориентированные на основанное на правилах манипулирование графами в памяти, графовые базы данных направлена ​​на сделка -безопасный, настойчивый хранение и запрос данные с графической структурой.

Лингвистика

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

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

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

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

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

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

Биология

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

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

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

Математика

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

Другие темы

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

История

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

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

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

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

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

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

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

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

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

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

Рисование графика

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

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

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

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

Также изучаются рисунки на поверхностях, отличных от плоскости.

Теоретико-графические структуры данных

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

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

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

Проблемы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

Рекомендации

• Бендер, Эдвард А .; Уильямсон, С. Гилл (2010). Списки, решения и графики. Знакомство с вероятностью.
• Клод, Клод (1958). Теория графических и других приложений. Пэрис: Данод. Английское издание, Wiley 1961; Метуэн и Ко, Нью-Йорк, 1962; Русский, Москва 1961; Испанский, Мексика, 1962 год; Румынский, Бухарест, 1969; Китайский, Шанхай, 1963 год; Второе издание первого английского издания 1962 г., Довер, Нью-Йорк, 2001 г.
• Biggs, N .; Lloyd, E .; Уилсон, Р. (1986). Теория графов, 1736–1936 гг.. Издательство Оксфордского университета.
• Bondy, J. A .; Мурти, США (2008). Теория графов. Springer. ISBN  978-1-84628-969-9.
• Боллобаш, Бела; Риордан, О. М. (2003). Математические результаты по безмасштабным случайным графам в "Handbook of Graphs and Networks" (С. Борнхольдт и Х. Г. Шустер (ред.)) (1-е изд.). Вайнхайм: Wiley VCH.
• Чартран, Гэри (1985). Вводная теория графов. Дувр. ISBN  0-486-24775-9.
• Део, Нарсинг (1974). Теория графов с приложениями в инженерии и информатике (PDF). Энглвуд, Нью-Джерси: Прентис-Холл. ISBN  0-13-363473-6.
• Гиббонс, Алан (1985). Алгоритмическая теория графов. Издательство Кембриджского университета.
• Реувен Коэн, Шломо Хавлин (2010). Сложные сети: структура, надежность и функции. Издательство Кембриджского университета. ISBN  9781139489270.
• Голумбик, Мартин (1980). Алгоритмическая теория графов и совершенные графы. Академическая пресса.
• Харари, Фрэнк (1969). Теория графов. Ридинг, Массачусетс: Эддисон-Уэсли.
• Харари, Фрэнк; Палмер, Эдгар М. (1973). Графическое перечисление. Нью-Йорк, Нью-Йорк: Academic Press.
• Махадев, Н. В. Р .; Пелед, Ури Н. (1995). Графики пороговых значений и связанные темы. Северная Голландия.
• Ньюман, Марк (2010). Сети: введение. Издательство Оксфордского университета.
• Кепнер, Джереми; Гилберт, Джон (2011). Графовые алгоритмы на языке линейной алгебры. Филадельфия, Пенсильвания: SIAM. ISBN  978-0-898719-90-1.

внешняя ссылка

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

Интернет-учебники

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