C++ Builder
| Главная | Уроки | Статьи | FAQ | Форум | Downloads | Литература | Ссылки | RXLib | Диски |

 
Нужно пербрать все графы, степень вершины ..., Помогите!
** Maximus
Отправлено: 08.05.2004, 18:34


Не зарегистрирован







Класс Graph задаётся числом вершин n (0,1,2,...,n) и матрицей смежностей [n][n]

Нужно пербрать все графы, степень каждой вершины которой равна 3.
И всё это дело занести в Базу Данных.

Никак не могу найти оптимальный алгоритм поиска НУЖНЫХ матриц.

NiGGa
Отправлено: 08.05.2004, 20:32


Не зарегистрирован







то, что не решается перебором — решается полным перебором!
exp
Отправлено: 09.05.2004, 00:14


Мастер участка

Группа: Участник
Сообщений: 304



Для начала, n может быть только четным числом, т. к. не существует графа с нечетным количеством нечетных вершин.
Поэтому здесь и далее считается, что n- четное.

Приблизительный алгоритм.
1) Расположи все вершины по окружности и соедини соседние вершины.
Тогда каждая вершина будет иметь степень 2.
2) Теперь нужно подобрать каждой вершине со степенью 2 еще одну вершину со степенью 2, чтоб их соединить. Тогда обе они становятся вершинами третьей степени.
3) Проделать операцию 2 с остальными вершинами второй степени.

Меняя способ подбора, перебираешь графы графы.

Например для 6-ти вершин существуют4 графа, удовлетворяющих твоей задаче.
Пример:
CODE

1-----2-----3
| \ \ | (еще соединены вершины 3 и 6)
6 ----5-----4

1-----2-----3
| | | (еще соединены вершины 1 и 4, 3 и 6)
6 ----5-----4

1-----2-----3
| | | (еще соединены вершины 1 и 3, 6 и 4)
6 ----5-----4

1-----2-----3
| / / | (еще соединены вершины 1 и 4)
6 ----5-----4

Т.е. ты смотришь в массив вершин, выбираешь вершину V, которой будешь искать пару, пробегаешь по оставшимся вершинам (проверяя их на соседство с вершиной V), если i-тая вершина — не сосед и имеет степень 2 то их можно связать ветвью.
Если после полного просмотра массива верщин у тебя остались 2 соседние вершины со степенями 2, то данный граф не удовлетворяет условию.
Тогда ищешь другой граф.
И так по всем графам.

Алгоритм имеет сложность O(n!).



9.05.04: Удалось узнать, что для n, кратных 4 количество графов, удовлетворяющих твоей задаче, выражается простой, но страшной формулой. (n-3)! . А это значит, что тебе следует серьезно задуматься, как ты будешь выводить свои графы, и, САМОЕ ГЛАВНОЕ (!), Куда? Извини, если расстроил cool.gif .

Отредактировано exp — 09/05/2004, 20:41

Вернуться в Вопросы программирования в C++Builder