2.7. Базисные разрезающие множества
В разд. 2.4 было показано, что остов связного графа можно использовать для получения множества базисных циклов в графе. В данном разделе мы показываем, как с помощью остова можно определить множество базисных разрезающих множеств.
Рассмотрим остов Т связного графа G. Пусть b — ветвь Т. Удаление ветви b разбивает Т на две компоненты 
Следует отметить, что 
являются деревьями графа G. Пусть 
обозначают соответственно такие множества вершин 
что 
вместе содержат все вершины графа 
Пусть 
будут соответственно порожденными подграфами графа G на множествах вершин 
. Не трудно видеть, что 
являются остовами 
Следовательно, по теореме 
— связные графы. В теореме 2.6 доказывается, что разрез 
является разрезающим множеством графа G. Это разрезающее множество называется базисным множеством графа G по отношению к ветви b остова Т графа G. Множество всех 
базисных разрезающих множеств по отношению к 
-ветви остова Т связного графа G называется базисным множеством разрезающих множеств графа G по отношению к остову Т.
Следует отметить, что разрезающее множество 
содержит точно одну ветвь, т. е. ветвь b остова Т. Все другие ребра 
являются хордами Т. Это следует из того, что 
не содержит ни одного ребра из остовов 
. Далее, ветвь b не присутствует ни в одном базисном разрезающем множестве по отношению к Т. Из этого следует, что множество ребер базисного разрезающего множества нельзя представить в виде кольцевой суммы множеств ребер нескольких или всех базисных разрезающих множеств. В гл. 4 мы покажем, что каждое разрезающее множество
в — базисное разрезающее множество по отношению к ветви 
г — базисное разрезающее множество по отношению к ветви 
д — базисное разрезающее множество по отношению к ветви е — базисное разрезающее множество по отношению к ветви 
графа G можно представить кольцевой суммой нескольких базисных разрезающих множеств по отношению к остову Т графа 
