|
|
|
Регистрация Восстановить пароль |
|||||||
| Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
||||
 |
|
|
Опции темы | Поиск в этой теме |
21.05.2010, 20:41
|
#1 |
|
Регистрация: 21.05.2010
Сообщений: 6
|
Кубический подграф
Условие. Задан граф G=<V,E>
Вопрос. Существует ли в E непустое подмножество E' такое, что в графе G'=<V,E'> любая вершина имеет степень, равную 3 или 0? Как реализовать данный алгоритм на С++? |
|
|
|
22.05.2010, 02:56
|
#2 |
|
Пользователь
Регистрация: 23.07.2009
Сообщений: 66
|
Насколько я знаю, задача о поиске кубического подграфа в графе является NP полной. Говоря по-русски: не имеет полиномиального решения, т.е. решается полным перебором. Тут перебор заключатся в следующем: каждому ребру присваиваем значение 0 или 1. потом делаем все возможные комбинации значений ребер, и каждый раз проверяем: получился ли у нас кубический граф. Итого сложность будет O(2^E)
O(n)
|
|
|
|
|
22.05.2010, 23:27
|
#3 |
|
Регистрация: 21.05.2010
Сообщений: 6
|
А как конкретно это реализовать в С++ (код алгоритма)?
|
|
|
|
|
23.05.2010, 21:18
|
#4 |
|
Пользователь
Регистрация: 23.07.2009
Сообщений: 66
|
Вы предлагаете за вас написать полный перебор?
O(n)
|
|
|
|
|
Похожие темы
|
||||
| Тема | Автор | Раздел | Ответов | Последнее сообщение |
| корень кубический | Небесный | Общие вопросы Delphi | 6 | 30.05.2010 12:50 |
| кубический корень числа | UnrealSP | Помощь студентам | 0 | 02.11.2009 18:04 |
| Кубический корень от отрицательного числа | Vito89 | Помощь студентам | 9 | 29.09.2009 14:40 |
| Подграф | RIO | Помощь студентам | 0 | 18.06.2009 17:24 |
