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

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

Определения

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

График

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

Информатика

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

Лингвистика

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

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

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

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

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

Биология

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

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

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

Математика

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

Другие темы

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проблемы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Алгоритмы

Подрайоны

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

Обобщения

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

Примечания

^ Бендер и Уильямсон 2010 , с. 148.
^ См., например, Иянага и Кавада, 69 J , с. 234 или Биггс, с. 4.
^ Бендер и Уильямсон 2010 , с. 149.
^ См., например, Graham et al., p. 5.
^ Jump up to: ^а ^б Бендер и Уильямсон 2010 , с. 161.
^ Хейл, Скотт А. (2014). «Многоязычие и редактирование Википедии». Материалы конференции ACM 2014 года по веб-науке . стр. 99–108. arXiv : 1312.0976 . Бибкод : 2013arXiv1312.0976H . дои : 10.1145/2615569.2615684 . ISBN 9781450326223 . S2CID 14027025 .
^ Машаги, А.; и др. (2004). «Исследование сети белкового комплекса». Европейский физический журнал Б. 41 (1): 113–121. arXiv : cond-mat/0304207 . Бибкод : 2004EPJB...41..113M . дои : 10.1140/epjb/e2004-00301-0 . S2CID 9233932 .
^ Шах, Прейя; Ашурван, Ариан; Михаил, Фади; Пайнс, Адам; Кини, Лохит; Охсель, Келли; Дас, Сандхицу Р; Штейн, Джоэл М; Шинохара, Рассел Т. (01 июля 2019 г.). «Характеристика роли структурного коннектома в динамике приступов» . Мозг 142 (7): 1955–1972. дои : 10.1093/brain/awz125 . ISSN 0006-8950 . ПМК 6598625 . ПМИД 31099821 .
^ Адали, Тулай; Ортега, Антонио (май 2018 г.). «Приложения теории графов [сканирование проблемы]» . Труды IEEE . 106 (5): 784–786. дои : 10.1109/JPROC.2018.2820300 . ISSN 0018-9219 .
^ Гранжан, Мартин (2016). «Анализ социальной сети Twitter: составление карты сообщества цифровых гуманитарных наук» (PDF) . Cogent Искусства и Гуманитарные науки . 3 (1): 1171458. doi : 10.1080/23311983.2016.1171458 . S2CID 114999767 .
^ Веккьо, Ф (2017). « Архитектура «маленького мира» в связях мозга и объеме гиппокампа при болезни Альцгеймера: исследование с помощью теории графов на основе данных ЭЭГ». Мозговые изображения и поведение . 11 (2): 473–485. дои : 10.1007/s11682-016-9528-3 . ПМИД 26960946 . S2CID 3987492 .
^ Веккьо, Ф (2013). «Связность мозговых сетей оценивается с использованием теории графов при лобно-височной деменции». Неврология . 81 (2): 134–143. дои : 10.1212/WNL.0b013e31829a33f8 . ПМИД 23719145 . S2CID 28334693 .
^ Бьоркен, доктор юридических наук; Дрелл, С.Д. (1965). Релятивистские квантовые поля . Нью-Йорк: МакГроу-Хилл. п. viii.
^ Кумар, Анкуш; Кулкарни, ГУ (04 января 2016 г.). «Оценка прозрачных электродов на основе проводящей сети с точки зрения геометрических соображений». Журнал прикладной физики . 119 (1): 015102. Бибкод : 2016JAP...119a5102K . дои : 10.1063/1.4939280 . ISSN 0021-8979 .
^ Ньюман, Марк (2010). Сети: Введение (PDF) . Издательство Оксфордского университета. Архивировано из оригинала (PDF) 28 июля 2020 г. Проверено 30 октября 2019 г.
^ Гранжан, Мартин (2015). «Анализ и визуализация социальных сетей: новый взгляд на социограммы Морено» . Переработанная сеть строго по роману Морено (1934) « Кто выживет» .
^ Розен, Кеннет Х. (14 июня 2011 г.). Дискретная математика и ее приложения (7-е изд.). Нью-Йорк: МакГроу-Хилл. ISBN 978-0-07-338309-5 .
^ Келли, С.; Блэк, Майкл (09 июля 2020 г.). «graphsim: пакет R для моделирования данных экспрессии генов из графовых структур биологических путей» (PDF) . Журнал программного обеспечения с открытым исходным кодом . 5 (51). Открытый журнал: 2161. Бибкод : 2020JOSS....5.2161K . bioRxiv 10.1101/2020.03.02.972471 . дои : 10.21105/joss.02161 . ISSN 2475-9066 . S2CID 214722561 .
^ Шах, Прейя; Ашурван, Ариан; Михаил, Фади; Пайнс, Адам; Кини, Лохит; Охсель, Келли; Дас, Сандхицу Р; Штейн, Джоэл М; Шинохара, Рассел Т. (01 июля 2019 г.). «Характеристика роли структурного коннектома в динамике приступов» . Мозг 142 (7): 1955–1972. дои : 10.1093/brain/awz125 . ISSN 0006-8950 . ПМК 6598625 . ПМИД 31099821 .
^ Биггс, Н.; Ллойд, Э.; Уилсон, Р. (1986), Теория графов, 1736–1936 , Oxford University Press
^ Коши, AL (1813), «Исследование многогранников - первые мемуары», Journal de l'École Polytechnique , 9 (Cahier 16): 66–86.
^ Л'Юлье, С.-А.-Ж. (1812–1813), «Мемуары о полиэдрометрии», Annales de Mathématiques , 3 : 169–189.
^ Кэли, А. (1857), «К теории аналитических форм, называемых деревьями» , Philosophical Magazine , Series IV, 13 (85): 172–176, doi : 10.1017/CBO9780511703690.046 , ISBN 9780511703690
^ Кэли, А. (1875), «Об аналитических фигурах, которые в математике называются деревьями, и их применении к теории химических соединений» , отчеты Немецкого химического общества , 8 (2): 1056–1059, doi : 10.1002/ cber.18750080252 .
^ Сильвестр, Джеймс Джозеф (1878). «Химия и алгебра» . Природа . 17 (432): 284. Бибкод : 1878Natur..17..284S . дои : 10.1038/017284a0 .
^ Тутт, WT (2001), Теория графов , издательство Кембриджского университета, стр. 30, ISBN 978-0-521-79489-3 , получено 14 марта 2016 г.
^ Гарднер, Мартин (1992), Фрактальная музыка, гиперкарты и многое другое… Математические развлечения от Scientific American , WH Freeman and Company, стр. 203
^ Общество промышленной и прикладной математики (2002), «Премия Джорджа Пойа», Оглядываясь назад, глядя вперед: история SIAM (PDF) , стр. 26, заархивировано из оригинала (PDF) 5 марта 2016 г. , получено 14 марта 2016 г.
^ Генрих Хеш: Исследования проблемы четырех цветов. Мангейм: Библиографический институт, 1969.
^ Аппель, К.; Хакен, В. (1977), «Каждая плоская карта раскрашивается в четыре цвета. Часть I. Разрядка» (PDF) , Illinois J. Math. , 21 (3): 429–490, doi : 10.1215/ijm/1256049011 .
^ Аппель, К.; Хакен, В. (1977), «Каждая плоская карта раскрашивается в четыре цвета. Часть II. Сводимость», Illinois J. Math. , 21 (3): 491–567, doi : 10.1215/ijm/1256049012 .
^ Робертсон, Н.; Сандерс, Д.; Сеймур, П.; Томас, Р. (1997), «Теорема о четырех цветах», Журнал комбинаторной теории, серия B , 70 : 2–44, doi : 10.1006/jctb.1997.1750 .
^ Кепнер, Джереми; Гилберт, Джон (2011). Графовые алгоритмы на языке линейной алгебры . СИАМ. п. 1171458. ISBN 978-0-898719-90-1 .

Ссылки

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

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

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

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

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

[FOOTNOTEBenderWilliamson2010148-1] Бендер и Уильямсон 2010 , с. 148.

[2] См., например, Иянага и Кавада, 69 J , с. 234 или Биггс, с. 4.

[FOOTNOTEBenderWilliamson2010149-3] Бендер и Уильямсон 2010 , с. 149.

[4] См., например, Graham et al., p. 5.

[FOOTNOTEBenderWilliamson2010161-5] Jump up to: ^а ^б Бендер и Уильямсон 2010 , с. 161.

[6] Хейл, Скотт А. (2014). «Многоязычие и редактирование Википедии». Материалы конференции ACM 2014 года по веб-науке . стр. 99–108. arXiv : 1312.0976 . Бибкод : 2013arXiv1312.0976H . дои : 10.1145/2615569.2615684 . ISBN 9781450326223 . S2CID 14027025 .

[7] Машаги, А.; и др. (2004). «Исследование сети белкового комплекса». Европейский физический журнал Б. 41 (1): 113–121. arXiv : cond-mat/0304207 . Бибкод : 2004EPJB...41..113M . дои : 10.1140/epjb/e2004-00301-0 . S2CID 9233932 .

[8] Шах, Прейя; Ашурван, Ариан; Михаил, Фади; Пайнс, Адам; Кини, Лохит; Охсель, Келли; Дас, Сандхицу Р; Штейн, Джоэл М; Шинохара, Рассел Т. (01 июля 2019 г.). «Характеристика роли структурного коннектома в динамике приступов» . Мозг 142 (7): 1955–1972. дои : 10.1093/brain/awz125 . ISSN 0006-8950 . ПМК 6598625 . ПМИД 31099821 .

[9] Адали, Тулай; Ортега, Антонио (май 2018 г.). «Приложения теории графов [сканирование проблемы]» . Труды IEEE . 106 (5): 784–786. дои : 10.1109/JPROC.2018.2820300 . ISSN 0018-9219 .

[10] Гранжан, Мартин (2016). «Анализ социальной сети Twitter: составление карты сообщества цифровых гуманитарных наук» (PDF) . Cogent Искусства и Гуманитарные науки . 3 (1): 1171458. doi : 10.1080/23311983.2016.1171458 . S2CID 114999767 .

[11] Веккьо, Ф (2017). « Архитектура «маленького мира» в связях мозга и объеме гиппокампа при болезни Альцгеймера: исследование с помощью теории графов на основе данных ЭЭГ». Мозговые изображения и поведение . 11 (2): 473–485. дои : 10.1007/s11682-016-9528-3 . ПМИД 26960946 . S2CID 3987492 .

[12] Веккьо, Ф (2013). «Связность мозговых сетей оценивается с использованием теории графов при лобно-височной деменции». Неврология . 81 (2): 134–143. дои : 10.1212/WNL.0b013e31829a33f8 . ПМИД 23719145 . S2CID 28334693 .

[13] Бьоркен, доктор юридических наук; Дрелл, С.Д. (1965). Релятивистские квантовые поля . Нью-Йорк: МакГроу-Хилл. п. viii.

[14] Кумар, Анкуш; Кулкарни, ГУ (04 января 2016 г.). «Оценка прозрачных электродов на основе проводящей сети с точки зрения геометрических соображений». Журнал прикладной физики . 119 (1): 015102. Бибкод : 2016JAP...119a5102K . дои : 10.1063/1.4939280 . ISSN 0021-8979 .

[15] Ньюман, Марк (2010). Сети: Введение (PDF) . Издательство Оксфордского университета. Архивировано из оригинала (PDF) 28 июля 2020 г. Проверено 30 октября 2019 г.

[16] Гранжан, Мартин (2015). «Анализ и визуализация социальных сетей: новый взгляд на социограммы Морено» . Переработанная сеть строго по роману Морено (1934) « Кто выживет» .

[17] Розен, Кеннет Х. (14 июня 2011 г.). Дискретная математика и ее приложения (7-е изд.). Нью-Йорк: МакГроу-Хилл. ISBN 978-0-07-338309-5 .

[18] Келли, С.; Блэк, Майкл (09 июля 2020 г.). «graphsim: пакет R для моделирования данных экспрессии генов из графовых структур биологических путей» (PDF) . Журнал программного обеспечения с открытым исходным кодом . 5 (51). Открытый журнал: 2161. Бибкод : 2020JOSS....5.2161K . bioRxiv 10.1101/2020.03.02.972471 . дои : 10.21105/joss.02161 . ISSN 2475-9066 . S2CID 214722561 .

[19] Шах, Прейя; Ашурван, Ариан; Михаил, Фади; Пайнс, Адам; Кини, Лохит; Охсель, Келли; Дас, Сандхицу Р; Штейн, Джоэл М; Шинохара, Рассел Т. (01 июля 2019 г.). «Характеристика роли структурного коннектома в динамике приступов» . Мозг 142 (7): 1955–1972. дои : 10.1093/brain/awz125 . ISSN 0006-8950 . ПМК 6598625 . ПМИД 31099821 .

[Biggs-20] Биггс, Н.; Ллойд, Э.; Уилсон, Р. (1986), Теория графов, 1736–1936 , Oxford University Press

[Cauchy-21] Коши, AL (1813), «Исследование многогранников - первые мемуары», Journal de l'École Polytechnique , 9 (Cahier 16): 66–86.

[Lhuillier-22] Л'Юлье, С.-А.-Ж. (1812–1813), «Мемуары о полиэдрометрии», Annales de Mathématiques , 3 : 169–189.

[23] Кэли, А. (1857), «К теории аналитических форм, называемых деревьями» , Philosophical Magazine , Series IV, 13 (85): 172–176, doi : 10.1017/CBO9780511703690.046 , ISBN 9780511703690

[Cayley1-24] Кэли, А. (1875), «Об аналитических фигурах, которые в математике называются деревьями, и их применении к теории химических соединений» , отчеты Немецкого химического общества , 8 (2): 1056–1059, doi : 10.1002/ cber.18750080252 .

[Sylvester-25] Сильвестр, Джеймс Джозеф (1878). «Химия и алгебра» . Природа . 17 (432): 284. Бибкод : 1878Natur..17..284S . дои : 10.1038/017284a0 .

[26] Тутт, WT (2001), Теория графов , издательство Кембриджского университета, стр. 30, ISBN 978-0-521-79489-3 , получено 14 марта 2016 г.

[27] Гарднер, Мартин (1992), Фрактальная музыка, гиперкарты и многое другое… Математические развлечения от Scientific American , WH Freeman and Company, стр. 203

[28] Общество промышленной и прикладной математики (2002), «Премия Джорджа Пойа», Оглядываясь назад, глядя вперед: история SIAM (PDF) , стр. 26, заархивировано из оригинала (PDF) 5 марта 2016 г. , получено 14 марта 2016 г.

[29] Генрих Хеш: Исследования проблемы четырех цветов. Мангейм: Библиографический институт, 1969.

[AA1-30] Аппель, К.; Хакен, В. (1977), «Каждая плоская карта раскрашивается в четыре цвета. Часть I. Разрядка» (PDF) , Illinois J. Math. , 21 (3): 429–490, doi : 10.1215/ijm/1256049011 .

[AA2-31] Аппель, К.; Хакен, В. (1977), «Каждая плоская карта раскрашивается в четыре цвета. Часть II. Сводимость», Illinois J. Math. , 21 (3): 491–567, doi : 10.1215/ijm/1256049012 .

[RSST-32] Робертсон, Н.; Сандерс, Д.; Сеймур, П.; Томас, Р. (1997), «Теорема о четырех цветах», Журнал комбинаторной теории, серия B , 70 : 2–44, doi : 10.1006/jctb.1997.1750 .

[33] Кепнер, Джереми; Гилберт, Джон (2011). Графовые алгоритмы на языке линейной алгебры . СИАМ. п. 1171458. ISBN 978-0-898719-90-1 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]

v т и Основные математики области
History Timeline Future Lists Glossary
Foundations	Category theory Information theory Mathematical logic Philosophy of mathematics Set theory Type theory
Algebra	Abstract Commutative Elementary Group theory Linear Multilinear Universal Homological
Analysis	Calculus Real analysis Complex analysis Hypercomplex analysis Differential equations Functional analysis Harmonic analysis Measure theory
Discrete	Combinatorics Graph theory Order theory
Geometry	Algebraic Analytic Arithmetic Differential Discrete Euclidean Finite
Number theory	Arithmetic Algebraic number theory Analytic number theory Diophantine geometry
Topology	General Algebraic Differential Geometric Homotopy theory
Applied	Engineering mathematics Mathematical biology Mathematical chemistry Mathematical economics Mathematical finance Mathematical physics Mathematical psychology Mathematical sociology Mathematical statistics Probability Statistics Systems science Control theory Game theory Operations research
Computational	Computer science Theory of computation Computational complexity theory Numerical analysis Optimization Computer algebra
Related topics	Mathematicians lists Informal mathematics Films about mathematicians Recreational mathematics Mathematics and art Mathematics education
Mathematics portal Category Commons WikiProject

v т и Информатика
Note: This template roughly follows the 2012 ACM Computing Classification System.
Hardware	Printed circuit board Peripheral Integrated circuit Very Large Scale Integration Systems on Chip (SoCs) Energy consumption (Green computing) Electronic design automation Hardware acceleration Processor Size / Form
Computer systems organization	Computer architecture Computational complexity Dependability Embedded system Real-time computing
Networks	Network architecture Network protocol Network components Network scheduler Network performance evaluation Network service
Software organization	Interpreter Middleware Virtual machine Operating system Software quality
Software notations and tools	Programming paradigm Programming language Compiler Domain-specific language Modeling language Software framework Integrated development environment Software configuration management Software library Software repository
Software development	Control variable Software development process Requirements analysis Software design Software construction Software deployment Software engineering Software maintenance Programming team Open-source model
Theory of computation	Model of computation Formal language Automata theory Computability theory Computational complexity theory Logic Semantics
Algorithms	Algorithm design Analysis of algorithms Algorithmic efficiency Randomized algorithm Computational geometry
Mathematics of computing	Discrete mathematics Probability Statistics Mathematical software Information theory Mathematical analysis Numerical analysis Theoretical computer science
Information systems	Database management system Information storage systems Enterprise information system Social information systems Geographic information system Decision support system Process control system Multimedia information system Data mining Digital library Computing platform Digital marketing World Wide Web Information retrieval
Security	Cryptography Formal methods Security hacker Security services Intrusion detection system Hardware security Network security Information security Application security
Human–computer interaction	Interaction design Social computing Ubiquitous computing Visualization Accessibility
Concurrency	Concurrent computing Parallel computing Distributed computing Multithreading Multiprocessing
Artificial intelligence	Natural language processing Knowledge representation and reasoning Computer vision Automated planning and scheduling Search methodology Control method Philosophy of artificial intelligence Distributed artificial intelligence
Machine learning	Supervised learning Unsupervised learning Reinforcement learning Multi-task learning Cross-validation
Graphics	Animation Rendering Photograph manipulation Graphics processing unit Mixed reality Virtual reality Image compression Solid modeling
Applied computing	Quantum Computing E-commerce Enterprise software Computational mathematics Computational physics Computational chemistry Computational biology Computational social science Computational engineering Differentiable computing Computational healthcare Digital art Electronic publishing Cyberwarfare Electronic voting Video games Word processing Operations research Educational technology Document management
Category Outline Glossaries

v т и Программное обеспечение для анализа графиков
Free	Cytoscape Graphviz Gephi igraph Microsoft Automatic Graph Layout NetworkX Tulip
Proprietary	Maple Mathematica