Fundamental set of cutsets: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Fundamental set of cutsets''' --- фундаментальная система разрезов.») |
Glk (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Fundamental set of cutsets''' --- фундаментальная система разрезов. | '''Fundamental set of cutsets''' --- фундаментальная система разрезов. | ||
Let <math>T</math> be a ''spanning tree'' of a connected graph <math>G</math>. Any edge | |||
of <math>T</math> defines a partition of the vertices of <math>G</math>, since its removal | |||
disconnects <math>T</math> into two components. There will be a corresponding | |||
cut-set of <math>G</math> producing the same partition of vertices. This cut-set | |||
contains precisely one edge and a number ''chord'' of <math>T</math>. This | |||
cut-set is called a '''fundamental cut-set''' of <math>G</math> with respect to | |||
<math>T</math>. For the graph <math>G</math> and spanning tree <math>T</math>, a corresponding '''set of fundamental cut-sets''' and some other cut-sets can be expressed as linear | |||
ring-sums of fundamental cut-sets. | |||
Текущая версия от 15:38, 3 мая 2011
Fundamental set of cutsets --- фундаментальная система разрезов.
Let [math]\displaystyle{ T }[/math] be a spanning tree of a connected graph [math]\displaystyle{ G }[/math]. Any edge of [math]\displaystyle{ T }[/math] defines a partition of the vertices of [math]\displaystyle{ G }[/math], since its removal disconnects [math]\displaystyle{ T }[/math] into two components. There will be a corresponding cut-set of [math]\displaystyle{ G }[/math] producing the same partition of vertices. This cut-set contains precisely one edge and a number chord of [math]\displaystyle{ T }[/math]. This cut-set is called a fundamental cut-set of [math]\displaystyle{ G }[/math] with respect to [math]\displaystyle{ T }[/math]. For the graph [math]\displaystyle{ G }[/math] and spanning tree [math]\displaystyle{ T }[/math], a corresponding set of fundamental cut-sets and some other cut-sets can be expressed as linear ring-sums of fundamental cut-sets.