Ориентированным графом называется граф, на рёбрах которого поставлены стрелки. Его рёбра называются дугами. Более формально, ориентированный граф — это пара $\Gamma=(V, E)$ из конечного множества вершин $V$ и множества дуг $E$, элементами которого являются упорядоченные пары вершин графа $\Gamma$. Заметим, что у нас в ориентированном графе разрешаются дуги из вершины в себя саму (петли), несколько дуг из одной вершины в другую (кратные дуги), "встречные" дуги (из $A$ в $B$ и из $B$ в $A$). То, что раньше называлось графом, мы теперь будем называть неориентированным графом.