4.Цикломатикалық матрица.
Айталық G ациклды болмаған мультиграф, яғни ν(G) > 0 болсын.
14-анықтама. Жолдары G мультиграф циклді базисінің вектор-циклдары болған ν(G) * m(G) өлшемді C(G) матрица G ның цикломатикалық матрицасы деп айтылады.
32 – мысал. 31-мысалда қарастырылған G мультиграф үшін цикломатикалық матрица анықтаймыз. G мультиграф қабырғаларына бағыт енгіземіз. Нәтижеде 32 – сызбада бейнеленген бағытталған мультиграф аламыз. υ2
х'2 х'3
х'5
υ1 х'7- -х'8 υ4
х'6
х'1 х'4
υ3
32 – сызба.
Енді 31 – мысалда табылған, G мультиграф циклді базисына сәйкес вектор-циклдарды жазамыз
C(μ1) = (0,1,1,0,-1,0,0,0);
C(μ2) = (-1,0,0,1,1,0,0,0);
C(μ3) = (0,0,0,0,1,-1,0,0);
C(μ4) = (-1,1,0,0,0,0,1,0);
C(μ5) = (-1,1,0,0,0,0,0,-1).
Онда
0 1 1 0 -1 0 0 0
-1 0 0 1 1 0 0 0
C(G) = 0 0 0 0 1 -1 0 0
-1 1 0 0 0 0 1 0
-1 1 0 0 0 0 0-1
Егер {μ1,…,μν} – алгоритм бойынша байланысты G мультиграфтан алынған циклді базис және С(G) – осы мультиграфтың цикломатикалық матрицасы болса, онда Т бұтақ ағашына кірмейтін қабырғаларға сәйкес C(G) матрицаның бағандарынан бас диогонал элементтері текқана {-1,1} жиынға тиісті болған ν(G) реттік квадрат матрица құру мүмкін. Мысалда нүктелі сызық арқылы көрсетілген бөліктер осы матрицаны құрайды. Бұл нақты факт әр бір μі жай циклда өзінен басқа циклда жатпайтын қабырға бар екендігін білдіреді.
Достарыңызбен бөлісу: |
