Форум программистов, компьютерный форум CyberForum.ru

C для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.69
Betokuha
32 / 29 / 9
Регистрация: 05.03.2012
Сообщений: 114
#1

Найти наибольшую клику в заданном орграфе, используя алгоритм нахождения независимых множеств - C (СИ)

08.03.2012, 16:25. Просмотров 2133. Ответов 5
Метки нет (Все метки)

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

Сам метод: Клика

Антиподом понятия независимого множества является понятие клики.
Подмножество U вершин графа G называется кликой, если любые две входящие в него вершины смежны, т.е. если порожденный подграф G(U) является полным.
Клика называется максимальной, если она не содержится в клике с большим числом вершин, и наибольшей, если число вершин в ней наибольшее среди всех клик.
Число вершин в наибольшей клике графа G называется его плот-ностью (или кликовым числом) и обозначается через (G). Как и в случае независимых множеств, максимальная клика графа может оказаться не наибольшей.
Понятие клики, в частности максимальной клики, используется в различных социологических теориях ( вопросы, связанные с голосованием, альянсами и т.п.), а также в теории игр.
Очевидно следующее утверждение: подмножество вершин графа G является кликой тогда и только тогда, когда оно является независимым множеством в дополнительном графе G*.



Вот то, что я начал писать:
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
#include <stdio.h>
#include <conio.h>
 
#define M 120
 
int n, g[M][M], f[M][M];
int main()
{
    printf("Vvedite n= %d", n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            printf("%d", g[i][j]);
 
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &g[i][j]);
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (g[i][j] == 0)
                g[i][j] = 1;
            else
                g[i][j] = 0;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            printf(" %d \n", g[i][j]);
 
    getch();
 
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.03.2012, 16:25     Найти наибольшую клику в заданном орграфе, используя алгоритм нахождения независимых множеств
Посмотрите здесь:

Найти НОД двух целых положительных чисел А и В, используя алгоритм Евклида C (СИ)
Исследовать алгоритм нахождения Эйлерова пути в неориентированном графе C (СИ)
C (СИ) Алгоритм нахождения простых чисел
Алгоритм нахождения Эйлерова цикла C (СИ)
C (СИ) Алгоритм нахождения квадратного корня
Записать алгоритм нахождения канторового разложения произвольного числа а C (СИ)
Построить алгоритм нахождения k-го наибольшего элемента в последовательности из n элементов C (СИ)
C (СИ) Найти наибольшую дробь
C (СИ) Алгоритм нахождения простого числа
C (СИ) Бинарный алгоритм нахождения НОД
Алгоритм для нахождения слов-серий в строке C (СИ)
Найти НОД для одномерного массива, используя алгоритм Евклида C (СИ)

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.03.2012, 18:08     Найти наибольшую клику в заданном орграфе, используя алгоритм нахождения независимых множеств #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
#include <stdio.h>
#include <conio.h>
 
#define M 120
 
int n,g[M][M],Res[M], N_res, Q[M], i_end;
 
void rec(int ii, int N)
{
    int i, j;
    if(N>N_res)
    {
        for(i=0; i<i_end; i++)
            Res[i]=Q[i];
        N_res=N;
    }
    if(ii==n)
        return;
    for(i=ii; i<n; i++)
    {       
        for(j=0; j<i_end; j++)
            if(g[Q[j]][i]==0)
                break;
        if(j==i_end)
        {
            Q[i_end++]=i;
            rec(ii+1, N+1);
            i_end--;
        }
        rec(ii+1, N);
    }
}
 
int main()
{
 printf("Vvedite n= ",n);
 scanf("%d",&n);
 int i;
 for(i=0;i<n;i++)
     for(int j=0;j<n;j++)
         scanf("%d",&g[i][j]);   
for(i=0;i<n;i++)
    for(int j=0;j<n;j++)
        if (g[i][j]==1) g[j][i]=1;
for(i=0;i<n;i++)
{
    for(int j=0;j<n;j++)
        printf(" %d",g[i][j]);
    printf("\n");
}
for(i=0; i<n; i++)
{
    i_end=0; 
    rec(i, 0);
}
printf("Max klik:\n");
for(i=0; i<N_res; i++)
    printf("%d ", Res[i]);
getch();
return 0;
}
Betokuha
32 / 29 / 9
Регистрация: 05.03.2012
Сообщений: 114
08.03.2012, 18:14  [ТС]     Найти наибольшую клику в заданном орграфе, используя алгоритм нахождения независимых множеств #3
Спасибо огромное
Какой алгоритм использовали для нахождения независимых множеств?
Алгоритм Магу-Уйсмана?
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.03.2012, 18:41     Найти наибольшую клику в заданном орграфе, используя алгоритм нахождения независимых множеств #4
Цитата Сообщение от Betokuha Посмотреть сообщение
Какой алгоритм использовали для нахождения независимых множеств?
сам придумал, но вполне возможно что совпадает с алгоритмом Магу-Уйсмана.
Betokuha
32 / 29 / 9
Регистрация: 05.03.2012
Сообщений: 114
08.03.2012, 18:44  [ТС]     Найти наибольшую клику в заданном орграфе, используя алгоритм нахождения независимых множеств #5
Спасибо выручил
to-z
2 / 2 / 1
Регистрация: 05.03.2016
Сообщений: 37
29.12.2016, 08:29     Найти наибольшую клику в заданном орграфе, используя алгоритм нахождения независимых множеств #6
valeriikozlov, что хранится в переменной i_end, N и N_res?
Yandex
Объявления
29.12.2016, 08:29     Найти наибольшую клику в заданном орграфе, используя алгоритм нахождения независимых множеств
Ответ Создать тему
Опции темы

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