Fundamental set of cutsets

Материал из WikiGrapp
Перейти к навигации Перейти к поиску

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.