Page 305 - 6197

За допомогою матриці інцидентності можна легко знайти
степінь будь-якої вершини графа. Для цього необхідно лише
знайти суму елементів відповідного рядка матриці B , тобто
m
deg V i  b , i  1,n , (Д3.2)
  
ij
j 1 
де n , m - відповідно вершин і ребер графа.
Для задачі з прикладу Д3.5:
V
2
deg   degV    degV    degV    degV     ,
4
1
3
8
7
 
4
deg   degV    3V  , deg V  .
6
5
2
Розглядається неорієнтований граф G , який має n
вершин. Уторимо матрицю A розміром n n , елементи якої
визначимо так:
 1 якщо та вершини з'єднані між собою,i j
a   .
ij
 0 в інших випадках.
j
0
У тому випадку, коли i  і граф не вміщує петель a  .
ii
Отримана у такий спосіб матриця A носить назву матриці
суміжності.
Приклад Д3.6. Скласти матрицю суміжності для графа,
який зображений на рис. 2.5. Оскільки граф має 8 вершин, то
матриця суміжності A буде квадратною матрицею розміром
8 8 . Будуємо матрицю A , в якій елементи визначаються за
правилом (Д3.2). Маємо

305