Page 107 - 4204
P. 107
ЛЕКЦІЯ 8. ЗАДАЧІ МЕРЕЖЕВОГО АНАЛІЗУ З ЕЛЕМЕНТАМИ ТЕОРІЇ ГРАФІВ
Степенем вершини називається кількість ребер, що вихо-
дить з вершини.
Маршрутом (або шляхом) у графі називається послідовність
вершин v і ребер e така, що кожні два сусідні ребра в цій послі-
i
i
довності мають спільну вершину e = (v ,v ), i=1,2,…,k.
i
i+1
i
Вершина v називається початком шляху, а вершина v
k+1
1
кінцем шляху. Всі інші вершини цього шляху називаються про-
міжними, або внутрішніми, вершинами.
Кількість ребер k у маршруті називається довжиною марш-
руту. Кажуть, що цей маршрут з’єднує вершини v і v або веде з
1
k+1
вершини v у вершину v .
k+1
1
Маршрут, в якому всі ребра попарно різні, називається лан-
цюгом. Маршрут, в якому всі проміжні вершини попарно різні,
називається простим ланцюгом.
Маршрут називається замкненим (або циклічним), якщо
v = v . Замкнений ланцюг називається циклом, а замкнений
1
k+1
простий ланцюг простим циклом.
Граф, довільні дві вершини якого можуть бути з’єднані де-
яким маршрутом називається зв’язним. Інакше граф називається
незв’язним.
Зв’язний граф що немає циклів називається деревом.
Покривним деревом називається будь-яке дерево, що містить
усі вершини графа.
106