Вниз
Скачать: CL | DM;

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

← →
простак   (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.

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


← →
palva ©   (2006-09-14 16:54) [6]

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


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

спасибо



Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.45 MB
Время: 0.031 c
2-1159904904
Lelja
2006-10-03 23:48
2006.10.22
размещение справки в проге


4-1149174929
salexn
2006-06-01 19:15
2006.10.22
Измерить скорость чтения диска


15-1159856612
term1t
2006-10-03 10:23
2006.10.22
как спасти флешку?


2-1159702149
Фиббоначи
2006-10-01 15:29
2006.10.22
Последовательность Фиббоначи


11-1131453880
XProger
2005-11-08 15:44
2006.10.22
Минимальная DLL




   Наверх