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