Тогда для того, чтобы проверить имеет ли ациклический орграф корень - достаточно посчитать количество вершин, не имеющих входящих дуг. Если такая вершина одна - это и есть корень.
Или я в чем-то не прав?
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Вопрос по графам |
| Автор: denis2105 22.6.2007, 12:49 |
| Задание: Написать прог… определяющую, имеет ли данный ациклический орграф корень. Вопрос: 1: какой алгоритм применить? 2: насколько я понял, корень, это вершина от которого можно пройти ко всем вершинам, верно ли это? А если таких больше одной, то кто тогда является вершиной? |
| Автор: Shurr 22.6.2007, 14:25 |
| Ну, если я правильно помню теорию графов, то для того, чтобы ациклический орграф имел корень - он должен быть связным, т.к. из корня по определению можно достичь всех остальных вершин. Соответственно, раз из корня можно достичь всех вершин - то корень может быть только один, т.к. орграф ациклический. Тогда для того, чтобы проверить имеет ли ациклический орграф корень - достаточно посчитать количество вершин, не имеющих входящих дуг. Если такая вершина одна - это и есть корень. Или я в чем-то не прав? |