Page 9 - 4336

Напряямлені рребра наазиваютьь орієнттованимми ребраами абоо

дугаами, перрша по черзі веершина називаєється поччатком дуги, аа

друуга – її кіінцем. Граф, щоо міститьь напряммлені реббра, назииваєтьсяя

орієєнтованним граффом або орграффом (рисс. 1.2 а),, а графф, що нее

місттить наппрямлених реберр – неоррієнтованим абоо н-графоом (рис..

1.2 б). Граф, у яякому пприсутніі і ребрра і дууги назииваєтьсяя

змішшаним гграфом (рис. 1.22 в). Мнножина рребер гррафа можже бутии

поррожньоюю (рис. 11.2 г). ТТакий грраф назииваєтьсяя порожжнім абоо

нулль-графоом. Тривііальним називаєється грааф з одніією вершшиною іі

без ребер. ММультигграф – цце граф, в якомуу існує ппара вершшин, щоо

з'єдднана білльш ніжж одним ребром,, або білльше ніжж двомаа дугамии

проотилежниих напряямків.

а бб в г

Рисунок 1..2 – Видии графівв: а – оріієнтованний; б – ннеорієнттований

граф; в –– змішанний графф; г – поррожній гграф

Якщо декількка реберр є інциидентні одній і тій саммій паріі
вершин, тоо такі реебра наззиваються краттними (ззустрічаюються вв

мулльтиграффах).
Граф без петеель і краатних реебер наззиваєтьсяся повнимм, якщоо

кожжна пара його вершинн з'єднанна ребрром. Поввний грраф з nn
вершинамии позначається KK . Якщоо граф GG=(V, E) є повниим, то заа
n
(2)
ознначеннямм E=V . На рис. 1.3 зоббражено повні гррафи К , К , К ,,
2 2
3
4
К , і К відпповідно.
6
5

9