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