Тео́рия гра́фов, область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Основной объект теории графов – граф и его обобщения. Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок (задача о Кёнигсбергских мостах, задача о расстановке ферзей на шахматной доске, задачи о перевозках, задача о кругосветном путешествии и др.). Одним из первых результатов в теории графов стал критерий существования обхода всех рёбер графа без повторений, полученный Л. Эйлером (1736) при решении задачи о Кёнигсбергских мостах. Сформулированная в середине 19 в. проблема четырёх красок также выглядит как развлекательная задача, однако попытки её решения привели к появлению некоторых исследований графов, имеющих теоретическое и прикладное значение. В середине 19 в. появились работы, в которых при решении практических задач были получены результаты, относящиеся к теории графов. Так, например, Г. Кирхгоф (Kirchhoff. 1847) при составлении полной системы уравнений для токов и напряжений в электрической схеме предложил по существу представлять такую схему графом и находить в этом графе остовные деревья, с помощью которых выделяются линейно независимые системы контуров. А. Кэли (Cayley. 1890), исходя из задач подсчёта числа изомеров предельных углеводородов, пришёл к задачам перечисления и описания деревьев, обладающих заданными свойствами, и решил некоторые из них. В 20 в. задачи, связанные с графами, начали возникать не только в физике, химии, электротехнике, биологии, экономике, социологии и т. д., но и внутри математики, в таких разделах, как топология, алгебра, теория вероятностей, теория чисел. В начале 20 в. графы стали использоваться для представления некоторых математических объектов и формальной постановки различных дискретных задач; при этом наряду с термином «граф» употреблялись и другие термины, например карта, комплекс, диаграмма, сеть, лабиринт. После выхода в свет в 1936 г. монографии Д. Кёнига (König. 1950) термин «граф» стал более употребительным, чем другие. В этой работе были систематизированы известные к тому времени факты. В 20–30-х гг. 20 в. появились первые результаты, относящиеся к изучению свойств связности, планарности, симметрии графов, которые привели к формированию ряда новых направлений в теории графов. Значительно расширились исследования по теории графов в конце 1940-х – начале 1950-х гг., прежде всего в силу развития кибернетики и вычислительной техники. Благодаря развитию вычислительной техники, изучению сложных кибернетических систем интерес к теории графов возрос, а проблематика теории графов существенным образом обогатилась. Кроме того, использование ЭВМ позволило решать возникающие на практике конкретные задачи, связанные с большим объёмом вычислений, прежде не поддававшиеся решению. Для ряда экстремальных задач теории графов были разработаны методы их решения, например, один из таких методов позволяет решать задачи о построении максимального потока через сеть. Для отдельных классов графов (деревья, плоские графы и т. д.), которые изучались и ранее, было показано, что решения некоторых задач для графов из этих классов находятся проще, чем для произвольных графов (нахождение условий существования графов с заданными свойствами, установление изоморфизма графов и др.).

Характеризуя проблематику теории графов, можно отметить, что некоторые направления носят более комбинаторный характер, другие – более геометрический. К первым относятся, например, задачи о подсчёте и перечислении графов с фиксированными свойствами, задачи о построении графов с заданными свойствами. Геометрический (топологический) характер носят многие циклы задач теории графов, например обходы графов, укладки графов. Существуют направления, связанные с различными классификациями графов, например по свойствам их разложения. Примером результата о существовании графов с фиксированными свойствами может служить критерий реализуемости чисел степенями вершин некоторого графа: набор целых чисел $0 \leqslant d_{1} \leqslant d_{2} \leqslant \ldots \leqslant d_{n}$, сумма которых чётна, можно реализовать степенями вершин графа без петель и кратных рёбер тогда и только тогда, когда для любого $r$ $(1 \leqslant r \leqslant n-1)$ выполняется условие

$$\sum_{i=1}^{r} d_{i} \leqslant r(r-1)+\sum_{i=r+1}^{n} \min \left(r, d_{i}\right).$$Примерами задач о подсчёте графов с заданными свойствами являются задачи о нахождении количеств неизоморфных графов с одинаковым числом вершин и (или) рёбер. Для числа неизоморфных деревьев с $n$ вершинами была получена асимптотическая формула

$$t_{n}=C \frac{\theta^{n}}{n^{5 / 2}}+O\left(\frac{\theta^{n}}{n^{7 / 2}}\right),$$где $C=0,534948 \ldots$, $\theta=2,95576 \ldots$. Для числа $g_{n}$ неизоморфных графов без петель $n$ кратных рёбер с $n$ вершинами было показано, что

$$g_{n}=\frac{2^{C_n^2}}{n !}\left(1+\frac{2 n(n-1)}{2^{n}}+\frac{8(3 n-7) n !}{3(n-3)! \cdot 2^{2 n}}+ O\left(\frac{n^{5}}{2^{5 n / 2}}\right)\right).$$Наряду с проблемами, носящими общий характер, в теории графов имеются специфические циклы задач. В одном из них изучаются различные свойства связности графов, исследуется строение графов по свойствам связности. При анализе надёжности сетей связи, электронных схем, коммуникационных сетей возникает задача о нахождении количеств непересекающихся цепей, соединяющих различные вершины графа. Здесь получен ряд результатов. Например, наименьшее число вершин, разделяющих две несмежные вершины графа, равно наибольшему числу непересекающихся (по вершинам) простых цепей, соединяющих эту пару вершин. Найдены критерии и построены эффективные алгоритмы установления меры связности графа (наименьшего числа вершин или рёбер, удаление которых нарушает связность графа).

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

Характерным специфическим направлением теории графов является цикл задач, связанный с раскрасками графов, в котором изучаются разбиения множества вершин (рёбер), обладающие определёнными свойствами, например смежные вершины (рёбра) должны принадлежать различным множествам (вершины или рёбра из одного множества окрашиваются одним цветом). Было доказано, что наименьшее число цветов, достаточное для раскраски рёбер любого графа без петель с максимальной степенью $\sigma$, равно $[3\sigma/2]$, а для раскраски вершин любого графа без петель и кратных рёбер достаточно $\sigma+1$ цветов.

Существуют и другие циклы задач (см. в статьях Покрытия и упаковки, Укладка графа, Числовые характеристики графов); некоторые из них сложились под влиянием различных разделов математики. Так, под влиянием топологии производится изучение вложений графов в различные поверхности. Например, было получено необходимое и достаточное условие вложения графа в плоскость (критерий Понтрягина – Куратовского): граф является плоским тогда и только тогда, когда он не содержит подграфов, получаемых с помощью подразбиения рёбер из полного $5$-вершинного графа и полного двудольного графа с тремя вершинами в каждой доле. Под влиянием алгебры стали изучаться группы автоморфизмов графов. В частности, было доказано, что каждая конечная группа изоморфна группе автоморфизмов некоторого графа. Влияние теории вероятностей сказалось на исследовании случайных графов. Многие свойства были изучены для «почти всех» графов; например, было показано, что почти все графы с $n$ вершинами связаны, имеют диаметр $2$, обладают гамильтоновым циклом (циклом, проходящим через все вершины графа по одному разу).

В теории графов существуют специфические методы решения экстремальных задач. Один из них основан на теореме о максимальном потоке и минимальном разрезе, утверждающей, что максимальный поток, который можно пропустить через сеть из вершины $u$ в вершину $v$, равен минимальной пропускной способности разрезов, разделяющих вершины $u$ и $v$. Были построены различные эффективные алгоритмы нахождения максимального потока.

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

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