Здравствуйте.

Такая задача:
Есть связный направленный граф.
Нада построить покрывающИе деревья (покрывающий лес? )
таким образом, чтобы:

1. Выбросить как можно меньше ребер.
2. Чтобы ребра во всех деревьях, которые получатся, смотрели в одну сторону (от корня к вершине)

как бы такое сделать?

Здравствуйте, Witeboragon, Вы писали:

W>1. Выбросить как можно меньше ребер.
Если это дерево значит там нет циклов а значит
у дерева строго определёное количество рёбер — ?))
Которое равно E_Count = V_Count-1

W>2. Чтобы ребра во всех деревьях, которые получатся, смотрели в одну сторону (от корня к вершине)

Здравствуйте, ё-лка, Вы писали:

ЁЛ>Здравствуйте, Witeboragon, Вы писали:

W>>1. Выбросить как можно меньше ребер.
ЁЛ> Если это дерево значит там нет циклов а значит
ЁЛ> у дерева строго определёное количество рёбер — ?))
ЁЛ> Которое равно E_Count = V_Count-1

если бы граф был ненаправленный, то так бы оно и было.
проблема в этом условии:
2). Чтобы ребра во всех деревьях, которые получатся, смотрели в одну сторону (от корня к вершине)

Например, вот такой граф:

A -> B
| ^
v |
C <- D

одним таким деревом покрыть не выходит

W>если бы граф был ненаправленный, то так бы оно и было.
W>проблема в этом условии:
W>2). Чтобы ребра во всех деревьях, которые получатся, смотрели в одну сторону (от корня к вершине)

W>Например, вот такой граф:

W> A -> B
W> | ^
W> v |
W> C <- D

W>одним таким деревом покрыть не выходит
Ну да не получитсья.
Т.е можно добавлять новые рёбра — ??

Здравствуйте, ё-лка, Вы писали:

W>>если бы граф был ненаправленный, то так бы оно и было.
W>>проблема в этом условии:
W>>2). Чтобы ребра во всех деревьях, которые получатся, смотрели в одну сторону (от корня к вершине)

W>>Например, вот такой граф:

 A -> B
 |    ^
 v    |
 C <- D

W>>одним таким деревом покрыть не выходит
ЁЛ>Ну да не получитсья.
ЁЛ>Т.е можно добавлять новые рёбра — ??

не, добавлять нельзя. зато можно вот так:

 A -> B
       
       
 C <- D

Здравствуйте, Witeboragon, Вы писали:

W>не, добавлять нельзя. зато можно вот так:

Тогла наверно можно сдедующим образо, надо пройтись и всем правильно направленым рёбрам задать вес например 1, затем всем обратоно направленым рёбрам даём вес допустим 2, и строим дерево минимального веса! Например методом Прима.
Также наверно стоит попробывать и наоборот !

зы. Хотя не знаю, может и не правильно... : )))

Здравствуйте, ё-лка, Вы писали:

ЁЛ>Здравствуйте, Witeboragon, Вы писали:

W>>не, добавлять нельзя. зато можно вот так:

ЁЛ>Тогла наверно можно сдедующим образо, надо пройтись и всем правильно направленым рёбрам задать вес например 1, затем всем обратоно направленым рёбрам даём вес допустим 2, и строим дерево минимального веса! Например методом Прима.
ЁЛ>Также наверно стоит попробывать и наоборот !

дык этот метод строит ОДНО дерево.. как же с тем самым графом в примере?
и как понять какие ребра "правильные" ?

ЁЛ>зы. Хотя не знаю, может и не правильно... : )))

спасибо за участие

Здравствуйте, Witeboragon, Вы писали:

W>дык этот метод строит ОДНО дерево.. как же с тем самым графом в примере?

W>и как понять какие ребра "правильные" ?


Выбераем корень, поиском в глубину всем рёбрам по которым прошелись ставим 1,
затем строим неоринтированый граф ( он то ориетированы, но в нём добавлены обратные рёбра там где это необходимо)
и всем оставшимся рёбрам устанавливаем 2. В этом графе ищим остовое дерево минимального веса.

Затем можно сделать всё наоборот.

Здравствуйте, ё-лка, Вы писали:

ЁЛ>Здравствуйте, Witeboragon, Вы писали:

W>>дык этот метод строит ОДНО дерево.. как же с тем самым графом в примере?

W>>и как понять какие ребра "правильные" ?


ЁЛ> Выбераем корень,

т.е. любую вершину?

ЁЛ> поиском в глубину всем рёбрам по которым прошелись ставим 1,
ЁЛ> затем строим неоринтированый граф ( он то ориетированы, но в нём добавлены обратные рёбра там где это необходимо)
ЁЛ> и всем оставшимся рёбрам устанавливаем 2. В этом графе ищим остовое дерево минимального веса.

а потом получившееся дерево раскусать на кусты, удалив "левые" ребра? или как?

ЁЛ> Затем можно сделать всё наоборот.

Здравствуйте, Witeboragon, Вы писали:

W>Здравствуйте.

W>Такая задача:
W>Есть связный направленный граф.
W>Нада построить покрывающИе деревья (покрывающий лес? )
W>таким образом, чтобы:

W>1. Выбросить как можно меньше ребер.
W>2. Чтобы ребра во всех деревьях, которые получатся, смотрели в одну сторону (от корня к вершине)

W>как бы такое сделать?

1. Пусть есть граф с N вершинами, тогда если у нас получается в лесе K деревьев, то количество ребер, оствшихся в этом лесе будет N-K. Таким образом, задача сводится к покрытию графа минимальным количеством деревьев, т.к. количество выброшеных дуг будет обратно количеству полученых деревьев.
2. Для сильносвязной компоненты графа (подграфа, из любой вершины которого достижима любая другая вершина этого подграфа) можно построить ровно одно требуемое тебе дерево, причем с корнем в любой вершине.
3. Стянем все сильносвязные компонеты графа в псевдовершины — получим ациклический граф, для которго нужно решить такую же задачу.
4. Количество получаемых деревьев для ациклического графа равна мощности его базы. База для ациклического графа состоит только из вершин, имеющих полустепень захода равную нулю.

Таким образом алгоритм следующий:
1. Ищем сильносвязные компоненты (два поиска в глюбину)
2. Выделяем сильносвязные компонеты, в которые не заходит ни одна дуга из других компонет (ИМХО — совместить с предыдущим шагом)
3. Из любой точки выделенных компонет — поиск в глубину дает нам нужные деревья

С уважением Михаил Копачев