Теорія графів
Основні поняття та визначення
Граф - пара множин V і X - G = (V, X). V - безліч вершин, X - безліч ребер.
Петля - ребро виду (v, v).
Кратні ребра - однакові пари в X.
Орієнтований граф (орграф D) - граф, для якого пари в Х впорядковані. Ребра в орграфе називаються дугами і позначаються .
Ступенем вершини V графа G називається число d (v) ребер графа, інцідентних вершині v. Якщо d (v) = 1, тоді v - висяча вершина, якщо d (v) = 0, тоді v - ізольована вершина.
полустепені результату (заходу ) вершини v орграфа D називається d + (v) - число дуг, що виходять з v (? < span align = "justify"> - (v) - число дуг, що заходять у v).
Маршрутом для графа G (шляхом для орграфа D) називається послідовність v 1 x 1 v 2 x 2 v 3 ... x k v k +1.
Ланцюг - незамкнутий маршрут (шлях), в якому всі ребра (дуги) попарно різні.
Простий ланцюг - ланцюг, в якій всі вершини попарно різні.
Цикл (контур) - замкнутий маршрут (шлях), в якому всі ребра (дуги) попарно різні.
Простий цикл (контур) - цикл (контур), в якому всі вершини попарно різні.
Довжина шляху - число ребер (дуг) у маршруті (шляхи).
Шлях у графі називається
мінімальним , якщо він складається з мінімальної кількості р...
