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

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

Определения

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

График

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

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

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

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

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

В еще одном общем смысле термина, допускающего несколько ребер, граф представляет собой упорядоченную тройку, состоящую из: ${\ Displaystyle G = (В, Е, \ фи)}$

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

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

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

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

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

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

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

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

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

В одном ограниченном, но очень распространенном смысле этого термина ориентированный граф — это упорядоченная пара, состоящая из: ${\ Displaystyle G = (В, Е)}$

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

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

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

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

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

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

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

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

Приложения

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

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

Информатика

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

Лингвистика

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

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

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

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

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

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

Биология

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

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

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

Математика

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

Другие темы

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проблемы

перечисление

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритмы

Подрайоны

Смежные области математики

Обобщения

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

Примечания

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

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

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

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

Languages

In other projects