Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:
- как и геометрия, обладает наглядностью;
- как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
- не имеет громоздкого математического аппарата ;
- имеет выраженный прикладной характер.
Задача коммивояжёра — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов. Существует несколько частных случаев общей постановки задачи, в частности, геометрическая задача коммивояжёра, метрическая задача коммивояжёра, симметричная и асимметричная задачи коммивояжёра. Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра.
Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.
В теории графов теорема Кёнига , доказанная Денешем Кёнигом в 1931, утверждает эквивалентность задач нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольных графах. Независимо была открыта, в том же 1931, Йенё Эгервари в несколько более общем виде для случая взвешенных графов.
Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах 
-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Граф-схема алгоритма (ГСА) — конечный связный ориентированный граф 
, вершины которого 
соответствуют операторам, а дуги 
задают порядок следования вершин (операторов) алгоритма, где 
— число вершин графа, 
— число дуг. В более широком смысле вершинам графа соответствуют не только операторные вершины, но и условные, начальная и конечная вершины и т. д. При рассмотрении параллельных алгоритмов вводится понятие параллельной граф-схемы алгоритма (ПарГСА), в состав которой входят вершины распараллеливания/синхронизации, функциональность которых обычно совмещается. Иногда в состав ГСА вводятся вершины дополнительных типов: объединения альтернативных дуг, фиктивные операторные вершины, вершины маркировки, ждущие вершины.
Разбиение графа на подграфы — представление исходного графа в виде множества подмножеств вершин 
по определенным правилам. Обычно по условию задачи требуется, чтобы 
, то есть все вершины исходного графа должны быть распределены по подмножествам, причём 
. Обычно также дополнительно вводится требование ортогональности разбиения: 
, то есть одна и та же вершина не может входить в состав различных подмножеств. Иногда из множества возможных разбиений требуется выбрать одно, удовлетворяющее ограничениям и являющееся оптимальным по обозначенному критерию, либо доказать, что искомое разбиение не существует. Задача разбиения графа относится к классу NP-полных, верхняя оценка числа разбиений определяется числом Белла, однако при этом обычно не все возможные разбиения являются корректными, то есть оценка является завышенной. При значениях числа вершин графа более 15—20 получение оптимальных разбиений как правило невозможно за приемлемое время, поэтому на практике ограничиваются субоптимальными решениями, полученными с использованием эвристических алгоритмов.
Задача Штейнера о минимальном дереве состоит в поиске кратчайшей сети, соединяющей заданный конечный набор точек плоскости. Задача получила своё название в честь Якоба Штейнера (1796—1863).
В теории графов паросочетание, или независимое множество рёбер в графе, — это набор попарно несмежных рёбер.
Инвариа́нт гра́фа в теории графов — некоторое обычно числовое значение или упорядоченный набор значений (хеш-функция), характеризующее структуру графа 
и не зависящее от способа обозначения вершин или графического изображения графа. Играет важную роль при проверке изоморфизма графов, а также в задачах компьютерной химии.
В комбинаторной оптимизации под линейной задачей о назначениях на узкие места понимается задача, похожая на задачу о назначениях.
В теории графов графом без клешней называется граф, который не содержит порождённых подграфов, изоморфных K1,3 (клешней).
Рёберно k-связный граф — граф, который остаётся связным после удаления не более чем 
рёбер.
Теорема о планарном разбиении — это форма изопериметрического неравенства для планарных графов, которое утверждает, что любой планарный граф может быть разбит на более мелкие части путём удаления небольшого числа вершин. В частности, удалением O(√n) вершин из графа с n вершинами можно разбить граф на несвязные подграфы, каждый из которых имеет не более 2n/3 вершин.
Лемма регулярности Семереди — лемма из общей теории графов, утверждающая, что вершины любого достаточно большого графа можно разбить на конечное число групп таких, что почти во всех двудольных графах, соединяющих вершины из двух разных групп, рёбра распределены между вершинами почти равномерно. При этом минимальное требуемое количество групп, на которые нужно разбить множество вершин графа, может быть сколь угодно большим, но количество групп в разбиении всегда ограничено сверху.
Модульное разложение — это разложение графа на подмножества вершин, называемых модулями. Модуль является обобщением компоненты связности графа. В отличие от компонент связности, однако, один модуль может быть собственным подмножеством другого. Модули, поэтому, ведут к рекурсивной (иерархической) декомпозиции графа, а не просто к разбиениям.
Косое разбиение графа — разбиение его вершин на два подмножества в виде несвязного порождённого подграфа и дополнения; играет важную роль в теории совершенных графов.
Минимально критичное остовное дерево во взвешенном неориентированном графе — это остовное дерево, в котором наиболее тяжёлое ребро весит как можно меньше. Критичное ребро — это самое тяжёлое ребро в стягивающем дереве. Стягивающее дерево является минимальным критичным остовным деревом, если граф не содержит стягивающего дерева с критичным ребром меньшего веса. Для ориентированного графа аналогичная задача известна как минимально критичное стягивающее ориентированное дерево.
