Граф – це абстрактних математичних об'єктів. Він складається з вершин та ребер. Кожне ребро поєднує пару вершин. Якщо ту саму пару вершин з'єднують кілька ребер, ці ребра називаються кратними.
Граф – це геометрична фігура, яка складається з точок та ліній, які їх з'єднують. Крапки називають вершинами графа, А лінії – ребрами. Два ребра називаються суміжними, якщо вони мають загальна вершина. Два ребра називаються кратними, якщо вони з'єднують ту саму пару вершин.
Зважений граф — граф, кожному ребру якого поставлено у відповідність певне значення (вага ребра). Граф, В якому всі вершини з'єднані ребрами, називається неорієнтованим. Ланцюг – шлях по вершинах і ребрах, що включає будь-яке ребро графа не більше одного разу.
Вершина графа – фундаментальне поняття теорії графів. Неорієнтований граф складається з безлічі вершин та безлічі ребер (невпорядкованих пар вершин), у той час як орієнтований граф складається з безлічі вершин та безлічі дуг (упорядкованих пар вершин).