Коне́чный автома́т (КА) в теории алгоритмов — математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. Является частным случаем абстрактного дискретного автомата, число возможных внутренних состояний которого конечно.
Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:
- как и геометрия, обладает наглядностью;
- как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
- не имеет громоздкого математического аппарата ;
- имеет выраженный прикладной характер.
Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.
Теория автоматов — раздел дискретной математики, изучающий абстрактные автоматы — вычислительные машины, представленные в виде математических моделей, и задачи, которые они могут решать.
Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.
В теории графов графом-циклом называется граф, состоящий из единственного цикла, или, другими словами, некоторого числа вершин, соединённых замкнутой цепью. Граф-цикл с n вершинами обозначают как Cn. Число вершин в Cn равно числу рёбер и каждая вершина имеет степень 2, то есть любая вершина инцидентна ровно двум рёбрам.
Куби́ческий граф — граф, в котором все вершины имеют степень три. Другими словами, кубический граф является 3-регулярным. Кубические графы называются также тривалентными.
В теории графов теорема о раскраске дорог, известная до недавнего времени как гипотеза о раскраске дорог, имеет дело с инструкциями синхронизации. Задача ставится в нахождении таких инструкций, чтобы независимо от начального положения объекта можно было бы дойти до пункта назначения в сети. В реальном мире можно данную задачу представить как набор инструкций для вашего друга, по которым он может добраться до вашего дома независимо от того, где он находится сейчас. Теорема также имеет приложение в символической динамике.
Циклический ранг ориентированного графа — мера связности орграфа, предложенная Эгганом и Бучи. Это понятие интуитивно отражает, насколько близок орграф к направленному ациклическому графу, когда циклический ранг НАГ равен нулю, в то время как ориентированный орграф порядка n с петлями в каждой вершине имеет циклический ранг n. Циклический ранг ориентированного графа тесно связан с глубиной дерева неориентированного графа и высотой итерации регулярных языков. Циклический ранг нашёл применение также в вычислениях с разреженными матрицами и логике.
Дэвид Самнер в 1971 высказал гипотезу, что турниры являются универсальными графами для полидеревьев. Более точно, гипотеза Самнера утверждает, что любая ориентация любого дерева с 
вершинами является подграфом любого турнира с 
вершинами. Гипотеза остаётся недоказанной. Кюн, Майкрофт и Остус говорят о гипотезе как об «одной из наиболее известных задач о турнирах.»
Говорят, что ориентированный граф апериодичен, если нет целого числа k > 1, делящего длину любого цикла графа. Эквивалентно, граф апериодичен, если наибольший общий делитель длин его циклов равен единице. Этот наибольший общий делитель для графа G называется периодом графа G.
Фишечная игра — это вид математической игры, в которой игра заключается в передвижении «фишек» или «маркеров» на ориентированном графе. Существует большое число различных фишечных игр.
Задача китайского почтальона, маршрут почтальона или задача инспекции дорог заключается в поиске кратчайшего замкнутого пути или цикла, который проходит через каждое ребро (связного) взвешенного неориентированного графа. Если граф имеет эйлеров цикл, тогда этот цикл служит оптимальным решением. В противном случае задачей оптимизации является поиск наименьшего числа рёбер графа с повторными проходами, так что получающийся мультиграф имеет эйлеров цикл. Эта задача может быть решена за полиномиальное время.
Су́ффиксный автома́т — структура данных, позволяющая хранить в сжатом виде и обрабатывать информацию, связанную с подстроками данной строки. Представляет собой детерминированный конечный автомат, принимающий все суффиксы слова 
и только их, и обладающий наименьшим возможным числом состояний среди всех таких автоматов. Менее формально, суффиксный автомат — это ориентированный ациклический граф с выделенной начальной вершиной и набором «финальных» вершин, дуги которого помечены символами, такой что у любой вершины символы на исходящих из неё дугах попарно различны и для любого суффикса слова 
существует путь из начальной вершины в некоторую финальную вершину, символы на котором при конкатенации образуют данный суффикс. Из всех графов, удовлетворяющих данному описанию, суффиксным автоматом называется тот, который обладает наименьшим возможным числом вершин.
Минимизация ДКА — построение по детерминированному конечному автомату (ДКА) эквивалентного ДКА, имеющего наименьшее возможное число состояний.
Детерминированный конечный автомат, известный также как детерминированный конечный распознаватель — это конечный автомат, принимающий или отклоняющий заданную строку символов путём прохождения через последовательность состояний, определённых строкой. Имеет единственную последовательность состояний во время работы. Мак-Каллок и Уолтер Питтс были одними из первых исследователей, предложивших концепцию, похожую на конечный автомат в 1943 году.
Недетерминированный конечный автомат — это детерминированный конечный автомат, который не выполняет следующие условия:
- любой его переход единственным образом определяется по текущему состоянию и входному символу
- чтение входного символа требуется для каждого изменения состояния.
