Оточення – безліч вершин, суміжних із заданою. Орграф, орієнтований граф G = (V, E) є пара множин, де V – безліч вершин (вузлів), E – безліч дуг (орієнтованих ребер). Дуга – упорядкована пара вершин (v, w), де вершину v називають початком, а w – кінцем дуги.
Якщо ребро має певний напрямок (наприклад, ребро йде не від вершини В до вершини А, а з вершини А до вершини В), то таке ребро називають дугою. Тобто ребро з'єднує дві вершини графа, а дуга починається з однієї вершини та закінчується в іншій.
Граф — це геометрична фігура, яка складається з точок та ліній, що їх з'єднують. Крапки називають вершинами графа, А лінії – ребрами. Два ребра називаються суміжними, якщо вони мають загальна вершина. Два ребра називаються кратними, якщо вони з'єднують ту саму пару вершин.
Петля у графі — ребро, інцидентне одній і тій самій вершині.