Page 73 - 2589

граф називається порожнім. Лінії, що зображають ребра графа,
можуть перетинатися, але точки перетину не є вершинами
(рис.4.1,в); різні ребра можуть бути інцидентними одній і тій

самій парі вершин (рис.4.1,г), такі ребра називаються кратними.
Цей випадок відповідає наявності кількох однакових пар

 , E(G). Граф, що містить кратні ребра, називається
i j
мультиграфом. Ребро може з'єднувати деяку вершину саму з

собою (рис.4.1,д), таке ребро називається петлею. Цей випадок
відповідає наявності в множині Е пар вигляду (ν, ν). Граф із
петлями та кратними ребрами називається псевдографом.

На рис.4.1,б зображено фрагмент нескінченного графа. Його
вершини – це точки площини з цілими координатами (х, у), а
ребра, що з'єднують їх, – горизонтальні й вертикальні відрізки.
Графи, які найчастіше розглядаються, є скінченними, тобто

скінченні множини їхніх елементів (вершин і ребер). їх і
розглядатимемо. Проте деякі поняття та результати, про які
йтиметься, належать до довільних графів. Скінченний

неорієнтований граф без петель і кратних ребер називається
звичайним.
Якщо пари (ν, w>)E вважаються впорядкованими, то граф є

орієнтованим. Інакше граф називається неорієнтованим. Ребра
орієнтованого графа прийнято називати дугами та зображати
напрямленими відрізками, як на рис.4.2.

При зображенні орієнтованих графів напрямки ребер
позначаються стрілками (рис.4.2,а). Орієнтований граф може
мати кратні ребра (рис.4.2,б), петлі (рис.4.2,в), а також петлі, що
з'єднують одні й ті самі вершини ребра, але у зворотних

напрямках (рис.4.2,г).

а) б) в) г)

Рисунок 4.2 – Типові приклади орієнтованих графів

Кожному неорієнтованому графу можна поставити у
відповідність орієнтований граф з тією самою множиною

вершин, в якій кожне ребро замінено двома орієнтованими
ребрами, що є інцидентними тим самим вершинам і мають

73