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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Цикломатическое число графа''' (''[[Cyclomatic number, circuit rank]]'') -
'''Цикломатическое число графа''' (''[[Cyclomatic number]], [[circuit rank]]'')
для [[неориентированный граф|неориентированного графа]] <math>G = (V,E)</math> число <math>\lambda(G) = |E| - |V| + 1</math>, равное мощности множества ''[[фундаментальный цикл|фундаментальных циклов]]'' или,
для [[неориентированный граф|неориентированного графа]] <math>G = (V,E)</math> число <math>\lambda(G) = |E| - |V| + 1</math>, равное мощности множества ''[[фундаментальный цикл|фундаментальных циклов]]'' или,
что то же, числу ''[[хорда|хорд]]'' относительно [[каркас|каркаса]] <math>T</math> [[граф|графа]] <math>G</math>; для [[орграф|орграфа]] '''Ц.ч.''' неориентированного графа, получающегося заменой [[дуга|дуг]] [[ребро|ребрами]].
что то же, числу ''[[хорда|хорд]]'' относительно [[каркас|каркаса]] <math>T</math> [[граф|графа]] <math>G</math>; для [[орграф|орграфа]] '''цикломатическое число''' неориентированного графа, получающегося заменой [[дуга|дуг]] [[ребро|ребрами]].


Другое название - ''[[Цикломатический ранг]]''.
Другое название ''[[Цикломатический ранг]]''.
==Литература==
==Литература==
[Уилсон],  
* Оре О. Теория графов. — М.: Наука, 1968.


[Харари],   
* Уилсон Р. Введение в теорию графов. — М.: Мир, 1977.
 
   
[Оре]
* Харари Ф. Теория графов. —  М.: Мир, 1973.

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

Цикломатическое число графа (Cyclomatic number, circuit rank) — для неориентированного графа [math]\displaystyle{ G = (V,E) }[/math] число [math]\displaystyle{ \lambda(G) = |E| - |V| + 1 }[/math], равное мощности множества фундаментальных циклов или, что то же, числу хорд относительно каркаса [math]\displaystyle{ T }[/math] графа [math]\displaystyle{ G }[/math]; для орграфа цикломатическое число неориентированного графа, получающегося заменой дуг ребрами.

Другое название — Цикломатический ранг.

Литература

  • Оре О. Теория графов. — М.: Наука, 1968.
  • Уилсон Р. Введение в теорию графов. — М.: Мир, 1977.
  • Харари Ф. Теория графов. — М.: Мир, 1973.