Page 79 - 2589

Розв’язок. Графи A і A не ізоморфні, хоча вони і мають
1
2
однакове число вершин і ребер. Але в графі A одне з ребер
1
направлено від а до b, а в графі A воно спрямоване в інший бік.
2
Графи B і B ізоморфні, тому що вони мають одне і те ж число
1
2
вершин і будь-які дві вершини графа B з'єднані ребром тільки
1
тоді, коли відповідні їм вершини графа B також з'єднані ребром.
2

5.3 Локальні степені вершин графа
Якщо задано матриці суміжності ∆ або інцидентності Е

графа, то можна визначити локальні степені всіх його вершин.
Справді, в j -му стовпці матриці інцидентності, що відповідає

вершині ν одиниці знаходяться на перетині з рядками, яким
j
відповідають інцидентні цій вершині ребра, а інші елементи
m
стовпця дорівнюють 0. Отже, ( )   
j ij
 i 1
Елементи ж δ матриці суміжності – це кількість ребер,
ij
n
інцидентних вершинам ν і ν . Звідси ( )    .
i j j ij
 j 1
При підрахунку степенів вершин за цими формулами кожна
петля вносить у степінь інцидентної їй вершини 1. Проте при
зображенні петлі на рисунку до цієї вершини примикають два
кінці петлі, тобто петля вносить у цей степінь 2. Щоб таким

чином ураховувати внесок петель у степінь, треба трохи
ускладнити формули для його обчислення. Через коефіцієнти
матриці інцендентності степінь можна розрахувати, наприклад, за

формулою
m n
(  )     3(    ).
j ij ik
 i 1 k 1
n
Коли і-те ребро звичайне,   ik  2, і відповідний доданок
k 1
зовнішньої суми дорівнює ε , тобто 1 для ребер, інцидентних
ij
n
вершині ν та 0 для інших. Якщо ж воно є петлею, то   1, а
j ik
k 1
доданок зовнішньої суми дорівнює 2ε , тобто 2 для петель,
ij
інцидентних вершині ν , та 0 для інших.
j
Це саме значення степеня визначається через коефіцієнти δ
ij
матриці суміжності графа G за формулою

79