This HTML5 document contains 293 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbthttp://dbpedia.org/resource/Template:
n30http://handle.dtic.mil/100.2/
n53http://bn.dbpedia.org/resource/
n7https://archive.org/details/discretemathemat0000dmtc/page/
wikipedia-enhttp://en.wikipedia.org/wiki/
n23http://research.nii.ac.jp/~uno/papers/
dbrhttp://dbpedia.org/resource/
n37https://www.nytimes.com/1990/06/26/science/
dbpedia-arhttp://ar.dbpedia.org/resource/
n47http://www.mgvis.com/Papers/MassiveDataSets/
n57http://dimacs.rutgers.edu/Volumes/
n12http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-frhttp://fr.dbpedia.org/resource/
dctermshttp://purl.org/dc/terms/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n35http://insilab.org/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n27https://web.archive.org/web/20110629023717/http:/www.cs.berkeley.edu/~luca/cs172/
n22http://i.stanford.edu/pub/cstr/reports/cs/tr/76/550/
n19http://dbpedia.org/resource/File:
dbphttp://dbpedia.org/property/
xsdhhttp://www.w3.org/2001/XMLSchema#
dbpedia-ukhttp://uk.dbpedia.org/resource/
dbpedia-srhttp://sr.dbpedia.org/resource/
dbohttp://dbpedia.org/ontology/
n8http://insilab.org/articles/
n21https://books.google.com/
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-jahttp://ja.dbpedia.org/resource/
dbchttp://dbpedia.org/resource/Category:
dbpedia-plhttp://pl.dbpedia.org/resource/
dbpedia-dehttp://de.dbpedia.org/resource/
n39http://www.renyi.hu/~p_erdos/
dbpedia-thhttp://th.dbpedia.org/resource/
n5https://digital.library.unt.edu/ark:/67531/metadc709300/
n4https://digital.library.unt.edu/ark:/67531/metadc1319152/
dbpedia-ruhttp://ru.dbpedia.org/resource/
yagohttp://dbpedia.org/class/yago/
dbpedia-rohttp://ro.dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/
n40http://www.labri.fr/perso/robson/mis/
yago-reshttp://yago-knowledge.org/resource/
n34https://global.dbpedia.org/id/
n54http://www.csc.kth.se/%7Ejohanh/
n25https://zenodo.org/record/
dbpedia-ithttp://it.dbpedia.org/resource/
n48https://hal.inria.fr/
provhttp://www.w3.org/ns/prov#
foafhttp://xmlns.com/foaf/0.1/
n6http://4mhz.de/
n56https://web.archive.org/web/20120527164352/http:/handle.dtic.mil/100.2/
dbpedia-zhhttp://zh.dbpedia.org/resource/
n52http://www.inf.u-szeged.hu/actacybernetica/edb/vol10n3/pdf/
dbpedia-kohttp://ko.dbpedia.org/resource/
n10http://www.cs.berkeley.edu/~luca/cs172/
freebasehttp://rdf.freebase.com/ns/
dbpedia-eshttp://es.dbpedia.org/resource/
owlhttp://www.w3.org/2002/07/owl#

Statements

Subject Item
dbr:Clique_problem
rdf:type
yago:Problem114410605 yago:State100024720 yago:Difficulty114408086 yago:WikicatComputationalProblemsInGraphTheory yago:Abstraction100002137 yago:Condition113920835 yago:WikicatNP-completeProblems yago:Attribute100024264
rdfs:label
클릭 문제 Problema do clique Задача о клике Problem kliki Problème de la clique Problema del clique Cliquenproblem مشكلة المخطط الكامل ضمن مخطط 最大クリーク問題 Задача про кліку 分團問題 Problema della cricca Clique problem
rdfs:comment
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: 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. 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: 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-полных задач в области теории графов. Впервые она была сформулирована в 1972 году Ричардом Карпом. Кликой в неориентированном графе называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это полный подграф первоначального графа. Размер клики определяется как число вершин в ней. Задача о клике существует в двух вариантах: в задаче распознавания требуется определить, существует ли в заданном графе G клика размера k, в то время как в вычислительном варианте требуется найти в заданном графе G клику максимального размера. 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. 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. 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. 最大クリーク問題（さいだいクリークもんだい）は、グラフ理論において、グラフ中のクリーク（任意の二頂点間に枝があるような頂点集合）の中で最大のものを見つける問題。NP困難であることが知られている。 この問題は、補グラフに対する最大独立集合問題と等価である。 近似アルゴリズムについても研究されているが、グラフの頂点数を n とするとき、近似度 O(n / (log n)2) が達成されているのみである。また、P = NP が成り立たないとき、任意の ε > 0 について、近似度 n1/2 − ε の近似アルゴリズムが存在しないことが示されている。NP = ZPP が成り立たない場合、近似度 n1 − ε の近似アルゴリズムが存在しないことも示されている。 المخطط الكامل هو مضلع كل رأسين فيه مرتبطان. ورتبة المخطط الكامل هو عدد رؤوسه. Задача про кліку відноситься до класу NP-повних задач в області теорії графів. Вперше вона була сформульована у 1972 році Річардом Карпом. Клікою в неорієнтованому графі називається підмножина вершин, кожні дві з яких з'єднані ребром графу. Іншими словами, це повний підграф первісного графу. Розмір кліки визначається як число вершин в ній. Задача про кліку існує у двох варіантах: у задачі розпізнавання потрібно визначити, чи існує в заданому графі G кліка розміру k, тоді як в обчислювальному варіанті потрібно знайти в заданому графі G кліку максимального розміру або всі максимальні кліки (такі, що не можна збільшити). 在計算複雜度理論中，分團問題（clique problem）是圖論中的一個NP完全（NP-complete）問題。 团（clique）是一個圖中兩兩相鄰的一個頂點集，或是一個完全子圖（complete subgraph），如右圖中的1、2、5三個頂點。 分团问题是問一個圖中是否有大小是k以上的团。任意挑出k個點，我們可以簡單的判斷出這k個點是不是一個团，所以這個問題屬於NP。 證明這問題是NP完備，我們可以很簡單的將(Independent set problem)歸約成這個問題。因為存在一個大小是k以上的分團，等價於它的補圖中存在一個大小是k以上的獨立集。 클릭 문제 (clique problem)는 NP완전인 그래프 이론에 등장하는 문제이다. 이 문제는 리처드 카프가 1972년 논문에서 NP완전임을 증명한 21문제 중의 하나일 뿐만 아니라, NP완전 문제 이론을 소개한 쿡의 논문에서도 언급된 유명한 문제이다. 그래프의 클릭(clique)이란 부분그래프이면서 그래프의 임의의 두 노드가 서로 연결된 것으로 정의된다. 즉, 완전 그래프인 부분그래프를 클릭이라 한다. 오른쪽 그림에서 노드 1, 2, 5로 이루어진 부분그래프는 클릭이 된다. 왜냐하면, 각 노드가 모든 나머지 노드와 연결되어 있기 때문이다. 반면 2, 5, 3으로 이루어진 그래프를 보면, 5와 3이 연결되어 있지 않아 클릭이 되지 못한다.
foaf:depiction
n12:Sat_reduced_to_Clique_from_Sipser.svg n12:Cube-face-intersection-graph.svg n12:Permutation_graph.svg n12:Decision_tree_for_3-clique_no_arrowheads.svg n12:Monotone_circuit_for_3-clique.svg n12:6n-graf-clique.svg n12:Brute_force_Clique_algorithm.svg
dcterms:subject
dbc:Computational_problems_in_graph_theory dbc:NP-complete_problems
dbo:wikiPageID
249254
dbo:wikiPageRevisionID
1093311196
dbo:wikiPageWikiLink
dbr:Evolutionary_tree dbr:IEEE_Transactions_on_Computers dbr:Complete_(complexity) dbr:Graph_property dbr:Boolean_satisfiability_problem dbr:Plenum_Publishing_Corporation dbr:Glossary_of_graph_theory dbr:Glossary_of_graph_theory_terms dbr:Discrete_Mathematics_(journal) dbr:Communications_of_the_ACM dbr:Complement_(graph_theory) dbr:Combinatorica dbr:Decision_tree_model dbr:Circle_graph dbr:Symposium_on_Foundations_of_Computer_Science dbr:Maximal_element dbr:Discrete_Applied_Mathematics dbr:Local_search_(optimization) dbr:Proceedings_of_the_USSR_Academy_of_Sciences dbr:Bulletin_of_the_American_Mathematical_Society dbr:The_New_York_Times dbr:Maximum_common_induced_subgraph dbr:Well-covered_graph dbr:Uriel_Feige dbr:Algorithm dbr:Planted_clique dbr:Unit_disk_graph dbr:Adjacency_matrix dbr:Theoretical_Computer_Science_(journal) dbr:NOT_gate dbr:Systematic_Zoology dbr:Arboricity dbr:Greedy_algorithm dbr:Acta_Mathematica dbr:Maximum_clique dbr:Linear_time n19:Sat_reduced_to_Clique_from_Sipser.svg dbr:Maximal_clique dbr:Brute-force_search dbr:Unordered_pair dbr:Keller's_conjecture dbr:Karp's_21_NP-complete_problems dbr:Information_and_Control dbr:NC_(complexity) dbr:Algorithmica dbr:The_Thomson_Corporation dbr:NP-complete dbr:Cook–Levin_theorem dbr:Kőnig's_theorem_(graph_theory) dbr:Conjunctive_normal_form dbr:American_Mathematical_Society dbr:Many-one_reduction dbr:Exponential_time dbr:Vertex_(graph_theory) dbc:Computational_problems_in_graph_theory dbr:Exponential_time_hypothesis dbr:Triangle-free_graph dbr:Protein_structure_prediction dbr:BIT_Numerical_Mathematics dbr:Dense_graph dbr:Parallel_algorithm dbr:P_versus_NP_problem dbr:Approximation_algorithm dbr:W(1) dbr:Ramsey_theory dbr:Dependency_graph dbr:Truth_value dbr:Truth_values dbr:Lexicographic_order dbr:Permutation_graph dbr:P_=_NP dbr:Heuristic_algorithm dbr:SIAM_Journal_on_Computing dbr:SIAM_Journal_on_Discrete_Mathematics dbr:Hereditary_property dbr:Chromatic_number dbr:FP_(complexity) dbr:And_gate dbr:DNA_computing dbr:Time_complexity dbr:Complete_graph dbr:Bipartite_graph dbr:Social_network dbr:DIMACS dbr:Chemistry dbr:Automatic_test_pattern_generation dbr:Adiabatic_quantum_computation dbr:Branch_and_bound dbr:Minor-closed_graph_family dbr:Random_graph n19:Permutation_graph.svg dbr:Big_O_notation dbr:Computational_complexity_theory dbr:Travelling_salesman_problem dbr:Probabilistically_checkable_proof dbr:Induced_subgraph dbr:Or_gate dbr:Hypercube dbr:Independent_set_problem n19:Decision_tree_for_3-clique_no_arrowheads.svg dbr:Computational_chemistry dbr:Journal_of_Graph_Algorithms_and_Applications dbr:Information_Processing_Letters n19:Brute_force_Clique_algorithm.svg dbr:Comparability_graph n19:Cube-face-intersection-graph.svg dbr:Approximation_ratio dbr:Bioinformatics dbr:Interval_graph dbr:Aanderaa–Karp–Rosenberg_conjecture dbr:Big_theta_notation dbr:Compositio_Mathematica dbr:Stephen_Cook dbr:Closure_(mathematics) dbr:Neighborhood_(graph_theory) dbr:Circuit_complexity dbr:Boxicity dbr:Clique dbr:Clique_(graph_theory) dbr:Adjacent_(graph_theory) dbr:Parameterized_complexity dbr:Polynomial-time_approximation_scheme dbr:Undirected_graph dbr:Journal_of_the_ACM dbr:Planar_graph dbr:Partial_word dbr:Science_(journal) dbr:Degeneracy_(graph_theory) dbr:Bron–Kerbosch_algorithm dbr:Backtracking dbr:Modular_product_of_graphs dbr:Erdős–Rényi_model dbr:Perfect_graph dbr:P_≠_NP dbr:Springer-Verlag dbr:Chordal_graph dbr:Docking_(molecular) dbr:Big_omega_notation dbr:Fan-in dbr:Lexicographic_ordering dbr:Wildcard_character dbr:Journal_of_Combinatorial_Theory dbr:Spectral_graph_theory dbr:Israel_Journal_of_Mathematics dbr:Polynomial_delay dbr:Output-sensitive_algorithm dbr:Computer_science dbr:Finite_set dbc:NP-complete_problems dbr:Decision_tree_complexity dbr:Journal_of_Computer_and_System_Sciences dbr:Real_number dbr:Proceedings_of_the_National_Academy_of_Sciences dbr:Edge_(graph_theory) dbr:Kuratowski's_theorem dbr:Decision_problem dbr:Dynamic_programming dbr:Graph_(discrete_mathematics) dbr:Matching_(graph_theory) dbr:Constraint_programming dbr:Journal_of_the_American_Statistical_Association dbr:Semidefinite_programming dbr:Discrete_and_Computational_Geometry n19:Monotone_circuit_for_3-clique.svg dbr:Academic_Press dbr:Complement_graph dbr:Polynomial_time dbr:Hardness_of_approximation dbr:Worst-case_analysis dbr:NP-completeness n19:6n-graf-clique.svg dbr:Longest_increasing_subsequence dbr:Computational_complexity_of_matrix_multiplication
dbo:wikiPageExternalLink
n4: n5: n6:cook.html n7:278 n8:match2007.pdf n10:karp.pdf n21:books%3Fid=CAm2DpIqRUIC&pg=PA276 n22:CS-TR-76-550.pdf n23:04swat.pdf n25:896067 n27:karp.pdf n30:ADA247861 n35:maxclique n37:in-a-frenzy-math-enters-age-of-electronic-mail.html n39:1935-01.pdf n40:techrep.html n47:Cliques.pdf n48:hal-00966509 n52:Groger_1992_ActaCybernetica.pdf n54:monotoneclique.pdf n56:ADA247861 n57:Vol26.html
owl:sameAs
dbpedia-ar:مشكلة_المخطط_الكامل_ضمن_مخطط dbpedia-fr:Problème_de_la_clique dbpedia-es:Problema_del_clique dbpedia-ru:Задача_о_клике dbpedia-zh:分團問題 dbpedia-ja:最大クリーク問題 dbpedia-ro:Problema_clicii n34:EiYJ dbpedia-it:Problema_della_cricca freebase:m.01k_tj dbpedia-pt:Problema_do_clique yago-res:Clique_problem dbpedia-th:ปัญหากลุ่มพรรคพวก wikidata:Q1196873 dbpedia-de:Cliquenproblem dbpedia-sr:Проблем_клике dbpedia-uk:Задача_про_кліку dbpedia-ko:클릭_문제 n53:ক্লিক_সমস্যা dbpedia-pl:Problem_kliki
dbp:wikiPageUsesTemplate
dbt:Good_article dbt:Citation dbt:Main dbt:Italics_correction dbt:Radic dbt:Clear dbt:Doi dbt:Sfnp dbt:Refbegin dbt:Reflist dbt:Refend dbt:Short_description dbt:Math dbt:Mvar dbt:Harvtxt dbt:ECCC
dbo:thumbnail
n12:Brute_force_Clique_algorithm.svg?width=300
dbo:abstract
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. 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. 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. 最大クリーク問題（さいだいクリークもんだい）は、グラフ理論において、グラフ中のクリーク（任意の二頂点間に枝があるような頂点集合）の中で最大のものを見つける問題。NP困難であることが知られている。 この問題は、補グラフに対する最大独立集合問題と等価である。 近似アルゴリズムについても研究されているが、グラフの頂点数を n とするとき、近似度 O(n / (log n)2) が達成されているのみである。また、P = NP が成り立たないとき、任意の ε > 0 について、近似度 n1/2 − ε の近似アルゴリズムが存在しないことが示されている。NP = ZPP が成り立たない場合、近似度 n1 − ε の近似アルゴリズムが存在しないことも示されている。 在計算複雜度理論中，分團問題（clique problem）是圖論中的一個NP完全（NP-complete）問題。 团（clique）是一個圖中兩兩相鄰的一個頂點集，或是一個完全子圖（complete subgraph），如右圖中的1、2、5三個頂點。 分团问题是問一個圖中是否有大小是k以上的团。任意挑出k個點，我們可以簡單的判斷出這k個點是不是一個团，所以這個問題屬於NP。 證明這問題是NP完備，我們可以很簡單的將(Independent set problem)歸約成這個問題。因為存在一個大小是k以上的分團，等價於它的補圖中存在一個大小是k以上的獨立集。 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. Задача о клике относится к классу NP-полных задач в области теории графов. Впервые она была сформулирована в 1972 году Ричардом Карпом. Кликой в неориентированном графе называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это полный подграф первоначального графа. Размер клики определяется как число вершин в ней. Задача о клике существует в двух вариантах: в задаче распознавания требуется определить, существует ли в заданном графе G клика размера k, в то время как в вычислительном варианте требуется найти в заданном графе G клику максимального размера. 클릭 문제 (clique problem)는 NP완전인 그래프 이론에 등장하는 문제이다. 이 문제는 리처드 카프가 1972년 논문에서 NP완전임을 증명한 21문제 중의 하나일 뿐만 아니라, NP완전 문제 이론을 소개한 쿡의 논문에서도 언급된 유명한 문제이다. 그래프의 클릭(clique)이란 부분그래프이면서 그래프의 임의의 두 노드가 서로 연결된 것으로 정의된다. 즉, 완전 그래프인 부분그래프를 클릭이라 한다. 오른쪽 그림에서 노드 1, 2, 5로 이루어진 부분그래프는 클릭이 된다. 왜냐하면, 각 노드가 모든 나머지 노드와 연결되어 있기 때문이다. 반면 2, 5, 3으로 이루어진 그래프를 보면, 5와 3이 연결되어 있지 않아 클릭이 되지 못한다. 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. Задача про кліку відноситься до класу NP-повних задач в області теорії графів. Вперше вона була сформульована у 1972 році Річардом Карпом. Клікою в неорієнтованому графі називається підмножина вершин, кожні дві з яких з'єднані ребром графу. Іншими словами, це повний підграф первісного графу. Розмір кліки визначається як число вершин в ній. Задача про кліку існує у двох варіантах: у задачі розпізнавання потрібно визначити, чи існує в заданому графі G кліка розміру k, тоді як в обчислювальному варіанті потрібно знайти в заданому графі G кліку максимального розміру або всі максимальні кліки (такі, що не можна збільшити). 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. 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. المخطط الكامل هو مضلع كل رأسين فيه مرتبطان. ورتبة المخطط الكامل هو عدد رؤوسه.
prov:wasDerivedFrom
wikipedia-en:Clique_problem?oldid=1093311196&ns=0
dbo:wikiPageLength
85275
foaf:isPrimaryTopicOf
wikipedia-en:Clique_problem