Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:
- как и геометрия, обладает наглядностью;
- как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
- не имеет громоздкого математического аппарата ;
- имеет выраженный прикладной характер.
Кванти́ли распределе́ния хи-квадра́т — числовые характеристики, широко используемые в задачах математической статистики таких как построение доверительных интервалов, проверка статистических гипотез и непараметрическое оценивание.
Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.
Граф Петерсена — неориентированный граф с 10 вершинами и 15 рёбрами; достаточно простой граф, используемый в качестве примера и контрпримера для многих задач в теории графов.
Хромати́ческое число графа — минимальное число цветов, в которые можно раскрасить вершины графа так, чтобы концы любого ребра имели разные цвета.
Формула поворота Родрига — формула, связывающая два вектора с общим началом, один из которых получен поворотом другого на известный угол вокруг оси, проходящей через их общее начало:
Снарк в теории графов — связный кубический граф без мостов c хроматическим индексом 4. Другими словами, это граф, в котором каждая вершина имеет три соседние вершины и рёбра нельзя выкрасить только в три цвета, так чтобы два ребра одного цвета не сходились в одной вершине. Чтобы избежать тривиальных случаев, снарками часто не считают графы, имеющие обхват меньше 5.
В теории графов снарк Уоткинса — снарк с 50 вершинами и 75 рёбрами. Открыт Джоном Д. Уоткинсом в 1989 году.
Снарк Блануши — 3-регулярный граф с 18 вершинами и 27 рёбрами. Существуют два таких графа. Носят имя нашедшего оба этих графа в 1946 году югославского математика Данило Блануши.
В теории графов снарки «Цветы» образуют бесконечное семейство снарков, введённых Айзексом Руфусом в 1975 году.
Снарк Секереша — снарк с 50 вершинами и 75 рёбрами, пятый известный снарк. Открыт Дьёрдьем Секерешем в 1973 году.
Двойное покрытие циклами в теории графов — множество циклов в неориентированном графе, которое включает в себя каждое ребро ровно два раза. Например, любой полиэдральный граф образован из вершин и рёбер выпуклого многогранника, грани же при этом образуют двойное покрытие циклами: каждое ребро принадлежит ровно двум граням.
В теории графов говорят, что граф G гипогамильтонов, если сам по себе граф не имеет гамильтонова цикла, но любой граф, полученный удалением одной вершины из G, является гамильтоновым.
Многочлен Татта — многочлен от двух переменных, играющий большую роль в теории графов; определён для любого неориентированного графа и содержит информацию, насколько граф связен. Стандартное обозначение — 
.
11-клетка Балабана или (3-11)-клетка Балабана — это 3-регулярный граф с 112 вершинами и 168 рёбрами, названные именем румынского химика Александру Т. Балабана.
Цикловую раскраску можно рассматривать как уточнение обычной раскраски графов. Цикловое хроматичеcкое число графа 
с обозначением 
можно определить следующими эквивалентными способами.
- равен инфимуму по всем вещественным числам
таким, что существует отображение из 
в окружность с длиной, равной 1, при этом две смежные вершины отображаются в точки на расстоянии 
вдоль окружности. - равен инфимуму по рациональным числам
таким, что существует отображение из в циклическую группу 
со свойством, что смежные вершины отображаются в элементы на расстоянии 
друг от друга. - В ориентированном графе определим дисбаланс цикла
, как значение 
, делённое на меньшее из числа рёбер, направленных по часовой стрелке и числа рёбер, направленных против часовой стрелки. Определим дисбаланс ориентированного графа, как максимальный дисбаланс по всем циклам. Теперь, равен минимальному дисбалансу по всем ориентациям графа .
Гипотеза Хедетниеми — математическая гипотеза, в общем случае опровергнутая, предположение о связи между раскраской графов и тензорным произведением графов:
,
Лексикографическое произведение или суперпозиция графов — конструкция графа по данным двум. Если связи рёбер в двух графах являются отношениями порядка, то связь рёбер в их лексикографическом произведении является соответствующим лексикографическим порядком — отсюда название.
Смешанный граф G = представляет собой математический объект, состоящий из набора вершин V, набора (неориентированных) ребер E и набора направленных ребер A.
