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

Маршрут (замкнутый маршрут) называется гамильтоновой цепью (гамильтоновым циклом), если он содержит все вершины графа и через каждую проходит по одному разу. Известен ряд достаточных условий существования гамильтоновых циклов, например: граф не имеет петель и кратных рёбер и для любых двух его несмежных вершин сумма степеней не меньше числа вершин этого графа; граф является плоским и $4$-связным; граф не имеет петель и кратных рёбер, а число $n$ его вершин и число $m$ его рёбер удовлетворяют условиям $n\geqslant 3$ и $m\geqslant\dfrac12(n^2 -3n + 6)$. Граф называется гамильтоновым (эйлеровым), если он имеет гамильтонов (эйлеров) цикл. Граф называется гамильтоново связным, если любые две его вершины соединены гамильтоновой цепью, и $k$-гамильтоновым, если любая простая цепь длины $k$ входит в некоторый гамильтонов цикл. Известная задача о коммивояжёре состоит в том, чтобы найти в графе, рёбрам которого приписаны неотрицательные числа (длины рёбер), гамильтонов цикл, имеющий наименьшую сумму длин рёбер. Эта и другие задачи об обходе графа имеют различные технические и экономические приложения.