Описание тега clique-problem
В информатике проблема клики относится к любой из проблем, связанных с поиском определенных полных подграфов ("клик") в графе, т. Е. Наборов элементов, в которых каждая пара элементов связана.
2
ответа
Доказательство NP-полноты клика + независимый граф набора
"Докажите, что NP-Complete определяет заданные входные данные G и k, имеет ли G как клику размера k, так и независимый набор размера k. Обратите внимание, что это 1 проблема, а не 2; ответ - да, если и только если G имеет оба этих подмножества." Нам…
12 ноя '10 в 01:54
1
ответ
Поиск всех кликов неориентированного графа
Как я могу перечислить все клики неориентированного графа? (Не все максимальные клики, как алгоритм Брон-Кербоша)
23 июн '16 в 18:33
2
ответа
Реализация алгоритма Брон-Кербоша в python
Для проекта колледжа я пытаюсь реализовать алгоритм Брон-Кербоша, то есть перечислять все максимальные клики в данном графе. Я пытаюсь реализовать первый алгоритм (без поворота), но мой код не дает всех ответов после тестирования его на примере Вики…
16 дек '12 в 19:14
1
ответ
Bron-Kerbosch C реализация
У меня возникли проблемы с реализацией C-версии алгоритма Брон-Кербоша: 1- Я абсолютно не понимаю, как работает алгоритм. Я пытался найти ссылки в интернете, но все они безрассудны из-за ужасных реализаций примера algol и без объяснения каких-либо ф…
01 янв '13 в 22:47
1
ответ
Эффективный алгоритм зацикливания на всех соседних парах (2 точечных клика) в двумерном массиве
Мне нужно перебрать все (неупорядоченные) пары пикселей в изображении, которые являются соседями друг с другом без повторения. Я использую 8-балльную окрестность. Например: x,y| 0 1 2 3 4 ---+---+---+---+---+---+ 0 | | | | | | +---+---+---+---+---+ …
05 окт '14 в 00:42
1
ответ
Класс NP, проверка за полиномиальное время КЛИК
Задача CLIQUE - задача определения максимальной клики в графе является NP-полной. То есть КЛИК является a.) в NP и b.) существует проблема полного NP, 3-SAT для одного, которая сводится к CLIQUE за полиномиальное время. Часть (b) выше в порядке - вс…
02 окт '13 в 22:33
1
ответ
Использование рекурсивного метода для клики
Я пытаюсь решить проблему клики. Я использую алгоритм Bron Kerbosch Clique, который хорошо написан на Java, и умную реализацию можно найти здесь. Тем не менее, благодаря жесткости клики, он может быть очень медленным, Я хочу использовать начальный н…
16 янв '15 в 21:41
1
ответ
Как написать C++ версию Python-функции powerset
Я хочу написать алгоритм максимальной клики для использования с матрицей смежности. Я следую за видео, которое объясняет, как кодировать и реализовывать алгоритм с использованием Python. В настоящее время я пытаюсь закодировать функцию powerset чере…
06 апр '14 в 18:29
0
ответов
Функция Networkx не работает в Pyspark
Я пытаюсь сделать так, чтобы графовая функция networkx могла работать в распределенной среде pyspark, но я понятия не имею, как преобразовать ее в RDD или другую выполняемую функцию networkx в распределенной среде spark. Вот часть моего кода на Pyth…
07 ноя '17 в 03:28
2
ответа
Алгоритм краевого клика
Я пытаюсь написать алгоритм, который вычисляет номер покрытия клики ребер (наименьшее число клик, которые охватывают все ребра) входного графа (ненаправленный и без самопетлей). Моя идея была бы Рассчитать все максимальные клики с помощью алгоритма …
06 мар '18 в 17:55
2
ответа
Сортировка строк и столбцов матрицы смежности для выявления кликов
Я ищу способ переупорядочения для группировки связанных компонентов матрицы смежности вместе. Например, я сделал иллюстрацию с двумя группами, синим и зеленым. Первоначально записи "1" распределяются по строкам и столбцам матрицы. Переупорядочив стр…
29 май '15 в 16:01
2
ответа
Является ли дополнение языка CLIQUE элементом NP?
Я изучаю класс NP и один из слайдов упоминает: It seems that verifying that something is not present is more difficult than verifying that it is present. ______ _________ Hence, CLIQUE (complement) and SubsetSUM (complement) are not obviously member…
16 янв '16 в 00:41
0
ответов
Сведение к клике
Подграф изоморфизма У нас есть графики G_1=(V_1,E_1), G_2=(V_2,E_2). Вопрос: граф G_1 изоморфен подграфу G_2? (т. е. существует ли подмножество вершин G_2, V ⊆ V_2 и подмножество ребер G_2, E ⊆ E_2 такое, что |V|=|V_1| и |E|=|E_1| и существует ли од…
17 апр '15 в 18:23
2
ответа
Генератор случайных списков смежности
В настоящее время я работаю над разработкой приложения, чтобы найти максимальный клик на графике для моего проекта за последний год. У меня большая часть проекта завершена, и я только начинаю тестировать приложение. В настоящее время приложение испо…
03 авг '12 в 12:27
1
ответ
Найти все группы соседних узлов графа
У меня есть график и это узлы смежной матрицы. Проблема заключается в том, чтобы найти все узлы, смежные "все ко всем". Например (на картинке) результат должен быть [1,2,3,7] все эти узлы соединены вместе. Для любого вида графа мне нужно получить сп…
14 июл '15 в 09:32
0
ответов
Учитывая набор интервалов на числовой линии, найдите минимальные точки, которые "покрывают" все интервалы (эффективное решение оптимально)?
Я пытался найти эффективный способ решить эту проблему - найти "минимальные" (не минимальные) временные точки, но не уверен, что это так просто. Я попытался смоделировать ее как задачу минимального покрытия ребер (полиномиальная временная сложность …
21 дек '18 в 19:12
1
ответ
Найти клики длины k в графе
Я работаю с графиками ~200 узлов и ~3500 ребер. Мне нужно найти все клики этого графа. Использование сети enumerate_all_cliques() отлично работает с меньшими графиками до 100 узлов, но не хватает памяти для больших. "Однако этот алгоритм, надеемся, …
02 июн '15 в 15:32
2
ответа
Проблема алгоритма
Граф - это подграф графа, в котором любая вершина связана с остальными вершинами. В задаче k вход является неориентированным графом и числом k, а выход - размером clof k, если таковой существует (или, иногда, всем cl размера k)
01 янв '10 в 17:32
1
ответ
Создать матрицу смежности для заданных соединений узлов
Я хочу создать матрицу смежности с n строками, представляющими частичную связь между некоторыми узлами графа. Например, из-за того, что каждая строка представляет клику, строки A-B; B-C; C-D; A-E-D сформировать следующий график. Мой первый подход бы…
22 апр '18 в 01:47
2
ответа
Почему метод igraph cliques() на несколько порядков медленнее, чем justTheCliques?
Я хотел найти все клики в графе среднего размера, но плотно связанном, имеющем 369 узлов и 22 724 ребер. Сначала я просто назвал igraph's Graph.cliques() Метод через интерфейс Python: cliques = graph.cliques() Он все еще работает и потребляет более …
03 сен '14 в 15:26