Page 107 - 4204

ЛЕКЦІЯ 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