Page 49 - 4496

Множину вершин графа позначають - V (G ) , а множину

ребер - E (G ) .
n (G )  V (G ; )
Кількість вершин графа
m (G )  E (G ; )
Кількість ребер графа
n (G )
Кількість вершин графа - називають
його порядком.

Ребра, які виходять із певної вершини називаються
інцидентними цій вершині. Кількість ребер графа,
інцидентних деякій вершині V , називається локальним
степенем, або просто степенем вершини V і позначається
 (V ) .
е 2
е 3

 (V )  3
е 1
V

Якщо e  (V ,W )  E (G ) , то кажуть : e W
- вершини V і W суміжні;
- вершини V і W є кінцями ребра e ;
- вершини V і W є інцидентними ребру e ;
- ребро e -інцидентне вершинам V і W .
Два ребра називають суміжними, якщо вони інцидентні
одній вершині.
e e e 1 ,e 2  суміжні ребра
1
2
Лінії, що зображають ребра графа можуть перетинатись,
але точки перетину не є вершинами графа.
Різні ребра можуть бути інцидентними одній і тій самій
вершині V .Такі ребра називаються кратними а граф, що
вміщує кратні ребра називається мультиграфом.

46