|
Cr1stal |
Помогите с задачей!  25.03.2010, 18:27 |
|
25/03/10
3
|
|
Построить детерминированную машину Тьюринга, выписывающую за полиномиальное время все компоненты связности неориентированного графа.
Какой здесь алгоритм действий????
|
|
|
|
 |
|
Xaositect |
Re: Помогите с задачей! 25.03.2010, 18:30 |
|
| Заслуженный участник |
 |
06/10/08
6422
|
|
Ну как.
Берем вершину, добавляем к ней все смежные с ней, потом смежные со смежными и т. д. пока не станет так, что не сможем ничего добавить - это получится одна компонента связности.
Если еще остались вершины, берем одну из них и так же строим ее компоненту связности.
И так далее, пока граф не кончится.
|
|
|
|
|
|
Cr1stal |
Re: Помогите с задачей! 25.03.2010, 19:09 |
|
25/03/10
3
|
|
|
|
|
|
Xaositect |
Re: Помогите с задачей! 25.03.2010, 19:47 |
|
| Заслуженный участник |
|
06/10/08
6422
|
|
А подробности зависят от того, как у Вас вводились машина Тьюринга и кодировка графов в строки.
|
|
|
|
|
  |
Страница 1 из 1
|
[ Сообщений: 4 ] |
|
Модераторы: Модераторы Математики, Супермодераторы
