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

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

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

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

Определения [ править ]

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

График [ править ]

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

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

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

В ребре вершины и называются концами ребра. Ребро называется присоединиться и и быть инцидент на и . Вершина может существовать в графе и не принадлежать ребру. Множественные ребра , недопустимые в соответствии с приведенным выше определением, - это два или более ребра, которые соединяют одни и те же две вершины.${\ Displaystyle \ {х, у \}}$${\ 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\to \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}}$, функция инцидентности, отображающая каждое ребро в неупорядоченную пару вершин (то есть ребро связано с двумя различными вершинами).

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

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

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

В неориентированном простом графе порядка n максимальная степень каждой вершины равна n - 1, а максимальный размер графа равен n ( n - 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 E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}}$, А набор из ребер (также называемые ориентированных ребер , направленные ссылки , направленные линии , стрелка или дуги ) , которые упорядоченные пары вершин (то есть, ребро связанно с двумя различными вершинами).

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

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

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

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

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

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

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

Приложения [ править ]

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

Информатика [ править ]

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

Лингвистика [ править ]

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

Физика и химия [ править ]

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

Социальные науки [ править ]

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

Биология [ править ]

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

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

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

Математика [ править ]

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

Другие темы [ править ]

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

История [ править ]

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

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

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

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

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

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

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

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

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

Рисование графика [ править ]

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

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

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

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

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

Структуры данных на основе теории графов [ править ]

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

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

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

Проблемы [ править ]

Перечисление [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Раскраска графика [ править ]

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

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

Подчинение и объединение [ править ]

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

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

Проблемы с маршрутом [ править ]

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

Сетевой поток [ править ]

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

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

Проблемы с видимостью [ править ]

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

Покрытие проблем [ править ]

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

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

Проблемы разложения [ править ]

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

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

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

Классы графов [ править ]

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

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

См. Также [ править ]

Заметки [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

Викискладе есть медиафайлы по теории графов .

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

Интернет-учебники [ править ]

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