Найти наибольшую клику в заданном орграфе, используя алгоритм нахождения независимых множеств - C (СИ)
Формулировка задачи:
Помогите написать программу в С. Найти наибольшую клику в заданном орграфе, используя алгоритм нахождения независимых множеств
Сам метод: Клика
Антиподом понятия независимого множества является понятие клики.
Подмножество U вершин графа G называется кликой, если любые две входящие в него вершины смежны, т.е. если порожденный подграф G(U) является полным.
Клика называется максимальной, если она не содержится в клике с большим числом вершин, и наибольшей, если число вершин в ней наибольшее среди всех клик.
Число вершин в наибольшей клике графа G называется его плот-ностью (или кликовым числом) и обозначается через (G). Как и в случае независимых множеств, максимальная клика графа может оказаться не наибольшей.
Понятие клики, в частности максимальной клики, используется в различных социологических теориях ( вопросы, связанные с голосованием, альянсами и т.п.), а также в теории игр.
Очевидно следующее утверждение: подмножество вершин графа G является кликой тогда и только тогда, когда оно является независимым множеством в дополнительном графе G*.
Вот то, что я начал писать:
#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; }
Решение задачи: «Найти наибольшую клику в заданном орграфе, используя алгоритм нахождения независимых множеств»
textual
Листинг программы
#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; }
Объяснение кода листинга программы
В этом коде реализован алгоритм поиска наибольшей независимой множества подмножеств, используя язык программирования C. Список действий, которые выполняются в коде:
- Ввод данных: Вводится значение переменной
n
, которое представляет собой количество вершин в графе. Затем, с помощью цикла, вводятся значения матрицыg
, представляющей собой граф. - Обработка графа: В этом блоке кода матрица
g
заполняется значениями, соответствующими верхней треугольной части матрицы. Это делается для удобства работы с алгоритмом поиска независимых множеств. - Вывод матрицы g: С помощью цикла и функции
printf
выводятся значения матрицыg
. Это делается для проверки входных данных. - Реализация алгоритма поиска наибольшей независимой множества: Этот блок кода реализует рекурсивную функцию
rec
, которая ищет наибольшую независимую множества. - Вывод результата: С помощью цикла и функции
printf
выводятся значения наибольшей независимой множества. - Ввод-вывод: В этом блоке кода происходит ввод значения переменной
n
и вывод сообщенияMax klik:
. - Завершение программы: Программа завершается с помощью функции
getch
, которая ожидает нажатия клавиши. Переменные, используемые в коде: n
: Количество вершин в графе.g[i][j]
: Значение (0 или 1) в матрицеg
, представляющей собой граф.Res[i]
: Значение (вершина) из наибольшей независимой множества.N_res
: Количество вершин в наибольшей независимой множества.Q[i]
: Вершина, которую нужно рассмотреть в текущем подмножестве.i_end
: Индекс последнего элемента в массивеQ
.M
: Размер матрицыg
.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д