Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
extrimally
6 / 6 / 2
Регистрация: 22.09.2012
Сообщений: 212
1

Алгоритм нахождения ВСЕХ ободов в графе

09.06.2013, 09:20. Просмотров 665. Ответов 1
Метки нет (Все метки)

Дан связанный граф (не менее 16 вершин), нужно найти все подграфы, являющиеся ободами.

(Обод – это граф, вершины которого V0,V1,…,Vn (n>=2) можно занумеровать так, что для всех i (1 <= i <= n-1) вершина Vi соединена с Vi-1 и Vi+1, вершина V0 с вершиной Vn и других ребер нет)
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.06.2013, 09:20
Ответы с готовыми решениями:

Алгоритм поиска всех деревьев в графе
Имеется граф. Необходимо найти множество всех деревьев. Где дерево это минимальная неизбыточная...

Алгоритм Нахождения всех булевых функций от четырёх перемнных
помогите найти оптимальный алгоритм для нахождения всех булевых функций от четырех переменных, и...

Алгоритм нахождения всех трехзначных чисел, сумма кубов цифр которых больше 89
Люююююди спасииите, не решить задачу :( Помоги те плизз если кто разбиратся в этом, завтра зачет...

Прохождение игры-числового паззла в виде нахождения оптимального пути в графе
На всякий случай сразу упомяну. В эту тему я буду заглядывать минимум неделю с момента публикации...

Алгоритм оптимального расположения на графе
Дан неориентированый граф. Необходимо вычислить, какие узлы отмечать, так, что бы расстояние до...

1
NurlashKO
89 / 89 / 80
Регистрация: 07.10.2012
Сообщений: 145
11.06.2013, 22:20 2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/*
Решил за О(2^n * n^2).
Я считаю что ребра в графе не ориентированы.
Читаю я его матрицей смежности.
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
#define sz 100
#define for(xx1 , yy1 , zz1) for(int zz1 = xx1 ; zz1 <= yy1 ; zz1++)
 
int a[sz][sz], g[sz], c, d[sz], n, cnt;
bool was[sz], f;
 
void dfs(int v)
{
    c++;
    was[v] = true;
    for (1, cnt, i)
        if (a[v][d[i]] && !was[d[i]])
            dfs(d[i]);
}
 
int main(){
    cin >> n;
        //Чтение графа
    for (1, n, i)
        for (1, n, j)
            cin >> a[i][j];
        //Перебираю подмножество вершин
    for (1, (1 << n) - 1, mask)
    {
        cnt = 0;
        f = true;
        for (0, n - 1, i)
        {
            if (mask & (1 << i))
                d[++cnt] = i + 1;//Выписал вершины которые хочу проверить
            was[i + 1] = false;
        }
        if (cnt < 2)// Если их меньше 2 то ответа нет.
            f = false;
        if (cnt == 2)//Если их две то в моей реализации это надо рассмотреть как частный случай
        {
            if (a[d[1]][d[2]]) //если они связаны, то это обод.
            {
                cout << d[1] << " " << d[2] << endl;
                continue;
            }
        }
 
        for (1, cnt, i)
            for (1, cnt, j)
                if (a[d[i]][d[j]])//Считаем степень каждой вершины
                    g[i]++;
 
        for (1, cnt, i)
        {
            if (g[i] != 2)//Если степень вершины не равна 2 то это не обод.
                f = false;
            g[i] = 0;//заодно обнуляем.
        }
        c = 0;
        dfs(d[1]);//просто проверяем этот выписанный подграф на связность
        if (f && c == cnt) // Если степень каждой вершины равна 2 и этот граф связный то это обод, выводим ответ.
        {
            for (1, cnt, i)
                cout << d[i] << " ";
            cout << endl;
        }
    }
        return 0;
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.06.2013, 22:20

Алгоритм поиска слова в заданном Графе
Доброго времени суток. Может быть кто-то, когда-то писал такой алгоритм, для поиска слова в...

Алгоритм поиска элементарных циклов в неориентированном графе
Необходимо граф разбить на элементарные циклы, то есть такие циклы, которые не имею внутри...

Реализовать алгоритм А* для поиска оптимального пути из начальной вершины в конечную на графе
Привет Нужно реализовать этот алгоритм для поиска оптимального пути из начальной вершины в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru