Page 50 - 4496

Кратні ребра

V

Ребро може починатися і закінчуватись в одній і тій
самій вершині. Тоді воно називається петлею.

V

Цей випадок відповідає наявності в множині Е пар
(V ,V ) .
Граф із кратними ребрами та петлями називається
псевдографом .
Якщо на рисунку вказують напрямок на ребра стрілкою
(наприклад, проходження сигналу),то граф називається
орієнтованим (орграф). В інших випадках-граф буде
неорієнтованим.
Скінчений неорієнтований граф без кратних ребер і
петель називають звичайним.
Ребра орієнтованого графа називають дугами.

e 1

V 1 V 2

e 2

Рисунок 3.1 - Орієнтований граф

Кожному неорієнтованому графу можна поставити у
відповідність орієнтований граф. З тією самою кількістю
вершин, в якому кожне ребро замінено двома орієнтованими
ребрами, що є інцидентними тим самим вершинам і мають
зворотні напрямки. Тому відповідність називають
канонічною.

47