Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

08.03.2012, 16:25. Просмотров 2326. Ответов 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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.03.2012, 16:25
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти наибольшую клику в заданном орграфе, используя алгоритм нахождения независимых множеств (C (СИ)):

Нахождения цикла в орграфе - C++
Задан орграф списком смежности, при этом его вершинами являются строчные латинские символы. Описание выглядит примерно так: &lt;описание...

Найти наибольшую цифру в заданном числе - C++
Заранее спасибо! Найти наибольшее цифру в заданном числе N

Найти наибольшую цифру в заданном целом числе N - C++
найти наибольшую цифру в заданном целом числе N С++(оч много лаб,просто не успеваю)

найти наибольшую цифру в заданном целом числе N - C++
Задача:Нужно найти наибольшую цифру в заданном целом числе N. Надо составить блок схему.Заранее спасибо

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

Генерация всех максимальных независимых множеств графа - C++
Здравствуйте,обращаюсь к вам по поводу задания своей курсовой работы по дискретной математике- генерация всех максимальных независимых...

5
valeriikozlov
Эксперт С++
4676 / 2502 / 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;
}
2
Betokuha
32 / 29 / 9
Регистрация: 05.03.2012
Сообщений: 114
08.03.2012, 18:14  [ТС] #3
Спасибо огромное
Какой алгоритм использовали для нахождения независимых множеств?
Алгоритм Магу-Уйсмана?
0
valeriikozlov
Эксперт С++
4676 / 2502 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.03.2012, 18:41 #4
Цитата Сообщение от Betokuha Посмотреть сообщение
Какой алгоритм использовали для нахождения независимых множеств?
сам придумал, но вполне возможно что совпадает с алгоритмом Магу-Уйсмана.
1
Betokuha
32 / 29 / 9
Регистрация: 05.03.2012
Сообщений: 114
08.03.2012, 18:44  [ТС] #5
Спасибо выручил
0
to-z
2 / 2 / 1
Регистрация: 05.03.2016
Сообщений: 38
29.12.2016, 08:29 #6
valeriikozlov, что хранится в переменной i_end, N и N_res?
0
29.12.2016, 08:29
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.12.2016, 08:29
Привет! Вот еще темы с ответами:

Используя базовые элементарные структуры, составьте алгоритм нахождения значений функции - Pascal ABC
(Ссылка на сторонний ресурс удалена)

В заданном массиве вещественных чисел найти наибольшую длину цепочки стоящих рядом знакочередующихся элементов - C#
Составить проект, в котором нужно описать метод обработки одномерных массивов. Результаты работы метода передавать параметрами.Написать...

В заданном массиве вещественных чисел найти наибольшую длину цепочки стоящих рядом знакочередующихся элементов - C#
В заданном массиве вещественных чисел найти наибольшую длину цепочки стоящих рядом знакочередующихся элементов(на с#).

Найти наибольшую высоту треугольника, если известно координаты его вершин, используя функцию или процедуру - Pascal
Найти наибольшую высоту треугольника, если известно координаты его вершин, используя функцию или процедуру.


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

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

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