Page 20 - 4336

Приклад 1.4. Записати список ребер відповідно до матриці

інцидентності орієнтованого графа:

1 23 45 6 7 8

a 1 00 00 0 0 -1

b -1 -1 0 0 0 0 0 0

c 0 1 2 -1 0 0 0 0
B=
d 0 00 12 -1 0 0

e 0 00 00 1-1 0

f 0 00 00 0 1 1

Розв'язок.

Список ребер, записаний відповідно до матриці

інцидентності орієнтованого графа має вигляд:

Ребро 1 2 345678

початок ac c d d e f f
Вершини
кінець bb c c dd e a

1.4 Маршрути, ланцюги і прості ланцюги

1.4.1 Неорієнтований граф

Маршрутом (шляхом) у графі G називається така

послідовність ребер M(e , e ,…, e ), у якій кожні два сусідніх
1
n
2
ребра e та e мають спільну вершину. У маршруті те саме ребро
i
i-1
може зустрічатися кілька разів. Іншими словами, маршрут – це
сукупність ребер, які об'єднані разом вершинами так, що можна

рухатися по них уздовж графа.

Початок маршруту – це вершина v , інцидентна ребру e і
1
0
не інцидентна ребру e . Кінець маршруту – це вершина v
2
n
інцидентна ребру e і не інцидентна e . Якщо ребра e , e (e ,
2
n-1
n
n-1
1
20