Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

связность графа.... [D7, WinXP]

простак © (2006-09-14 14:55:00)
Не подскажете, как можно удалить все вершины из графа не нарушая его связности. Граф можно представить в любом виде.

простак (2006-09-14 17:18:00) [1]
спасибо

palva (2006-09-14 16:54:00) [2]
Для уменьшения трудоемкости можно скрестить оба этапа и делать их по очереди. Сначала удалить все вершины степени один, потом найти один цикл и удалить ребро и так повторять.

TUser (2006-09-14 16:50:00) [3]
Построить остовное дерево (для примера - см. алгоритмы Крускала и Прима) и удалять листья. Если построить остовное дерево не получается - значит граф изначально не вязный.

palva (2006-09-14 16:50:00) [4]
Сначала из графа надо убрать некоторые РЕБРА. А именно: ищем в графе цикл и убираем из него одно ребро. Повторяем, пока не останется циклов и граф не превратится в дерево (называется остовное дерево графа). Теперь можно удалять вершины. Всякий раз удаляется вершина, которая имеет степерь 1.

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

palva (2006-09-14 16:18:00) [5]
Завтра пятница. Предложите в качетве пятничной задачки.

простак (2006-09-14 15:45:00) [6]
хм... возможно я неправильно сформулировал вопрос... объясню поподробнее: дан СВЯЗНЫЙ граф, мне необходимо найти такой порядок удаления вершин из графа, чтобы при каждом удалении граф оставался СВЯЗНЫМ. Вершины должны удаляться по очереди и удаляются ВСЕ вершины в конечном счете....
Заранеее спасибо за советы.... Мне бы хотя бы схематично прикинуть как это будет выглядеть? так ли уж необходимо при каждом удалении проверять остался ли граф связным? или есть определенный алгоритм?

Александр Иванов (2006-09-14 15:15:00) [7]
Удалить все вершины, не упомянутые в списках связей (ребрах)

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »