Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:
- как и геометрия, обладает наглядностью;
- как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
- не имеет громоздкого математического аппарата ;
- имеет выраженный прикладной характер.
Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.
Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.
Хроматический многочлен — многочлен, изучаемый в алгебраической теории графов, представляющий число раскрасок графа как функцию от числа цветов. Первоначально определён Джорджем Биркгофов для попытки решения на проблемы четырёх красок. Обобщен и систематически изучен Хасслером Уитни, Татт обобщил хроматический многочлен до многочлена Татта, связав его с моделью Поттса статистической физики.
В теории графов графом без клешней называется граф, который не содержит порождённых подграфов, изоморфных K1,3 (клешней).
В теории графов совершенным графом называется граф, в котором хроматическое число любого порождённого подграфа равно размеру максимальной клики этого подграфа. Благодаря строгой теореме о совершенных графах, с 2002 года известно, что совершенные графы — это то же самое, что и графы Бержа. Граф G является графом Бержа если ни G, ни его дополнение не имеет порождённых циклов нечётной длины.
Дробная раскраска — это тема молодой области теории графов, известной как теория дробных графов. Дробная раскраска является обобщением обычной раскраски. В традиционной раскраске графа каждой вершине назначается некий цвет, и смежным вершинам — тем, что связаны рёбрами, — должны быть назначены разные цвета. В дробной раскраске каждой вершине назначается набор цветов. Ограничения, накладываемые на смежные вершины, остаются в силе, так что если две вершины соединены ребром, они не должны иметь общих цветов.
В теории графов максимальным независимым множеством, максимальным устойчивым множеством, или максимальным стабильным множеством называется независимое множество, не являющееся подмножеством другого независимого множества. То есть это такое множество вершин S, что любое ребро графа имеет хотя бы одну конечную вершину, не принадлежащую S, и любая вершина не из S имеет хотя бы одну соседнюю в S. Максимальное независимое множество является также доминирующим в графе, а любое доминирующее множество, являющееся независимым, должно быть максимальным независимым, поэтому максимальные независимые множества также называют независимыми доминирующими множествами. Граф может иметь много максимальных независимых множеств в широком диапазоне размеров.
Интервальный граф — граф пересечений мультимножества интервалов на прямой. Имеет по одной вершине для каждого интервала в множестве и по ребру между каждой парой вершин, если соответствующие интервалы пересекаются.
В теории графов трапецеидальными графами называются графы пересечений трапеций, все параллельные стороны которых лежат на двух прямых. Этот класс графов содержится в классе графов косравнимости и содержат интервальные графы и графы перестановки в качестве подклассов. Граф является трапецеидальным в том и только в том случае, когда существует набор трапеций, соответствующих вершинам графа, и две вершины графа соединены ребром в том и только в том случае, когда соответствующие вершинам трапеции пересекаются. Трапецеидальные графы были введены в рассмотрение в 1988 году Даганом, Колумбиком и Пинтером. Для этих графов существуют алгоритмы со временем работы 
для раскраски графа, для поиска взвешенных независимых множеств, кликовых покрытий и максимальных взвешенных клик.
В теории графов граф сравнимости — это неориентированный граф, в котором пары элементов соединены ребром, если эти элементы сравнимы в некотором частичном порядке. Графы сравнимости также называют транзитивно-ориентируемыми графами, частично упорядочиваемыми графами и графами вложенности.Граф несравнимости — это неориентированный граф, в котором пары элементов соединяются ребром, если элементы несравнимы в некотором частичном порядке.
В теории графов число пересечений cr(G) графа G — это наименьшее число пересечений рёбер плоского рисунка графа G. Например, граф является планарным тогда и только тогда, когда его число пересечений равно нулю.
В теории графов путевая декомпозиция графа G — это, неформально, представление графа G в виде «утолщённого» пути, а путевая ширина графа G — это число, измеряющее, насколько граф G был утолщён. Более формально, путевая декомпозиция — это последовательности вершин подмножества графа G, такие, что конечные вершины каждого ребра появляются в одном из подмножеств и каждая вершина принадлежит одному из множеств, а путевая ширина на единицу меньше размера наибольшего множества в такой декомпозиции. Путевая ширина известна также как интервальная толщина, величина вершинного разделения или вершинно-поисковое число.
Неравенство числа пересечений или лемма о пересечениях даёт нижнюю грань минимального числа пересечений данного графа как функцию от числа рёбер и вершин графа. Лемма утверждает, что для графов, у которых число рёбер e достаточно велико по сравнению с числом вершин n, число пересечений по меньшей мере пропорционально e3/n2.
Струнный граф — это граф пересечений кривых на плоскости, каждая кривая при этом называется «струной». Если дан граф G, он является струнным тогда и только тогда, когда существует набор кривых (струн), нарисованных на плоскости, таких, что никакие три струны не пересекаются в одной точке и граф G изоморфен графу, вершины которого соответствуют кривым, а дуга в этом графе соответствует пересечению двух кривых.
Степень k неориентированного графа G — это другой граф, имеющий тот же самый набор вершин, и две вершины этого графа смежны, если расстояние между этими вершинами в исходном графе G не превышает k. Для указания степени графа используется терминология, аналогичная степеням чисел — G2 называется квадратом графа G, G3 называется кубом.
k-Вырожденный граф — это неориентированный граф, в котором каждый подграф имеет вершины со степенью, не превосходящей k. Вырожденность графа — это наименьшее значение k, для которого граф является k-вырожденным. Вырожденность графа отражает, насколько граф разрежен и отражает другие меры разреженности, такие как древесность графа.
Предписанная раскраска — это вид раскраски графов, в которой каждая вершина может принимать ограниченное множество допустимых цветов. Одними из первых эту раскраску изучили Визинг и Эрдёш, а также Рубин и Тейлор в 1970-х годах.
Топологический граф — представление графа на плоскости, в котором вершины графа представлены различными точками, а рёбра кривыми Жордана, соединяющими соответствующие пары точек. Точки, представляющие вершины графа, и дуги, представляющие рёбра, называются вершинами и рёбрами топологического графа. Обычно предполагается, что любые два ребра топологического графа пересекаются конечное число раз, при этом ни одно ребро не проходит через вершину и никакие два ребра не касаются друг друга. Топологический граф называется также «рисунком» графа.
