Основні поняття теорії графів

З формальної точки зору граф являє собою впорядковану пару G = (V, Е) множин, перше з яких складається з вершин, або вузлів, графа, а друге - з його ребер. Ребро пов'язує між собою дві вершини. При роботі з графами нас часто цікавить, як прокласти шлях з ребер від однієї вершини графа до іншої. Тому ми будемо говорити про рух по ребру; це означає, що ми переходимо з вершини А графа в іншу вершину В, пов'язану з нею ребром АВ (ребро графа, що пов'язує дві вершини, для стислості позначається цією парою вершин). В цьому випадку ми говоримо, що А примикає до В, або що ці дві вершини сусідні.
Граф може бути орієнтованим чи ні. Ребра неориентированного графа, найчастіше званого просто графом, можна проходити в обох напрямках. В цьому випадку ребро - це невпорядкована пара вершин, його кінців. В орієнтованому графі, або орграфе, ребра є впорядковані пари вершин: перша вершина - це початок ребра, а друга - його кінець. Далі ми скорочено говорити просто про ребрах, а орієнтовані вони чи ні буде зрозуміло з контексту.
Пізніше ми будемо просто малювати графи, а не ставити їх множинами. Вершини зображатимуться кружечками, а ребра - відрізками ліній. Усередині кружечків будуть записані мітки вершин. Ребра орієнтованого графа будуть забезпечені стрілками, що вказують допустиме напрямок руху по ребру.
На малюнку 1 зображено графічне представлення неорієнтованого (а) і орієнтованого (б) графів разом з їх формальним описом.

Термінологія
Повний граф - це граф, в якому кожна вершина з'єднана з усіма іншими. Числ ребер в повному графі без петель з N вершинами одно (N 2 - N) / 2. У повному оріентірвоанном графі дозволяється перехід з будь-якої вершини в будь-яку іншу. Оскільки в графі перехід по ребру дозволяється в обох напрямках, а перехід по ребру в орграфе - тільки в одному, в повному орграфе в два рази більше ребер, тобто їх число дорівнює N 2 - N.
Подграф (VS. ES) графа або орграфа (V, E) складається з деякого підмножини вершин і деякого підмножини ребер, їх з'єднують.
Шлях в графі або орграфе - це послідовність ребер, за якими можна по черзі проходити. Іншими словами, шлях з вершини A в вершину B починається в A і проходить по набору ребер до тих пір, поки не буде досягнута вершина B. З формальної точки зору, шлях з вершини vi в вершину vj це послідовність ребер графа vi vi + 1. vi + 1 vi + 2. vj-1 vj. Ми вимагаємо, щоб будь-яка вершина зустрічалася на такому шляху не більше, ніж один раз. У всякого шляху є довжина - число ребер в ньому. Довжина шляху AB, BC, CD, DE дорівнює 4.
В підвішеному графі або орграфе кожному ребру приписана число, зване вагою ребра. При зображенні графа зазвичай записують вагу ребра поруч з ребром. При формальному описі вага буде додатковим елементом невпорядкованою або впорядкованої пари вершин (утворюючи разом з цією парою "триплет"). При роботі з орієнтованими графами ми вважаємо вага ребра ціною проходу по ньому. Вартість шляху за зваженим графу дорівнює сумі ваг ребер шляху. Найкоротший шлях в зваженому графі - це шлях з мінімальною вагою, навіть якщо число ребер в дорозі і можна зменшити. Якщо, наприклад, шлях P1 складається з п'яти ребер з загальною вагою 24, а шлях P2 - з трьох ребер з загальною вагою 36, то шлях P1 вважається більш коротким.
Граф або орграф називається зв'язковим, якщо будь-яку пару вузлів можна з'єднати принаймні одним шляхом. Цикл - це шлях, який починається і закінчується в одній і тій же вершині. У ациклічному графі або орграфе цикли відсутні. Зв'язний ациклічний граф називається (Неукоріненість) деревом. Структура Неукоріненість дерева така ж, що і у дерева, тільки в ньому не виділено корінь. Однак кожна вершина Неукоріненість дерева може служити його коренем.