Clique problem (original) (raw)
المخطط الكامل هو مضلع كل رأسين فيه مرتبطان. ورتبة المخطط الكامل هو عدد رؤوسه.
| Property | Value |
|---|---|
| dbo:abstract | المخطط الكامل هو مضلع كل رأسين فيه مرتبطان. ورتبة المخطط الكامل هو عدد رؤوسه. (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) 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. The clique problem arises in the following real-world setting. Consider a social network, where the graph's vertices represent people, and the graph's edges represent mutual acquaintance. Then a clique represents a subset of people who all know each other, and algorithms for finding cliques can be used to discover these groups of mutual friends. Along with its applications in social networks, the clique problem also has many applications in bioinformatics, and computational chemistry. Most versions of the clique problem are hard. The clique decision problem is NP-complete (one of Karp's 21 NP-complete problems). The problem of finding the maximum clique is both fixed-parameter intractable and hard to approximate. And, listing all maximal cliques may require exponential time as there exist graphs with exponentially many maximal cliques. Therefore, much of the theory about the clique problem is devoted to identifying special types of graph that admit more efficient algorithms, or to establishing the computational difficulty of the general problem in various models of computation. To find a maximum clique, one can systematically inspect all subsets, but this sort of brute-force search is too time-consuming to be practical for networks comprising more than a few dozen vertices.Although no polynomial time algorithm is known for this problem, more efficient algorithms than the brute-force search are known. For instance, the Bron–Kerbosch algorithm can be used to list all maximal cliques in worst-case optimal time, and it is also possible to list them in polynomial time per clique. (en) 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) 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. Le problème de la clique apparaît dans la situation réelle suivante. Considérons un réseau social, où les sommets du graphe représentent des personnes et les arêtes représentent la connaissance mutuelle entre les personnes. Une clique représente alors un sous-ensemble de personnes qui se connaissent toutes mutuellement, et des algorithmes pour trouver des cliques peuvent être utilisés pour découvrir ces groupes d'amis communs. Outre ses applications aux réseaux sociaux, le problème de la clique a également de nombreuses applications en bioinformatique et en chimie numérique. La plupart des versions du problème de la clique sont des problèmes difficiles. Le problème décisionnel de la clique est NP-complet (l'un des 21 problèmes NP-complets de Karp). Le problème de trouver une k-clique est à la fois intraitable à paramètre fixé (il n'est pas dans la classe de problèmes FPT) et est (en). Lister toutes les cliques maximums peut nécessiter un temps exponentiel car il existe des graphes avec un nombre de cliques maximums exponentiel en le nombre de sommets. Par conséquent, une grande partie de la théorie sur le problème de la clique est consacrée à l'identification de types particuliers de graphes qui admettent des algorithmes plus efficaces, ou à l'établissement de la difficulté algorithmique du problème général dans divers modèles de calcul. Pour trouver une clique maximum, on peut inspecter tous les sous-ensembles du graphe, mais ce type de recherche exhaustive est trop long pour être utilisable dans des graphes comprenant plus de quelques dizaines de sommets. Bien qu'aucun algorithme de temps polynomial ne soit connu pour ce problème, des algorithmes plus efficaces que la recherche exhaustive sont connus. Par exemple, l'algorithme de Bron-Kerbosch peut être utilisé pour lister toutes les cliques maximums, en temps optimal dans le pire cas, et il est également possible de les lister en temps polynomial par clique. (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. Per esempio, il problema della cricca massima nasce nel seguente scenario del mondo reale. Si consideri una rete sociale, dove i vertici del grafo rappresentano le persone, e gli spigoli del grafo rappresentano le reciproche conoscenze. Per trovare un sottoinsieme più grande di persone che si conoscono tutte tra di loro, si possono ispezionare sistematicamente tutti i sottoinsiemi, un processo che consuma troppo tempo per essere pratico per reti sociali che comprendano più di qualche dozzina di persone. Sebbene questa ricerca mediante forza bruta possa essere migliorata da algoritmi più efficienti, tutti questi algoritmi impiegano un tempo esponenziale per risolvere il problema. Perciò, gran parte della teoria sul problema della cricca è dedicata a identificare tipi speciali di grafo che ammettano algoritmi più efficienti, o a stabilire la difficoltà computazionale del problema generale in vari modelli di computazione. Insieme alle sue applicazioni nelle reti sociali, il problema della cricca ha anche molte applicazioni in bioinformatica e in chimica computazionale. I problemi della cricca includono: * trovare la cricca massima (una cricca con il più grande numero di vertici), * trovare una cricca con il peso massimo in un grafo pesato, * elencare tutte le cricche massimali (cricche che non possono essere ampliate), * risolvere il problema decisionale di verificare se un grafo contiene una cricca più grande di una data dimensione. Questi problemi sono tutti difficili: il problema decisionale della cricca è NP-completo (uno dei 21 problemi NP-completi di Karp), il problema di trovare la cricca massima è sia , sia , ed elencare tutte le cricche massimali può richiedere un tempo esponenziale in quanto esistono grafi con un numero esponenziale di cricche massimali. Nondimeno, ci sono algoritmi per questi problemi che si eseguono in tempo esponenziale o che gestiscono certi grafi di entrata più specializzati in tempo polinomiale. (it) 클릭 문제 (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) 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. NP-zupełność tego problemu wynika łatwo z NP-zupełności problemu zbioru niezależnego, ponieważ w grafie istnieje klika o rozmiarze k wtedy i tylko wtedy, gdy w dopełnieniu grafu istnieje zbiór niezależny o rozmiarze k. (pl) 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. Por exemplo, o problema clique surge no cenário seguinte. Considere uma rede social, onde os vértices do grafo representam pessoas, e as arestas representam o conhecimento mútuo. Para encontrar um maior subconjunto de pessoas, em que todas conhecem umas as outras, pode-se sistematicamente inspecionar todos os subconjuntos, um processo que é muito demorado para ser prático para as redes sociais, mesmo que pequenas. Embora a pesquisa por força bruta possa ser melhorada através de algoritmos mais eficientes, todos estes algoritmos levam tempo exponencial para resolver o problema. Portanto, grande parte da teoria sobre o problema do clique é dedicado à identificação de tipos especiais de gráfo que admitem algoritmos mais eficientes, ou a definição da dificuldade computacional do problema geral em vários modelos de computação. Junto com seus aplicativos em redes sociais , o clique também tem muitas aplicações em bioinformática e química computacional. Problemas que envolvem o clique: * encontrar o clique máximo (um clique com o maior número de vértices); * encontrar o clique com maior valor em um grafo valorado; * listar todos os cliques máximos (cliques que não podem ser ampliados); * resolver o problema de decisão de testar se um grafo contém um clique maior que um tamanho determinado. Esses problemas são todos difíceis: o problema de decisão clique é NP-completo (um dos 21 problemas NP-Completo de Karp), e listar todos os cliques máximos pode exigir tempo exponencial. No entanto, existem algoritmos para esses problemas que são executados em tempo exponencial ou que lidam com grafos de entrada mais especializados em tempo polinomial. (pt) Задача о клике относится к классу 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) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Brute_force_Clique_algorithm.svg?width=300 |
| dbo:wikiPageExternalLink | http://4mhz.de/cook.html http://dimacs.rutgers.edu/Volumes/Vol26.html http://insilab.org/articles/match2007.pdf http://www.mgvis.com/Papers/MassiveDataSets/Cliques.pdf http://handle.dtic.mil/100.2/ADA247861 http://www.labri.fr/perso/robson/mis/techrep.html http://www.csc.kth.se/%7Ejohanh/monotoneclique.pdf http://www.renyi.hu/~p_erdos/1935-01.pdf https://hal.inria.fr/hal-00966509 http://research.nii.ac.jp/~uno/papers/04swat.pdf http://i.stanford.edu/pub/cstr/reports/cs/tr/76/550/CS-TR-76-550.pdf http://www.inf.u-szeged.hu/actacybernetica/edb/vol10n3/pdf/Groger_1992_ActaCybernetica.pdf http://insilab.org/maxclique http://www.cs.berkeley.edu/~luca/cs172/karp.pdf https://archive.org/details/discretemathemat0000dmtc/page/278 https://books.google.com/books%3Fid=CAm2DpIqRUIC&pg=PA276 https://web.archive.org/web/20110629023717/http:/www.cs.berkeley.edu/~luca/cs172/karp.pdf https://web.archive.org/web/20120527164352/http:/handle.dtic.mil/100.2/ADA247861 https://www.nytimes.com/1990/06/26/science/in-a-frenzy-math-enters-age-of-electronic-mail.html https://zenodo.org/record/896067 https://digital.library.unt.edu/ark:/67531/metadc1319152/ https://digital.library.unt.edu/ark:/67531/metadc709300/ |
| dbo:wikiPageID | 249254 (xsd:integer) |
| dbo:wikiPageLength | 85275 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1093311196 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Proceedings_of_the_USSR_Academy_of_Sciences dbr:Branch_and_bound dbr:Degeneracy_(graph_theory) dbr:Dense_graph dbr:Algorithm dbr:Algorithmica dbr:Approximation_algorithm dbr:Arboricity dbr:DIMACS dbr:DNA_computing dbr:Undirected_graph dbr:Decision_problem dbr:Decision_tree_model dbr:Dependency_graph dbr:Induced_subgraph dbr:Information_Processing_Letters dbr:Kuratowski's_theorem dbr:Kőnig's_theorem_(graph_theory) dbr:Adjacent_(graph_theory) dbr:Protein_structure_prediction dbc:NP-complete_problems dbr:Complete_graph dbr:Computational_complexity_of_matrix_multiplication dbr:Matching_(graph_theory) dbr:NOT_gate dbr:Social_network dbr:Partial_word dbr:Output-sensitive_algorithm dbr:Chromatic_number dbr:Glossary_of_graph_theory dbr:Glossary_of_graph_theory_terms dbr:Graph_(discrete_mathematics) dbr:Boxicity dbr:NC_(complexity) dbr:NP-complete dbr:Conjunctive_normal_form dbr:Constraint_programming dbr:Cook–Levin_theorem dbr:The_New_York_Times dbr:The_Thomson_Corporation dbr:Erdős–Rényi_model dbr:SIAM_Journal_on_Computing dbr:SIAM_Journal_on_Discrete_Mathematics dbr:Proceedings_of_the_National_Academy_of_Sciences dbr:Lexicographic_order dbr:Linear_time dbr:Big_omega_notation dbr:Stephen_Cook dbr:Clique dbr:Clique_(graph_theory) dbr:Closure_(mathematics) dbr:Combinatorica dbr:Communications_of_the_ACM dbr:Comparability_graph dbr:Complement_graph dbr:Complete_(complexity) dbr:Compositio_Mathematica dbr:Computational_chemistry dbr:Computational_complexity_theory dbr:Computer_science dbr:Hardness_of_approximation dbr:Parallel_algorithm dbr:Perfect_graph dbr:Plenum_Publishing_Corporation dbr:Probabilistically_checkable_proof dbr:Theoretical_Computer_Science_(journal) dbr:Many-one_reduction dbr:Maximum_common_induced_subgraph dbr:Acta_Mathematica dbr:Adiabatic_quantum_computation dbr:Time_complexity dbr:Travelling_salesman_problem dbr:Triangle-free_graph dbr:Truth_value dbr:Truth_values dbr:Well-covered_graph dbr:Docking_(molecular) dbr:Karp's_21_NP-complete_problems dbr:Local_search_(optimization) dbr:Spectral_graph_theory dbr:Adjacency_matrix dbr:American_Mathematical_Society dbr:And_gate dbr:Dynamic_programming dbr:Edge_(graph_theory) dbr:Evolutionary_tree dbr:Finite_set dbr:Bron–Kerbosch_algorithm dbr:Discrete_Applied_Mathematics dbr:Discrete_Mathematics_(journal) dbr:Fan-in dbr:Graph_property dbr:Israel_Journal_of_Mathematics dbr:Journal_of_Combinatorial_Theory dbr:Journal_of_Computer_and_System_Sciences dbr:Journal_of_Graph_Algorithms_and_Applications dbr:Journal_of_the_ACM dbr:Journal_of_the_American_Statistical_Association dbr:Uriel_Feige dbr:Ramsey_theory dbr:Interval_graph dbr:Backtracking dbr:Hypercube dbr:Wildcard_character dbr:Aanderaa–Karp–Rosenberg_conjecture dbr:Academic_Press dbr:Chemistry dbr:Chordal_graph dbr:Keller's_conjecture dbr:Big_O_notation dbr:Bioinformatics dbr:Bipartite_graph dbc:Computational_problems_in_graph_theory dbr:Hereditary_property dbr:Modular_product_of_graphs dbr:Automatic_test_pattern_generation dbr:BIT_Numerical_Mathematics dbr:Boolean_satisfiability_problem dbr:Bulletin_of_the_American_Mathematical_Society dbr:Planar_graph dbr:Polynomial-time_approximation_scheme dbr:Circle_graph dbr:Circuit_complexity dbr:Greedy_algorithm dbr:Polynomial_time dbr:Approximation_ratio dbr:Independent_set_problem dbr:Brute-force_search dbr:Neighborhood_(graph_theory) dbr:Real_number dbr:Longest_increasing_subsequence dbr:Maximal_element dbr:Science_(journal) dbr:Unit_disk_graph dbr:Vertex_(graph_theory) dbr:Exponential_time dbr:Exponential_time_hypothesis dbr:FP_(complexity) dbr:Discrete_and_Computational_Geometry dbr:IEEE_Transactions_on_Computers dbr:Planted_clique dbr:NP-completeness dbr:Polynomial_delay dbr:Semidefinite_programming dbr:Maximal_clique dbr:Maximum_clique dbr:Unordered_pair dbr:Permutation_graph dbr:Worst-case_analysis dbr:P_versus_NP_problem dbr:Parameterized_complexity dbr:Symposium_on_Foundations_of_Computer_Science dbr:Random_graph dbr:W(1) dbr:Or_gate dbr:Springer-Verlag dbr:Big_theta_notation dbr:P_=_NP dbr:P_≠_NP dbr:Lexicographic_ordering dbr:Systematic_Zoology dbr:Minor-closed_graph_family dbr:Heuristic_algorithm dbr:Decision_tree_complexity dbr:Information_and_Control dbr:Complement_(graph_theory) dbr:File:6n-graf-clique.svg dbr:File:Brute_force_Clique_algorithm.svg dbr:File:Cube-face-intersection-graph.svg dbr:File:Decision_tree_for_3-clique_no_arrowheads.svg dbr:File:Monotone_circuit_for_3-clique.svg dbr:File:Permutation_graph.svg dbr:File:Sat_reduced_to_Clique_from_Sipser.svg |
| dbp:wikiPageUsesTemplate | dbt:ECCC dbt:Italics_correction dbt:Citation dbt:Clear dbt:Doi dbt:Good_article dbt:Harvtxt dbt:Main dbt:Math dbt:Mvar dbt:Radic dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfnp dbt:Short_description |
| dcterms:subject | dbc:NP-complete_problems dbc:Computational_problems_in_graph_theory |
| rdf:type | yago:WikicatComputationalProblemsInGraphTheory yago:WikicatNP-completeProblems yago:Abstraction100002137 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Problem114410605 yago:State100024720 |
| 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) |
| rdfs:label | مشكلة المخطط الكامل ضمن مخطط (ar) Cliquenproblem (de) Problema del clique (es) Clique problem (en) Problème de la clique (fr) Problema della cricca (it) 最大クリーク問題 (ja) 클릭 문제 (ko) Problem kliki (pl) Problema do clique (pt) Задача о клике (ru) Задача про кліку (uk) 分團問題 (zh) |
| owl:sameAs | freebase:Clique problem yago-res:Clique problem wikidata:Clique problem dbpedia-ar:Clique problem http://bn.dbpedia.org/resource/ক্লিক_সমস্যা dbpedia-de:Clique problem dbpedia-es:Clique problem dbpedia-fr:Clique problem dbpedia-it:Clique problem dbpedia-ja:Clique problem dbpedia-ko:Clique problem dbpedia-pl:Clique problem dbpedia-pt:Clique problem dbpedia-ro:Clique problem dbpedia-ru:Clique problem dbpedia-sr:Clique problem dbpedia-th:Clique problem dbpedia-uk:Clique problem dbpedia-zh:Clique problem https://global.dbpedia.org/id/EiYJ |
| prov:wasDerivedFrom | wikipedia-en:Clique_problem?oldid=1093311196&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Sat_reduced_to_Clique_from_Sipser.svg wiki-commons:Special:FilePath/6n-graf-clique.svg wiki-commons:Special:FilePath/Brute_force_Clique_algorithm.svg wiki-commons:Special:FilePath/Cube-face-intersection-graph.svg wiki-commons:Special:FilePath/Decision_tree_for_3-clique_no_arrowheads.svg wiki-commons:Special:FilePath/Monotone_circuit_for_3-clique.svg wiki-commons:Special:FilePath/Permutation_graph.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Clique_problem |
| is dbo:wikiPageDisambiguates of | dbr:Clique_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Approximation_algorithms_for_the_clique_problem dbr:Maximum_clique_problem dbr:K-clique_problem |
| is dbo:wikiPageWikiLink of | dbr:Enumeration_algorithm dbr:List_of_computability_and_complexity_topics dbr:Dense_subgraph dbr:Approximation_algorithm dbr:List_of_graph_theory_topics dbr:Vertex_cover dbr:Dedekind–MacNeille_completion dbr:Independent_set_(graph_theory) dbr:Induced_subgraph dbr:List_of_mathematical_proofs dbr:Matroid_parity_problem dbr:Maximal_independent_set dbr:Genome_architecture_mapping dbr:Geodetic_graph dbr:Partial_word dbr:Graph_coloring dbr:Bounded_expansion dbr:Logic_of_graphs dbr:Clique_(graph_theory) dbr:Combinatorial_optimization dbr:Clique_(disambiguation) dbr:MaxCliqueDyn_maximum_clique_algorithm dbr:Maximum_common_induced_subgraph dbr:Time_complexity dbr:HCS_clustering_algorithm dbr:Karp's_21_NP-complete_problems dbr:Bron–Kerbosch_algorithm dbr:Graph_isomorphism_problem dbr:Graph_theory dbr:Isolation_lemma dbr:List_of_NP-complete_problems dbr:Quadratic_knapsack_problem dbr:Hall_violator dbr:Tolerance_graph dbr:Keller's_conjecture dbr:Coenraad_Bron dbr:Cograph dbr:Modular_product_of_graphs dbr:Boolean_satisfiability_problem dbr:Point-set_registration dbr:Circuit_complexity dbr:Approximation_algorithms_for_the_clique_problem dbr:Maximum_clique_problem dbr:Longest_increasing_subsequence dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:The_Art_of_Computer_Programming dbr:Planted_clique dbr:Subgraph_isomorphism_problem dbr:NP-completeness dbr:Pairwise_compatibility_graph dbr:Permutation_graph dbr:Set_packing dbr:Word-representable_graph dbr:K-clique_problem |
| is dbp:data of | dbr:MaxCliqueDyn_maximum_clique_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Clique_problem |
