| rdfs:comment
| - المخطط الكامل هو مضلع كل رأسين فيه مرتبطان. ورتبة المخطط الكامل هو عدد رؤوسه. (ar)
- Das Cliquenproblem (mit CLIQUE notiert) ist ein Entscheidungsproblem der Graphentheorie.Das Cliquenproblem ist eines der 21 klassischen NP-vollständigen Probleme, deren Zugehörigkeit zu dieser Klasse Richard M. Karp 1972 bewies. (de)
- En complejidad computacional, el problema del clique (a veces también traducido desde el inglés como problema del clan o problema de la camarilla), es un problema NP-completo según la Teoría de la complejidad computacional. (es)
- 클릭 문제 (clique problem)는 NP완전인 그래프 이론에 등장하는 문제이다. 이 문제는 리처드 카프가 1972년 논문에서 NP완전임을 증명한 21문제 중의 하나일 뿐만 아니라, NP완전 문제 이론을 소개한 쿡의 논문에서도 언급된 유명한 문제이다. 그래프의 클릭(clique)이란 부분그래프이면서 그래프의 임의의 두 노드가 서로 연결된 것으로 정의된다. 즉, 완전 그래프인 부분그래프를 클릭이라 한다. 오른쪽 그림에서 노드 1, 2, 5로 이루어진 부분그래프는 클릭이 된다. 왜냐하면, 각 노드가 모든 나머지 노드와 연결되어 있기 때문이다. 반면 2, 5, 3으로 이루어진 그래프를 보면, 5와 3이 연결되어 있지 않아 클릭이 되지 못한다. (ko)
- 最大クリーク問題（さいだいクリークもんだい）は、グラフ理論において、グラフ中のクリーク（任意の二頂点間に枝があるような頂点集合）の中で最大のものを見つける問題。NP困難であることが知られている。 この問題は、補グラフに対する最大独立集合問題と等価である。 近似アルゴリズムについても研究されているが、グラフの頂点数を n とするとき、近似度 O(n / (log n)2) が達成されているのみである。また、P = NP が成り立たないとき、任意の ε > 0 について、近似度 n1/2 − ε の近似アルゴリズムが存在しないことが示されている。NP = ZPP が成り立たない場合、近似度 n1 − ε の近似アルゴリズムが存在しないことも示されている。 (ja)
- Задача о клике относится к классу NP-полных задач в области теории графов. Впервые она была сформулирована в 1972 году Ричардом Карпом. Кликой в неориентированном графе называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это полный подграф первоначального графа. Размер клики определяется как число вершин в ней. Задача о клике существует в двух вариантах: в задаче распознавания требуется определить, существует ли в заданном графе G клика размера k, в то время как в вычислительном варианте требуется найти в заданном графе G клику максимального размера. (ru)
- Задача про кліку відноситься до класу NP-повних задач в області теорії графів. Вперше вона була сформульована у 1972 році Річардом Карпом. Клікою в неорієнтованому графі називається підмножина вершин, кожні дві з яких з'єднані ребром графу. Іншими словами, це повний підграф первісного графу. Розмір кліки визначається як число вершин в ній. Задача про кліку існує у двох варіантах: у задачі розпізнавання потрібно визначити, чи існує в заданому графі G кліка розміру k, тоді як в обчислювальному варіанті потрібно знайти в заданому графі G кліку максимального розміру або всі максимальні кліки (такі, що не можна збільшити). (uk)
- 在計算複雜度理論中，分團問題（clique problem）是圖論中的一個NP完全（NP-complete）問題。 团（clique）是一個圖中兩兩相鄰的一個頂點集，或是一個完全子圖（complete subgraph），如右圖中的1、2、5三個頂點。 分团问题是問一個圖中是否有大小是k以上的团。任意挑出k個點，我們可以簡單的判斷出這k個點是不是一個团，所以這個問題屬於NP。 證明這問題是NP完備，我們可以很簡單的將(Independent set problem)歸約成這個問題。因為存在一個大小是k以上的分團，等價於它的補圖中存在一個大小是k以上的獨立集。 (zh)
- In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique (a clique with the largest possible number of vertices), finding a maximum weight clique in a weighted graph, listing all maximal cliques (cliques that cannot be enlarged), and solving the decision problem of testing whether a graph contains a clique larger than a given size. (en)
- En informatique, le problème de la clique est un problème algorithmique qui consiste à trouver des cliques (sous-ensembles de sommets d'un graphe tous adjacents les uns aux autres, également appelés sous-graphes complets) dans un graphe. Ce problème a plusieurs formulations différentes selon les cliques et les informations sur les cliques devant être trouvées. Les formulations courantes du problème de la clique incluent la recherche d'une clique maximum (une clique avec le plus grand nombre possible de sommets), la recherche d'une clique de poids maximal dans un graphe pondéré, la liste de toutes les cliques maximums et la résolution du problème de décision consistant à déterminer si un graphe contient une clique plus grande qu'une taille donnée. (fr)
- In informatica, il problema della cricca si riferisce a uno qualsiasi dei problemi legati alla ricerca di particolari sottografi completi ("cricche") in un grafo, cioè, insiemi di elementi dove ciascuna coppia di elementi è connessa. I problemi della cricca includono: (it)
- Em ciência da computação, o problema do clique refere-se a qualquer problema que possui como objetivo encontrar subgrafos completos ("cliques") em um grafo. Como exemplo, o problema de encontrar conjuntos de nós em que todos os elementos estão conectados entre si. Problemas que envolvem o clique: (pt)
- Problem kliki – jeden z pierwszych zidentyfikowanych problemów NP-zupełnych. Klika w grafie jest zbiorem wierzchołków, w którym każda para wierzchołków jest połączona krawędzią, czyli zbiorem, który indukuje podgraf będący grafem pełnym. Problem kliki polega na stwierdzeniu, czy w danym grafie istnieje klika o podanym rozmiarze k. Mając podane wierzchołki należące do takiej kliki, możemy trywialnie stwierdzić, że tworzą one klikę, dlatego problem ten należy do klasy NP. Odpowiadający mu problem optymalizacyjny, problem maksymalnej kliki, polega na wskazaniu maksymalnych klik w podanym grafie. (pl)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)