| ** 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)! . А это значит, что тебе следует серьезно задуматься, как ты будешь выводить свои графы, и, САМОЕ ГЛАВНОЕ (!), Куда? Извини, если расстроил  .
Отредактировано exp — 09/05/2004, 20:41
|
|
|
