связность графа....

← →
простак (2006-09-14 14:55) [0]

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

← →
Александр Иванов © (2006-09-14 15:15) [1]

Удалить все вершины, не упомянутые в списках связей (ребрах)

← →
простак (2006-09-14 15:45) [2]

хм... возможно я неправильно сформулировал вопрос... объясню поподробнее: дан СВЯЗНЫЙ граф, мне необходимо найти такой порядок удаления вершин из графа, чтобы при каждом удалении граф оставался СВЯЗНЫМ. Вершины должны удаляться по очереди и удаляются ВСЕ вершины в конечном счете....
Заранеее спасибо за советы.... Мне бы хотя бы схематично прикинуть как это будет выглядеть? так ли уж необходимо при каждом удалении проверять остался ли граф связным? или есть определенный алгоритм?

← →
palva © (2006-09-14 16:18) [3]

Завтра пятница. Предложите в качетве пятничной задачки.

← →
TUser © (2006-09-14 16:50) [4]

Построить остовное дерево (для примера - см. алгоритмы Крускала и Прима) и удалять листья. Если построить остовное дерево не получается - значит граф изначально не вязный.

← →
palva © (2006-09-14 16:50) [5]

Сначала из графа надо убрать некоторые РЕБРА. А именно: ищем в графе цикл и убираем из него одно ребро. Повторяем, пока не останется циклов и граф не превратится в дерево (называется остовное дерево графа). Теперь можно удалять вершины. Всякий раз удаляется вершина, которая имеет степерь 1.

Здесь трудоемко искать циклы, когда их уже осталось мало или они отсутствуют.

Для уменьшения трудоемкости можно скрестить оба этапа и делать их по очереди. Сначала удалить все вершины степени один, потом найти один цикл и удалить ребро и так повторять.

← →
простак (2006-09-14 17:18) [7]

спасибо

связность графа.... Найти похожие ветки