Автома́т на гра́фе, формализация алгоритма, аналогичная машине Тьюринга. Ячейке ленты соответствует вершина графа, а движение головки влево или вправо по ленте заменяется переходом по одному из рёбер, инцидентных текущей вершине графа. Если граф является ориентированным, то движение из вершины возможно только по исходящим дугам. Неориентированный граф моделируется ориентированным графом заменой каждого ребра на два противоположно направленные дуги.

Если головка машины Тьюринга моделируется конечным автоматом, полустепень исхода вершины должна быть ограничена сверху. Это ограничение можно обойти, если, например, циклически упорядочить исходящие дуги, выделив одну из них в качестве начальной. Головка помещается не в вершину, а на дугу и может совершать только два движения: на следующую дугу, исходящую из той же вершины, или по текущей дуге на начальную дугу, исходящую из конца текущей дуги.

Основное назначение автомата на графе – исследовать граф, на котором он находится. Считается, что топология графа заранее неизвестна и автомат узнаёт её только в процессе движения по графу. Тем самым моделируется класс алгоритмов на графах, которые называются автоматными. Эта модель была предложена в 1967 г. М. О. Рабином, который поставил задачу обхода графа конечным автоматом. Для неориентированных графов задача обхода достаточно проста, соответствующие алгоритмы хорошо известны, имеют оценку $O(m),$ где $m$ – число рёбер графа, и являются автоматными. Для ориентированных графов существуют алгоритмы обхода с неулучшаемой оценкой $O(nm),$ где $n$ – число вершин. Однако эти алгоритмы не являются автоматными. При автоматном обходе возникает проблема отката (англ. backtracking): переход от конца дуги в её начало по некоторому ориентированному циклу. Если обход не автоматный, этот цикл проходится один раз, но автомат вынужден делать несколько проходов по циклу, чтобы выполнить откат. Поэтому верхняя оценка автоматных алгоритмов отличается от оптимальной $O(nm)$ на величину, требуемую для совершения таких откатов. См. также «О большое».

В 1971 г. И. Б. Бурдонов предложил автоматный алгоритм обхода ориентированного графа с $n$ вершинами и $m$ дугами, имеющий оценку $O(nm+n^2 \rm{log} n).$ Алгоритм основан на построении исходящего остова графа и метода поиска в ширину (англ. Breadth First Search – BFS) на этом остове. В 1978 г. К. Кобаяси представил алгоритм экспоненциальной сложности, основанный на методе поиска в глубину (англ. Depth First Search – DFS). В 1988 г. Ш. Куттен описал алгоритм с оптимальной оценкой $O(nm),$ но его автомат не был конечным, т. к. использовал ячейки графа с $\rm{log} n$ битов памяти. В 1994 г. Й. Афек и Э. Гафни описали алгоритм с оценкой $O(nm+n^2 \rm{log} n),$ также основанный на построении исходящего дерева, но использующий DFS. В 2004 г. И. Б. Бурдонов представил алгоритм, совмещающий BFS с методом отката, предложенным Афеком и Гафни, за счёт чего достигается оценка $O(nm+n^2\log\rm{log} n).$ Точная верхняя оценка автоматных алгоритмов обхода неизвестна.

Модель автомата на графе можно «инвертировать»: символ в вершине графа понимается как состояние автомата, неподвижно «сидящего» в этой вершине, а по дуге графа, понимаемой как канал передачи, перемещается не головка со своим состоянием, а сообщение, которое автомат в начале дуги посылает автомату в конце дуги. Эти две интерпретации модели эквивалентны.

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

Дальнейшее развитие этой модели связано с использованием нескольких автоматов на графе, которые (в интерпретации двигающихся автоматов) могут двигаться по графу независимо друг от друга, читать пометки в вершинах, оставленные другими автоматами, и обмениваться между собой сообщениями. В частности, время обхода графа двумя автоматами становится оптимальным – $O(nm).$ Эти автоматы двигаются синхронно, кроме случая прохода по новой (ещё не пройденной) дуге. В этом случае один автомат (первый) идёт по дуге, а второй автомат остаётся на месте, ожидая сообщения от первого автомата. В этом сообщении указывается, нужно ли второму автомату двигаться вперёд, догоняя первый автомат, если откат (возвращение в начало только что пройденной дуги) не требуется, или оставаться на месте, поджидая первый автомат, который проходит по циклу до второго автомата, тем самым совершая откат.

Были поставлены и предложены некоторые решения более сложных задач: исследование недетерминированного графа, мониторинг динамически меняющегося графа, а также задача параллельного вычисления значения функции от мультимножества значений, записанных в вершинах графа. Вычисление выполняется автоматами, находящимися в вершинах графа и обменивающимися между собой сообщениями, передаваемыми по дугам графа, т. е. в интерпретации неподвижных автоматов. Сначала выполняется обход графа, цель которого – разметить граф, изменяя состояния автоматов в вершинах. Строятся прямой (ориентированный от корня) и обратный (ориентированный к корню) остовы графа. Эта разметка используется для вычисления функции в алгоритме пульсации: от корня по прямому остову распространяются во все вершины сообщения-вопросы, а по обратному остову в корень приходят сообщения-ответы от всех вершин графа. Алгоритм пульсации может вычислять только агрегатную функцию: значение функции от объединения мультимножеств можно вычислить по значениям функции от этих мультимножеств. Однако известно, что любая функция $f(x)$ имеет агрегатное расширение, т. е. может быть вычислена как $h(g(x)),$ где $g$ – агрегатная функция. Разметка графа не зависит от той функции, которая будет вычисляться. Поэтому разметка выполняется один раз, а потом многократно используется для вычисления различных функций.

Требование конечности автомата на графе может ослабляться. В частности, исследовались автоматы, размер памяти которых может расти вместе с ростом числа вершин и дуг графа, но описание графа не помещается в памяти автомата. Неподвижные автоматы на графе как модель распределённой системы могут быть двух типов: синхронная модель, в которой все автоматы меняют свои состояния одномоментно, и асинхронная модель, в которой эти изменения происходят независимо друг от друга и в разные моменты времени. На основе таких моделей исследовались параллельные алгоритмы таких задач на графе, как построение максимального независимого множества (англ. Maximal Independent Set – MIS), поиск множества всех мостов в графе (англ. Finding Set of Bridges – FSB), построение минимального остовного дерева во взвешенном графе (англ. Minimum Spanning Tree – MST) и др.