Цикломатическая матрица

Материал из WikiGrapp
Версия от 15:29, 16 февраля 2010; Glk (обсуждение | вклад) (Создана новая страница размером '''Цикломатическая матрица''' (''Cyclomatic matrix'') - матрица размером <math>c \times m</math>, г...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Цикломатическая матрица (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]-й цикл и ее ориентация совпадает с направлением обхода, ориентация противоположна направлению обхода или она вообще не принадлежит циклу.

Литература

[Берж],

[Свами-Тхуласираман]