Independent circuits

Материал из WikiGrapp
Версия от 15:09, 19 мая 2011; Glk (обсуждение | вклад) (Новая страница: «'''Independent circuits''' --- независимые циклы. A set <math>{\mathcal C}</math> of ''circuits'' of <math>G</math> is called '''independent''' if …»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Independent circuits --- независимые циклы.

A set [math]\displaystyle{ {\mathcal C} }[/math] of circuits of [math]\displaystyle{ G }[/math] is called independent if for every nonempty subset [math]\displaystyle{ {\mathcal A} }[/math] of [math]\displaystyle{ {\mathcal C} }[/math] the symmetric difference of the circuits in [math]\displaystyle{ {\mathcal A} }[/math] is not empty. A maximal independent set of circuits of [math]\displaystyle{ G }[/math] is called a cycle basis of [math]\displaystyle{ G }[/math]. It is easy to see that every cycle basis of [math]\displaystyle{ G }[/math] has [math]\displaystyle{ |E(G)| - |V(G)| + c(G) }[/math] circuits, where [math]\displaystyle{ c(G) }[/math] is the number of components of [math]\displaystyle{ G }[/math].

See also

  • Cyclomatic number.