Цикломатическая матрица: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Цикломатическая матрица''' (''[[Cyclomatic matrix]]'') -
'''Цикломатическая матрица''' (''[[Cyclomatic matrix]]'') матрица размером <math>c \times m</math>, где <math>\,c</math> число [[цикл|циклов]], а <math>\,m</math> число [[ребро|ребер]] в [[граф|графе]], <math>\,(i,j)</math> элемент которой равен 1, если <math>\,j</math>-е ребро принадлежит <math>\,i</math>-му циклу, и 0 в противном случае;
матрица размером <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, -1 или 0,
задается направление [[обход графа|обхода]] и <math>\,(i,j)</math>-й элемент равен 1, -1 или 0,
смотря по тому, входит ли <math>j</math>-я [[дуга]] в <math>i</math>-й цикл и ее ориентация
смотря по тому, входит ли <math>\,j</math>-я [[дуга]] в <math>\,i</math>-й цикл и ее ориентация
совпадает с направлением обхода, ориентация противоположна
совпадает с направлением обхода, ориентация противоположна направлению обхода или она вообще не принадлежит циклу.
направлению обхода или она вообще не принадлежит циклу.
==Литература==
==Литература==
[Берж],  
* Берж К. Теория графов и ее применения. — М.: Изд-во иностр. лит., 1962.
 
[Свами-Тхуласираман]
* Свами М., Тхуласираман К. Графы, сети и алгоритмы. — М.: Мир, 1984.

Текущая версия от 12:43, 30 сентября 2011

Цикломатическая матрица (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.