Page 99 - 4496

коцикломатичним числом. Цикломатичним числом графа
називають число =m-n+p.
Формальне поняття незалежних циклів уводиться в
такий спосіб. Введемо в графі довільну орієнтацію ребер.
Розглянемо деякий довільний цикл і зіставимо йому вектор,
який містить m компонент, що зіставлені ребрам за правилом:
значення компоненти
-
+
+
r ij= r ij – r ij, де r ij - число проходів по циклу у
-
напрямку ребра, r ij –число проходів проти напрямку ребра.
Уведемо дві операції на множині всіх векторів:
додавання векторів як покомпонентне додавання їх
компонентів і множення вектора на число як множення
кожного компонента на це число.
Множина векторів називається лінійно незалежною,
якщо рівність  1r 1+ 2r 2...+ кr к =0 виконується тільки при
 1= 2.=...= до=0.
Множина векторів з введеними операціями утворюють
лінійний простір. Множина, що містить максимальне число
його лінійно незалежних векторів, називається базисом
простору, число елементів базису називається розмірністю
простору. У цьому просторі будь-який вектор може бути
виражений як сума добутків базисних векторів на константи.
Теорема. У графі число  визначає число незалежних
циклів у ньому.
Доведення проводиться за індукцією. Припустимо, що
теорема слушна для числа ребер m, і покажемо, що тоді вона
слушна й для m`=m+1. Додамо в граф G ще одне ребро (a,b),
тоді можливі два випадки:
1. В G вершини a і b пов'язані ланцюгом, тоді в
розширеному графі G’ додасться ще один цикл, тобто буде
m’=m+1, p’=p, ’=+1.

96