Цикломатическая матрица: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Цикломатическая матрица''' (''Cyclomatic matrix'') - матрица размером <math>c \times m</math>, г...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Цикломатическая матрица''' (''Cyclomatic matrix'') - | '''Цикломатическая матрица''' (''[[Cyclomatic matrix]]'') - | ||
матрица размером <math>c \times m</math>, где <math>c</math> | матрица размером <math>c \times m</math>, где <math>c</math> - число [[цикл|циклов]], а <math>m</math> - число [[ребро|ребер]] в [[граф|графе]], <math>(i,j)</math> элемент которой равен 1, если <math>j</math>-е ребро принадлежит <math>i</math>-му циклу, и 0 в противном случае; '''Цикломатическая матрица''' называется ''базисной'', если в ней представлены только независимые (''фундаментальные'' относительно некоторого [[каркас|каркаса]]) ''циклы''. Иногда под | ||
число ребер в графе, <math>(i,j)</math> элемент которой равен 1, если <math>j</math>-е ребро | '''цикломатической матрицей''' понимают именно базисную '''цикломатическую матрицу.''' В [[орграф|орграфе]] для каждого цикла | ||
принадлежит <math>i</math>-му циклу, и 0 в противном случае; ''' | задается направление [[обход графа|обхода]] и <math>(i,j)</math>-й элемент равен 1, -1 или 0, | ||
''базисной'', если в ней представлены только независимые (''фундаментальные'' относительно некоторого каркаса) ''циклы''. Иногда под | смотря по тому, входит ли <math>j</math>-я [[дуга]] в <math>i</math>-й цикл и ее ориентация | ||
''' | |||
задается направление обхода и <math>(i,j)</math>-й элемент равен 1, -1 или 0, | |||
смотря по тому, входит ли <math>j</math>-я дуга в <math>i</math>-й цикл и ее ориентация | |||
совпадает с направлением обхода, ориентация противоположна | совпадает с направлением обхода, ориентация противоположна | ||
направлению обхода или она вообще не принадлежит циклу. | направлению обхода или она вообще не принадлежит циклу. | ||
Версия от 14:15, 7 мая 2010
Цикломатическая матрица (Cyclomatic matrix) - матрица размером [math]\displaystyle{ c \times m }[/math], где [math]\displaystyle{ c }[/math] - число циклов, а [math]\displaystyle{ m }[/math] - число ребер в графе, [math]\displaystyle{ (i,j) }[/math] элемент которой равен 1, если [math]\displaystyle{ j }[/math]-е ребро принадлежит [math]\displaystyle{ i }[/math]-му циклу, и 0 в противном случае; Цикломатическая матрица называется базисной, если в ней представлены только независимые (фундаментальные относительно некоторого каркаса) циклы. Иногда под цикломатической матрицей понимают именно базисную цикломатическую матрицу. В орграфе для каждого цикла задается направление обхода и [math]\displaystyle{ (i,j) }[/math]-й элемент равен 1, -1 или 0, смотря по тому, входит ли [math]\displaystyle{ j }[/math]-я дуга в [math]\displaystyle{ i }[/math]-й цикл и ее ориентация совпадает с направлением обхода, ориентация противоположна направлению обхода или она вообще не принадлежит циклу.
Литература
[Берж],
[Свами-Тхуласираман]