Page 65 - 4496

Крім того, якщо довільгу вершину v  V вважати
1  0  0 0   i  n , 2
шляхом із v у v нульової ваги, то і  i , .
Уведемо також у розгляд квадратну матрицю C(D)
порядку n з елементами
 v(l v , ), якщо v , v ( ) E
c ij   i j i j
 , якщо i v , v ( j ) E ,
яку будемо називати матрицею дуг зваженого орієнтованого
графа.
k
Твердження. Для обчислення  i використовується
i 
рекурентна формула (k ) 1  min{ i  k  c ij ) при i  n , 2 ; k  0

3.11 Ейлерові й напівейлерові графи

Теорія графів започаткована філософом Імануїлом Кант,
який гуляючи по місту Кенігсбергу поставив задачу у (1736),
відому в математиці як задача про сім мостів: чи можна
пройти по всіх цих мостах 190 і при цьому повернутися у
вихідну точку так, щоб по кожному мосту пройти тільки один
раз. Знаменитий математик швейцарського походження
Леонард Ейлер блискуче вирішив цю задачу.
Відповідно до поставленого Канта (і вирішеної Ейлером)
задачею можна дати наступні визначення:
Граф (або мультиграф без петель) називається
Ейлеровим, якщо існує цикл без повторення ребер (такий цикл
називають Ейлеровим), що обходить всі вершини графа. Граф
називається напівейлеровим, якщо існує маршрут без
повторення ребер (Ейлерів шлях), що обходить всі ребра
графа рівно один раз. На рис. 2 зображені: а– Ейлерсв граф,
б – напівейлерів граф й в – граф, що не є ні Ейлеревим, ні
напівейлеровим.

62