Граф (від грецького "пишу") - безліч V вершин і набір E невпорядкованих і впорядкованих пар вершин; зазвичай граф позначають як G (V, E).
Ребро - невпорядкована пара вершин.
Дуга - впорядкована пара вершин.
Те-є дуга має певний напрям, а ребро немає.
Граф, що містить тільки ребра, називається неорієнтованим (або неорграфом);
Граф, що містить тільки дуги - орієнтованим (або Орграф).
Кратні дуги і ребра - коли дві вершини з'єднані декількома ребрами. або декількома односпрямованим дугами.
Мультіграф - граф, який має кратні дуги або ребра.
Дуга (або ребро) може починатися і закінчуватися в одній і тій же вершині, в цьому випадку відповідна дуга (або ребро) називається петлею.
Псевдографом - граф, що містить петлі.
Вершини, з'єднані ребром або дугою, називаються суміжними.
Ребра, що мають загальну вершину, теж називаються суміжними.
Инцидентность - поняття, яке використовується тільки в відношенні ребра і вершини: якщо v1, v2 - вершини, а e = (v1, v2) - з'єднує їх ребро, тоді вершина v1 і ребро e інцидентні, вершина v2 і ребро e теж інцидентні. Дві вершини (або два ребра) інцидентними бути не можуть.
Доведено, що в 3-вимірному просторі будь-граф можна представити у вигляді укладання (коли вершини представляються точками, а дуги і ребра - стрілками і лініями відповідно) таким чином, що лінії, відповідні ребрам (дугам) ні перетинатися у внутрішніх точках. Для 2-мірного простору це невірно.
Планарний граф - граф, який може бути зображений на площині без перетину ребер (дуг).
Повний граф - граф. в якому кожна вершина з'єднана з кожної.
Повний граф - простий граф, в якому кожна пара різних вершин суміжна.
Полустепені заходу (результату) вершини - кількість дуг, що заходять (виходять) в (з) вершину (и).
Ступінь (валентність) вершини - це кількість вершин, з'єднаних з даної вершиною, або - кількість ребер графа, інцидентних даній вершині.
Гола вершина графа - ізольована вершина без петель.
Ізольована вершина - вершина, що не поєднана з іншими вершинами ні дугами, ні ребрами. проте така вершина може мати петлі. Так само можна сказати, що це вершина без інцідентних їй дуг або ребер. А в разі графа без петель це вершина ступеня 0 (до речі кажучи таку вершину вже можна назвати голою).
Вхід і вихід графа - вершини, які мають відповідну смислове значення в рамках конкретного завдання.
Шлях (маршрут) - послідовність ребер (в неорієнтованому графі) і / або дуг (в орієнтованому графі), така, що кінець однієї дуги (ребра) є початком іншої дуги (ребра). Або послідовність вершин і дуг (ребер) в якій кожен елемент інциденту попереднього і наступного.
Ланцюг в графі - маршрут, всі ребра якого різні.
Простий граф - граф, в якому немає кратних ребер і петель.
Простий шлях - шлях, всі ребра якого попарно різні. Іншими словами, простий шлях не проходить двічі через одне ребро.
Орієнтований граф G (V, X) називається односторонньо зв'язковим. якщо для будь-якої пари вершин vi. vj існує шлях або з vi в vj, або з vj в vi.
Орієнтований граф G (V, X) називається сильно зв'язковим. якщо для будь-якої пари вершин vi. vj існує шлях і з vi в vj, і з vj в vi.
Ейлеровим шляхом (ланцюгом) в графі називається довільний шлях, що проходить через кожне ребро графа в точності один раз.
Ейлером цикл - це Ейлером шлях, який є циклом.
Ейлеров граф - граф, що містить Ейлером цикл.
Полуейлеров граф - граф, що містить Ейлером шлях (ланцюг).
Гамильтонов шлях (або гамільтонова ланцюг) - шлях, що містить кожну вершину графа рівно один раз. Гамильтонов шлях, початкова і кінцева вершини якого збігаються, називається Гамільтона циклом.
Граф є гамільтоновим тоді і тільки тоді, коли його замикання - гамільтоновграф.
Контур - замкнутий шлях в орграфе.
Критичний шлях графа - шлях максимальної довжини в орієнтованому ациклічному графі.