LINUX.ORG.RU

построение двусвязного графа

 ,


0

2

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

Алгоритм:
1) Нашли точки сочленения
2) Рассматриваем граф без них
3) Сжимаем каждую связную компоненту в вершину
4) Находим минимальное остовное дерево
5) Восстанавливаем по пунктам 2-4, что надо было сделать с исходным графом

Вопрос:
но что делать, если в графе существуют «островки» вершин, не связанные с основным графом? теперь получается так, что при вызове алгоритма при отсутствии точек артикуляции, ничего не происходит; когда же такие точки присутствуют, эти островки становятся соединёнными с основным графом. можно, конечно, отказаться от варианта достраивания уже существующего графа для обеспечения двусвязности и строить только минимальный двусвязный граф, но уж очень хочется, чтобы такая возможность существовала.



Последнее исправление: vladimirsmirnov9 (всего исправлений: 1)

Ответ на: комментарий от anonymous

Блин, не факт - что односвязный будет входит в минимальный двухсвязный. Надо как-то еще поплясать.

anonymous
()
Ответ на: комментарий от anonymous

братишка, я тебе покушать принёс я и сам бы рад так сразу всё сконденсировать да связать, но вот biconnected_components работает на основе информации о рёбрах - то есть, если у нас существуют вершины, ни с чем не связанные - ничего мы и не получим. беда, в общем. второй день думаю над этим.

vladimirsmirnov9
() автор топика

Э... я в ентих ваших грфафх-князьях-баронах не силен, унивеситетов не заканчивал, поэтому наверное и проблем не вижу.

А что сделать то надо, можно как то попроще объяснить? Что значит «обеспечить двусвязность» - вот есть граф, местами односвязный (связь A->B есть, связи B->A нету), и надо добавить недостающие связи, так?

AIv ★★★★★
()
Ответ на: комментарий от AIv

граф неориентированный, то есть A->B == B->A

A connected graph is biconnected if the removal of any single vertex (and all edges incident on that vertex) can not disconnect the graph.

vladimirsmirnov9
() автор топика
Ответ на: комментарий от vladimirsmirnov9

но вот biconnected_components работает на основе информации о рёбрах - то есть, если у нас существуют вершины, ни с чем не связанные - ничего мы и не получим

Ну это-то не принципиально: никто не мешает разбить на связные компоненты и каждую из них разбивать на двусвязные.

// Возможно в качестве «пляски» подойдет: после 1,2,3,4,5 (на этапе двусвязности) проверить ребра, добавленные на 3,4,5 - и удалить те, которые перестали быть нужными для двусвязности.

anonymous
()
Ответ на: комментарий от vladimirsmirnov9

то есть, если у нас существуют вершины, ни с чем не связанные

Ну для этого собственно и было предложено сначала провести: 3,4,5 - дабы обеспечить односвязность (biconnected_components на этом этапе еще не нужен).

anonymous
()
Ответ на: комментарий от anonymous

Ну для этого собственно и было предложено сначала провести: 3,4,5 - дабы обеспечить односвязность (biconnected_components на этом этапе еще не нужен).

3) Сжимаем каждую связную компоненту в вершину

как не нужен? информацию о связных компонентах я получаю как раз из результатов алгоритма biconnected_components, он для этого и предназначен :)

vladimirsmirnov9
() автор топика
Ответ на: комментарий от vladimirsmirnov9

Эм... разбитие на компоненты - это одно из применений поиска в глубину.

biconnected_components - относится к пунктам 1-2

он для этого и предназначен :)

Прув?

anonymous
()
Ответ на: комментарий от vladimirsmirnov9

Сначала достроить до односвязного: разбить на компоненты -> сжать в вершины -> минимальное остовное дерево  — получим набор дополнительных ребер (*).

Теперь изначальных алгоритм нормально отработает. Получится двусвязный граф. Но некоторые ребра из (*) теперь могут оказаться лишними: нужно проверять каждое (*)-ребро на необходимость его для двухсвязности.

anonymous
()
Ответ на: комментарий от anonymous

Но некоторые ребра из (*) теперь могут оказаться лишними: нужно проверять каждое (*)-ребро на необходимость его для двухсвязности.

но как? неужели перебирать все рёбра тем же biconnected_components?

vladimirsmirnov9
() автор топика
Ответ на: комментарий от vladimirsmirnov9

но как? неужели перебирать все рёбра тем же biconnected_components?

Пока не вижу эффективный способ, а ожидаемое число компонент связности может быть большим?

anonymous
()
Ответ на: комментарий от anonymous

ну, как сказать. граф со 150-200 вершинами и всевозможными способами соединения, это много или мало? мне почему-то кажется, больно жирно получится

vladimirsmirnov9
() автор топика
Ответ на: комментарий от vladimirsmirnov9

Есть такая статья: http://www.cs.utexas.edu/~vlr/papers/bi_aug.pdf

Another version of the problem is to augment a graph, with a weight assigned to each edge, to meet a connectivity requirement using a set of edges with a minimum total cost. Several related problems have been proved to be NP-complete. These results can be found in Eswaran & Tarjan 4 , Frank 5 , Frederickson & Ja'Ja' 7 , Watanabe & Nakamura 26 and Watanabe, Narita & Nakamura 29

Посмотрите, вдруг задача действительно в общем случае NP-полная.

anonymous
()
Ответ на: комментарий от vladimirsmirnov9

150-200 вершинами и всевозможными способами соединения, это много или мало?

Конечно, мало).

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.