Page 58 - 4496

локальні степені вершин графа. Дійсно, якщо e ребро
i
інцидентне V вершини то на перетині i -го рядка і j -го
j
стовпця маємо 1. В іншому випадку матимемо 0.
) = 
m
Отже,  (V j  . Елементи  матриці суміжності
 i 1 ij ij
V V
– це кількість ребер, інцидентних вершинам i і j .
n
Звідси  (V j 
) =  .
 i 1 ij
Наведені формули справедливості для підрахунку
локальної степені (ЛС) вершин графів без петель. У тому
випадку коли граф має петлі ЛС вершин графа знаходять за
такою формулою(використовується матриця інцидентності).
m
n


  V )( j   ij 3 (   ) , де m - кількість рядків
ik
 j 1 k 1
матриці, n - кількість стовпців матриці.
Дійсно, коли ребро e звичайне (з’єднює дві
i
n
вершини),то    2 .
ik
k 1 n
то   1
Якщо ж воно є петлею, ik і відповідно
k 1
m

  V )( j  2  ij , тобто 2 для петель інцидентних вершині
 i 1
V j і 0 для інших вершин .
e
V

55