Первая страница / Визуализаторы / Графы. Потоки и паросочетания /

Минимальное покpытие пyтями

Голосование: 228, 193

Покрытием путями ориентированного графа G=(V,E) назовем множество всех путей P с таким свойством: каждая вершина из V принадлежит ровно одному пути из P. Пyть длины k из вершины u в вершину v определяется как последовательность вершин <v0,v1,…,vk >, в которой v0=u, vk=v и (vi-1,vi)?E) для всех i=1,2,…,k.

Пути могут начинаться и заканчиваться где угодно и иметь любую длину, в том числе и нулевую. Покрытие наименьшим возможным числом путей назовем минимальным покрытием путями.

Запустить визуализатор

Автор визуализатора: Карпец Алексей


Алексей / 2008-07-09 11:38:05

В Примере 1 на Шаге 6 : ответ - количество путей 3, хотя их вроде 2....

Ошибка или я не прав?

Вы правы. Из формализма определения следует, что в данном примере минимальное покрытие составляют пути (1, 2, 3) и (4, 5). Примененный потоковый алгоритм обнаружил 3 дуги, а потом надо бы еще проверить, какие из них входят в общие пути.

Алексей / 2009-09-27 14:32:33

не на самом деле я не прав :) потому что вершина 6 тоже принадлежит пути. Просто это вырожденный путь состоящий из одной вершины.

Иван / 2010-03-25 07:33:18

В описании сверху сказано "Пути могут начинаться и заканчиваться где угодно и иметь любую длину, в том числе и нулевую."

В первом примере вершина 6 является путем нулевой длины... Только, наверное, стоило её тоже выделять цветом)

А вообще, удобный визуализатор!

Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий