36 Краткие сообщения УДК 519.1 О СТЯГИВАНИИ ЦИКЛОВ В ОРИЕНТИРОВАННЫХ ГРАФАХ П.В. <...> Наливайко1 Для решения задачи об отыскании в ориентированном графе ветвления минимального веса среди всех ветвлений максимальной мощности существует эффективный алгоритм, разработанный Тарьяном, основанный на технике стягивания циклов. <...> В данной работе показывается, что эта техника применима и к более общей задаче, в которой на ветвление наложено дополнительное условие о том, что множество покрытых им вершин должно быть независимо относительно заданного матроида. <...> An efficient algorithm exists for solution of the problem of determination of a branching of minimal weight among all branchings of maximal cardinality in an oriented graph. <...> It is shown in this paper that this technique is applicable to a more general problem when the branching is subject to the additional condition that the set of vertices covered by this branching must be independent with respect to a given matroid. <...> Для произвольного ориентированного графа G обозначим через VG (соответственно AG) множество его вершин (соответственно дуг). <...> Для множества вершин X обозначим множество входящих в (исходящих из) X дуг через δin(X) (δout(X)). <...> Обозначим множество дуг, оба конца которых лежат в X, через γ(X). носителем (здесь и далее подразумеваемое конечным), а I — это семейство подмножеств множества E, такое, что: 1) ∅∈ I; 2) из того, что X ∈I и Y ⊆ X, следует, что Y ∈I; 3) для любых X,Y ∈I, таких, что |X| < |Y |, существует такое a ∈ Y \X,что X ∪{a}∈I. <...> Ветвлением в ориентированном графе G =(VG,AG) назовем множество дуг B ⊆ AG, такое, что неориентированный граф, порожденный множеством B, ацикличен и в каждую вершину графа входит не более одной дуги из B. <...> Напомним [1], что матроидом называется пара (E,I),где E — это непустое множество, называемое Предположим, что дуги графа G имеют <...>