Page 299 - 6197

a,b
Якщо   – ребра, тоді вершини a і b називають їх

кінцями. Ребро a,b називають інцидентними вершинам a і
b . І, навпаки, вершини a і b інцидентні ребру.
Дві вершини називають суміжними, якщо вони є кінцями
ребра (інцидентні ребру). Два ребра називають суміжними,
якщо вони інцидентні одній вершині (рис. Д3.1).
Обмеження на існування тільки одного ребра між двома
вершинами дає змогу подати будь-яке ребро як множину із
двох елементів, а саме вершин графа.

Приклад Д3.1. Граф з множиною вершин V  a,b,c,d,e і
 
 b,d ,
множиною ребер E    a,b , a,e ,  b,c ,  c,d 
 b,e ,
показаний на рис. Д3.2.
Наше визначення виключає також ребра, які називають
петлями (рис. Д3.3). Ребро яке з’єднує вершину саму з собою
називається петлею. Граф, в якому є петлі, називають графом
з петлями.
Якщо в графі є більше одного ребра між двома
вершинами, то він носить назву мультиграфа (рис. Д3.4).

Рисунок Д3.1 – Суміжні Рисунок Д3.2 – Граф з


ребра a,b і b,c
множиною вершин V і
множиною ребер E
Якщо граф має петлі і вершини, які з’єднані більше ніж
одним ребром, то такий граф називають псевдографом.

299