RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Московского университета. Серия 1: Математика. Механика // Архив

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2010, номер 3, страницы 36–38 (Mi vmumm783)

Краткие сообщения

О стягивании циклов в ориентированных графах

П. В. Наливайко

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Аннотация: Для решения задачи об отыскании в ориентированном графе ветвления минимального веса среди всех ветвлений максимальной мощности существует эффективный алгоритм, разработанный Тарьяном, основанный на технике стягивания циклов. В данной работе показывается, что эта техника применима и к более общей задаче, в которой на ветвление наложено дополнительное условие о том, что множество покрытых им вершин должно быть независимо относительно заданного матроида.

Ключевые слова: граф, ветвление, матроид, стягивание циклов.

УДК: 519.1

Поступила в редакцию: 26.01.2009



Реферативные базы данных:


© МИАН, 2024