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

Материал из WikiGrapp
Перейти к:навигация, поиск

Цикломатическая матрица (Cyclomatic matrix) — матрица размером c \times m, где \,c — число циклов, а \,m — число ребер в графе, \,(i,j) элемент которой равен 1, если \,j-е ребро принадлежит \,i-му циклу, и 0 в противном случае;

Цикломатическая матрица называется базисной, если в ней представлены только независимые (фундаментальные относительно некоторого каркаса) циклы. Иногда под цикломатической матрицей понимают именно базисную цикломатическую матрицу. В орграфе для каждого цикла задается направление обхода и \,(i,j)-й элемент равен 1, -1 или 0, смотря по тому, входит ли \,jдуга в \,i-й цикл и ее ориентация совпадает с направлением обхода, ориентация противоположна направлению обхода или она вообще не принадлежит циклу.

Литература

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