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

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

Литература

• Берж К. Теория графов и ее применения. — М.: Изд-во иностр. лит., 1962.

• Свами М., Тхуласираман К. Графы, сети и алгоритмы. — М.: Мир, 1984.