Графът е съвкупност от възли (върхове) и дъги (ребра), които ги свързват.
Графът се нарича ориентиран ако са дефинирани посоки на дъгите. Тогава дъгите се наричат стрелки.
Броят стрелки, влизащи в даден възел се наричат негова входна степен, а броят на излизащите – изходна степен.
Дървото е граф, на който само един възел има входна степен 0, а всички останали имат входни степени 1.
Етикетиран граф е този, чиито възли или дъги са именовани, например граф с градове и разстоянията между тях.
Път в граф е съвкупността от дъги, свързващи два възела. Един възел се нарича достижим от друг ако има път между тях. Дължина на пътя е броят дъги в него.
Цикъл е ненулев път, започващ и завършващ в един и същ възел.
Примка е цикъл с дължина 1.
Дървото е граф без цикли, и между два възела съществува най-много един път.
Коренен граф е граф, който има възел, наречен корен, такъв от който има път до всеки един възел. Дървото винаги има корен.