Clique (graph theory) (original) (raw)
Eine Clique bezeichnet in der Graphentheorie eine Teilmenge von Knoten in einem ungerichteten Graphen, bei der jedes Knotenpaar durch eine Kante verbunden ist. Zu entscheiden, ob ein Graph eine Clique einer bestimmten Mindestgröße enthält, wird Cliquenproblem genannt und gilt, wie das Finden von größten Cliquen, als algorithmisch schwierig (NP-vollständig). Das Finden einer Clique einer bestimmten Größe in einem Graphen ist ein NP-vollständiges Problem und somit auch in der Informationstechnik ein relevantes Forschungs- und Anwendungsgebiet.
| Property | Value |
|---|---|
| dbo:abstract | Klika, anglicky Clique je takový podgraf nějakého grafu, který je úplným grafem, tzn. jehož všechny vrcholy jsou spojeny hranou se všemi zbylými. Klikovost grafu je celé číslo udávající velikost největší kliky (úplného podgrafu) v daném grafu. Klikovost úplného grafu Kn je n, klikovost diskrétního grafu je 1. Klikovost grafu G se značí ω(G). Problém nalezení takového čísla (resp. nalezení největší kliky) je (rozhodovací verze, zda daný graf má klikovost alespoň k, je NP-úplná). Tento problém je ze třídy NP-úplných, jelikož nalezením nezávislé množiny IND v grafu alespoň k získáme zároveň v doplňku grafu i kliku (viz vzorec níže). A Lze také dokázat, že problém logických formulí SAT z NP-úplných je redukovatelný na IND a dle předchozího je IND redukovatelný na Clique a tak patří třídě NP-úplných problémů. Klikovost těsně souvisí s nezávislostí – je zřejmé, že v doplňku grafu odpovídá klice nezávislá podmnožina, takže platí ω(G) = α(−G). (cs) En grafeteorio, kliko en sendirekta grafeo G estas aro de verticoj V tia ke por ĉiuj du verticoj en V ekzistas eĝo konektanta ilin du. Alternative, kliko estas grafeo en kiu ĉiu vertico estas koneksa al ĉiu la alia vertico de la grafeo. Alternative, kliko estas la subgrafeo konkludita per la aro de verticoj V kiu estas kompleta grafeo. La amplekso de kliko estas la nombro de verticoj en ĝi. Provado ĉu estas kliko de donita amplekso en donita grafeo (la ) estas . La kontraŭo al kliko estas , en la senco ke ĉiu kliko respektivas al sendependa en la de la grafeo. La plej granda kliko en grafeo G estas de teoria graveco kaj estas skribata kiel ω(G) (eo) In the mathematical area of graph theory, a clique (/ˈkliːk/ or /ˈklɪk/) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied. Although the study of complete subgraphs goes back at least to the graph-theoretic reformulation of Ramsey theory by , the term clique comes from , who used complete subgraphs in social networks to model cliques of people; that is, groups of people all of whom know each other. Cliques have many other applications in the sciences and particularly in bioinformatics. (en) Eine Clique bezeichnet in der Graphentheorie eine Teilmenge von Knoten in einem ungerichteten Graphen, bei der jedes Knotenpaar durch eine Kante verbunden ist. Zu entscheiden, ob ein Graph eine Clique einer bestimmten Mindestgröße enthält, wird Cliquenproblem genannt und gilt, wie das Finden von größten Cliquen, als algorithmisch schwierig (NP-vollständig). Das Finden einer Clique einer bestimmten Größe in einem Graphen ist ein NP-vollständiges Problem und somit auch in der Informationstechnik ein relevantes Forschungs- und Anwendungsgebiet. (de) En teoría de grafos, un clique (o «una clique», pronunciado /klik/), a veces traducido desde el inglés como clan o camarilla, C, en un grafo no dirigido G = (V, E) es un conjunto de vértices, C ⊆ V, tal que todo par de vértices distintos son adyacentes, es decir, existe una arista que los conecta. En otras palabras, un clique es un subgrafo en el que cada vértice está conectado a todos los demás vértices del subgrafo. Esto equivale a decir que el subgrafo de G inducido por C es un grafo completo. El tamaño de un clique es el número de vértices que contiene. El problema del clique, que consiste en dado un grafo, decidir si existe en él un clique con un tamaño particular, es NP-completo. Lo opuesto de un clique es un conjunto independiente, en el sentido que cada clique corresponde a un conjunto independiente del grafo complemento. (es) Une clique d'un graphe non orienté est, en théorie des graphes, un sous-ensemble des sommets de ce graphe dont le sous-graphe induit est complet, c'est-à-dire que deux sommets quelconques de la clique sont toujours adjacents. Une clique maximum d'un graphe est une clique dont le cardinal est le plus grand (c'est-à-dire qu'elle possède le plus grand nombre de sommets). Le cardinal d'une telle clique maximum est une caractéristique du graphe, appelée nombre de clique, et que l'on peut relier à son nombre chromatique. Le problème de la clique maximum, la recherche de l'une des cliques maximum pour un graphe (fini) donné, est un problème NP-difficile. (fr) グラフ理論において、無向グラフ のクリーク（英: clique）とは、頂点の部分集合 のうち、 に属するあらゆる2つの頂点を繋ぐ辺が存在するものをいう。これはすなわち、 から誘導される部分グラフが完全だということである。なお、頂点の集合ではなく、そのような部分グラフをクリークと呼ぶこともある。（また包含関係に関して極大な完全部分グラフのみをクリークと呼ぶこともあるので注意がいる。）クリークに属する頂点数をそのクリークの大きさと言う。 与えられたグラフに指定された大きさのクリークがあるかどうかを求める問題（クリーク問題、その特殊版が最大クリーク問題）はNP完全である。 クリークの逆の概念を独立集合と呼び、クリークは必ず補グラフの独立集合と対応する。 この用語は、頂点を人、辺を「知っている」という意味としたとき、全ての人が互いに知っていることになるため "clique"（徒党、派閥）と名付けられた。 グラフ の最大クリークは理論上重要であり、 で表される。 (ja) 그래프 이론에서 클릭(영어: clique)은 모든 가능한 변이 존재하는 꼭짓점들의 부분집합이다. (ko) In teoria dei grafi, una cricca (o clique) è un insieme V di vertici in un grafo non orientato G, tale che, per ogni coppia di vertici in V, esiste un arco che li collega. In modo equivalente, si potrebbe dire che il sottografo indotto da V è un grafo completo. La dimensione di una cricca è definita come il numero di vertici che contiene. Alcuni autori chiamano cricca ogni sottografo completo che sia di dimensione massima. Il problema di trovare, se esiste, una cricca di una dimensione fissata all'interno di un grafo è detto problema della cricca, ed è NP-completo. Il concetto complementare a quello di cricca è l'insieme indipendente, nel senso che a ogni cricca corrisponde un insieme indipendente nel grafo complemento. Sebbene lo studio dei sottografi completi risalga almeno alla riformulazione della teoria dei grafi con la teoria di Ramsey da parte di , il termine "cricca" viene da , che utilizzarono sottografi completi nelle reti sociali per modellare le cricche (in inglese cliques) di persone, vale a dire gruppi ristretti di persone che si conoscono tutte fra di loro. Le cricche hanno molte applicazioni nelle scienze e particolarmente in bioinformatica. (it) In de grafentheorie is een clique of kliek een deelverzameling van de knopen van een niet-gerichte enkelvoudige graaf, waarvan de geïnduceerde deelgraaf volledig is. Dit houdt in dat elk tweetal knopen van een clique met elkaar verbonden zijn. De term clique werd ingevoerd door Luce en Perry in 1949, in het kader van de analyse van sociale netwerken.Een clique of kliek is daarin een groep personen waarvan elke persoon elke andere persoon kent. (nl) Klika – podgraf, w którym każde dwa wierzchołki są połączone krawędzią. Klika jest maksymalna, jeśli nie da się dodać do niej wierzchołka tak, aby razem z nią również tworzył klikę. Klika jest największa (najliczniejsza), jeśli nie ma w grafie kliki o większej liczbie wierzchołków. Rząd największej kliki grafu (ang. clique number) oznaczamy Graf, którego liczba chromatyczna jest równa rozmiarowi największej kliki nazywa się grafem doskonałym (ang. perfect graph). Stwierdzenie, czy w grafie istnieje klika o zadanym rozmiarze (problem kliki), jest jednym z klasycznych problemów NP-zupełnych. Problemem dualnym dla problemu kliki jest problem zbioru niezależnego. (pl) En klick är inom matematik, specifikt grafteori, ett antal utvalda noder i en graf sådan att det i grafen finns en båge mellan varje par av noder. Annorlunda uttryckt är en klick en mängd av noder som inducerar en H i en graf G sådan att H är en komplett graf. Med storleken på en klick avses antalet noder som den innehåller. En klick i en graf bildar en oberoende mängd i dess komplementgraf. Klickproblemet är att, givet en graf, avgöra om det finns en klick av minst en given storlek i grafen. Klickproblemet är NP-fullständigt. Detta hänger samman med NP-fullständigheten att hitta en oberoende mängd av given storlek, eftersom om man hittar en oberoende mängd i komplementgrafen har man hittat en klick i den ursprungliga grafen. En graf G:s klicktal, ofta betecknat , är storleken på den största klicken i G. Detta kan även uttryckas som att är det största heltalet r så att den kompletta grafen är en delgraf till G. (sv) Na área da matemática da teoria dos grafos, um clique em um grafo não orientado é um subconjunto de seus vértices tais que cada dois vértices do subconjunto são conectados por uma aresta.Clique é um dos conceitos mais básicos na teoria dos grafos e são utilizados em vários problemas matemáticos e construções em grafos. O Clique vem sendo estudado na ciência da computação: a tarefa de achar se existe um clique de um dado tamanho em um grafo (o problema do clique) é NP-completo, mas apesar de sua dificuldade, vários algoritmos para encontrar clique foram estudados. Embora o estudo de subgrafos completos seja da época da reformulação teórica dos grafos da Teoria de Ramsey por , o termo "clique" vem de , que utilizou subgrafos completos em redes sociais para modelar de pessoas; ou seja, grupos de pessoas onde todas se conhecem. O Clique possui várias outras aplicações na ciência, principalmente na bioinformática. (pt) Кликой неориентированного графа называется подмножество его вершин, любые две из которых соединены ребром. Клики являются одной из основных концепций теории графов и используются во многих других математических задачах и построениях с графами. Клики изучаются также в информатике — задача определения, существует ли клика данного размера в графе (Задача о клике) является NP-полной. Несмотря на эту трудность, изучаются многие алгоритмы для поиска клик. Хотя изучение полных подграфов началось ещё с формулировки теоремы Рамсея в терминах теории графов Эрдёшем и Секерешем. Термин «клика» пришёл из работы Люка и Пери, использовавших полные подграфы при изучении социальных сетей для моделировании клик людей, то есть групп людей, знакомых друг с другом. Клики имеют много других приложений в науке, и, в частности, в биоинформатике. (ru) 在图论领域的一个无向图中，满足两两之间有边连接的顶点的集合，被称为该无向图的团。团是图论中的基本概念之一，用在很多数学问题以及图的构造上。计算机科学中也有对它的研究，尽管在一个图中寻找给定大小的团达到了NP完全的难度，人们还是研究过很多寻找团的算法。 虽然对完全子图的研究可以追溯到)中拉姆齐理论对图理论的重组，“团”这一术语本身其实源自 )，那篇文章中社会网络的完全子图被用来模拟一“团”人，也就是一组两两相互认识的人。团在科学领域特别是在生物信息学中有许多其他应用。 (zh) Кліка в неорієнтованому графі це підмножина його вершин така, що кожні дві вершини з цієї підмножини поєднанні ребром. Кліки є однією з базових концепцій теорії графів і використовуються в багатьох математичних задачах та побудовах на графах. Кліки також вивчаються в інформатиці: виявлення чи існує в графі кліка даного розміру (задача про кліку) є NP-повною, але незважаючи на складність, вивчаються багато алгоритмів знаходження клік. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/VR_complex.svg?width=300 |
| dbo:wikiPageExternalLink | http://aris.ss.uci.edu/~lin/1.pdf http://www.renyi.hu/~p_erdos/1935-01.pdf http://www.cs.berkeley.edu/~luca/cs172/karp.pdf https://archive.org/details/ramseytheory0000grah https://web.archive.org/web/20110629023717/http:/www.cs.berkeley.edu/~luca/cs172/karp.pdf http://matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf |
| dbo:wikiPageID | 524466 (xsd:integer) |
| dbo:wikiPageLength | 20241 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1096684789 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Protein-protein_interaction dbr:Biconnected_component dbr:Dense_graph dbr:Algorithm dbr:Undirected_graph dbr:Independent_set_(graph_theory) dbr:Induced_subgraph dbr:Intersection_number_(graph_theory) dbr:Kuratowski's_theorem dbr:Adjacent_(graph_theory) dbr:Protein_structure_prediction dbc:Graph_theory_objects dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Mathematics dbr:Maximal_independent_set dbr:Median_graph dbr:Chemical_database dbr:Gene_expression dbr:Social_network dbr:Chromatic_number dbr:Clique-sum dbr:Clique-width dbr:Clique_problem dbr:Cluster_graph dbr:Electrical_engineering dbr:Graph_(discrete_mathematics) dbr:Graph_minor dbr:NP-complete dbr:Perfect_phylogeny dbr:Proceedings_of_the_IRE dbr:Proceedings_of_the_National_Academy_of_Sciences dbr:Line_graph dbr:Lower_bound dbr:Clique dbr:Clique_complex dbr:Clique_cover dbr:Clique_game dbr:Clique_graph dbr:Complement_graph dbr:Computer_science dbr:Hardness_of_approximation dbr:Perfect_graph dbr:Triangle-free_graph dbr:Karp's_21_NP-complete_problems dbr:Abstract_simplicial_complex dbr:Erdős–Faber–Lovász_conjecture dbr:Evolutionary_tree dbr:Food_chain dbr:Bron–Kerbosch_algorithm dbr:Graph_theory dbr:Israel_Journal_of_Mathematics dbr:Ramsey_theory dbr:Hadwiger_conjecture_(graph_theory) dbr:Hadwiger_number dbr:Intersection_graph dbr:Interval_graph dbr:Power_graph_analysis dbr:Chemistry dbr:Chordal_graph dbr:Biclustering dbr:Bioinformatics dbr:Bipartite_dimension dbr:Block_graph dbr:Cograph dbr:Ecological_niche dbr:Automatic_test_pattern_generation dbr:Planar_graph dbr:Split_graph dbr:Connected_component_(graph_theory) dbr:Polynomial_time dbr:Neighborhood_(graph_theory) dbr:Ramsey's_theorem dbr:Median_algebra dbr:Simplex_graph dbr:Vertex_(graph_theory) dbr:Exponential_time dbr:Turán's_theorem dbr:Parameterized_complexity dbr:Turán_graph dbr:Wagner's_theorem dbr:Subdivision_(graph_theory) dbr:File:VR_complex.svg |
| dbp:mode | cs2 (en) |
| dbp:title | Clique (en) Clique Number (en) |
| dbp:urlname | Clique (en) CliqueNumber (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:IPAc-en dbt:Main dbt:Math dbt:MathWorld dbt:Mvar dbt:Other_uses dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfnp dbt:Short_description dbt:Unordered_list |
| dct:subject | dbc:Graph_theory_objects |
| gold:hypernym | dbr:Subset |
| rdf:type | yago:Abstraction100002137 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Feature105849789 yago:Idea105833840 yago:Invariant105850432 yago:Object100002684 yago:PhysicalEntity100001930 yago:Property105849040 yago:PsychologicalFeature100023100 yago:WikicatGraphInvariants yago:WikicatGraphTheoryObjects dbo:ProgrammingLanguage |
| rdfs:comment | Eine Clique bezeichnet in der Graphentheorie eine Teilmenge von Knoten in einem ungerichteten Graphen, bei der jedes Knotenpaar durch eine Kante verbunden ist. Zu entscheiden, ob ein Graph eine Clique einer bestimmten Mindestgröße enthält, wird Cliquenproblem genannt und gilt, wie das Finden von größten Cliquen, als algorithmisch schwierig (NP-vollständig). Das Finden einer Clique einer bestimmten Größe in einem Graphen ist ein NP-vollständiges Problem und somit auch in der Informationstechnik ein relevantes Forschungs- und Anwendungsgebiet. (de) グラフ理論において、無向グラフ のクリーク（英: clique）とは、頂点の部分集合 のうち、 に属するあらゆる2つの頂点を繋ぐ辺が存在するものをいう。これはすなわち、 から誘導される部分グラフが完全だということである。なお、頂点の集合ではなく、そのような部分グラフをクリークと呼ぶこともある。（また包含関係に関して極大な完全部分グラフのみをクリークと呼ぶこともあるので注意がいる。）クリークに属する頂点数をそのクリークの大きさと言う。 与えられたグラフに指定された大きさのクリークがあるかどうかを求める問題（クリーク問題、その特殊版が最大クリーク問題）はNP完全である。 クリークの逆の概念を独立集合と呼び、クリークは必ず補グラフの独立集合と対応する。 この用語は、頂点を人、辺を「知っている」という意味としたとき、全ての人が互いに知っていることになるため "clique"（徒党、派閥）と名付けられた。 グラフ の最大クリークは理論上重要であり、 で表される。 (ja) 그래프 이론에서 클릭(영어: clique)은 모든 가능한 변이 존재하는 꼭짓점들의 부분집합이다. (ko) In de grafentheorie is een clique of kliek een deelverzameling van de knopen van een niet-gerichte enkelvoudige graaf, waarvan de geïnduceerde deelgraaf volledig is. Dit houdt in dat elk tweetal knopen van een clique met elkaar verbonden zijn. De term clique werd ingevoerd door Luce en Perry in 1949, in het kader van de analyse van sociale netwerken.Een clique of kliek is daarin een groep personen waarvan elke persoon elke andere persoon kent. (nl) 在图论领域的一个无向图中，满足两两之间有边连接的顶点的集合，被称为该无向图的团。团是图论中的基本概念之一，用在很多数学问题以及图的构造上。计算机科学中也有对它的研究，尽管在一个图中寻找给定大小的团达到了NP完全的难度，人们还是研究过很多寻找团的算法。 虽然对完全子图的研究可以追溯到)中拉姆齐理论对图理论的重组，“团”这一术语本身其实源自 )，那篇文章中社会网络的完全子图被用来模拟一“团”人，也就是一组两两相互认识的人。团在科学领域特别是在生物信息学中有许多其他应用。 (zh) Кліка в неорієнтованому графі це підмножина його вершин така, що кожні дві вершини з цієї підмножини поєднанні ребром. Кліки є однією з базових концепцій теорії графів і використовуються в багатьох математичних задачах та побудовах на графах. Кліки також вивчаються в інформатиці: виявлення чи існує в графі кліка даного розміру (задача про кліку) є NP-повною, але незважаючи на складність, вивчаються багато алгоритмів знаходження клік. (uk) Klika, anglicky Clique je takový podgraf nějakého grafu, který je úplným grafem, tzn. jehož všechny vrcholy jsou spojeny hranou se všemi zbylými. Klikovost grafu je celé číslo udávající velikost největší kliky (úplného podgrafu) v daném grafu. Klikovost úplného grafu Kn je n, klikovost diskrétního grafu je 1. Klikovost grafu G se značí ω(G). Problém nalezení takového čísla (resp. nalezení největší kliky) je (rozhodovací verze, zda daný graf má klikovost alespoň k, je NP-úplná). ω(G) = α(−G). (cs) In the mathematical area of graph theory, a clique (/ˈkliːk/ or /ˈklɪk/) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied. (en) En grafeteorio, kliko en sendirekta grafeo G estas aro de verticoj V tia ke por ĉiuj du verticoj en V ekzistas eĝo konektanta ilin du. Alternative, kliko estas grafeo en kiu ĉiu vertico estas koneksa al ĉiu la alia vertico de la grafeo. Alternative, kliko estas la subgrafeo konkludita per la aro de verticoj V kiu estas kompleta grafeo. La amplekso de kliko estas la nombro de verticoj en ĝi. Provado ĉu estas kliko de donita amplekso en donita grafeo (la ) estas . La kontraŭo al kliko estas , en la senco ke ĉiu kliko respektivas al sendependa en la de la grafeo. (eo) En teoría de grafos, un clique (o «una clique», pronunciado /klik/), a veces traducido desde el inglés como clan o camarilla, C, en un grafo no dirigido G = (V, E) es un conjunto de vértices, C ⊆ V, tal que todo par de vértices distintos son adyacentes, es decir, existe una arista que los conecta. En otras palabras, un clique es un subgrafo en el que cada vértice está conectado a todos los demás vértices del subgrafo. Esto equivale a decir que el subgrafo de G inducido por C es un grafo completo. El tamaño de un clique es el número de vértices que contiene. (es) Une clique d'un graphe non orienté est, en théorie des graphes, un sous-ensemble des sommets de ce graphe dont le sous-graphe induit est complet, c'est-à-dire que deux sommets quelconques de la clique sont toujours adjacents. (fr) In teoria dei grafi, una cricca (o clique) è un insieme V di vertici in un grafo non orientato G, tale che, per ogni coppia di vertici in V, esiste un arco che li collega. In modo equivalente, si potrebbe dire che il sottografo indotto da V è un grafo completo. La dimensione di una cricca è definita come il numero di vertici che contiene. Alcuni autori chiamano cricca ogni sottografo completo che sia di dimensione massima. Il problema di trovare, se esiste, una cricca di una dimensione fissata all'interno di un grafo è detto problema della cricca, ed è NP-completo. (it) Na área da matemática da teoria dos grafos, um clique em um grafo não orientado é um subconjunto de seus vértices tais que cada dois vértices do subconjunto são conectados por uma aresta.Clique é um dos conceitos mais básicos na teoria dos grafos e são utilizados em vários problemas matemáticos e construções em grafos. O Clique vem sendo estudado na ciência da computação: a tarefa de achar se existe um clique de um dado tamanho em um grafo (o problema do clique) é NP-completo, mas apesar de sua dificuldade, vários algoritmos para encontrar clique foram estudados. (pt) Klika – podgraf, w którym każde dwa wierzchołki są połączone krawędzią. Klika jest maksymalna, jeśli nie da się dodać do niej wierzchołka tak, aby razem z nią również tworzył klikę. Klika jest największa (najliczniejsza), jeśli nie ma w grafie kliki o większej liczbie wierzchołków. Rząd największej kliki grafu (ang. clique number) oznaczamy Graf, którego liczba chromatyczna jest równa rozmiarowi największej kliki nazywa się grafem doskonałym (ang. perfect graph). (pl) En klick är inom matematik, specifikt grafteori, ett antal utvalda noder i en graf sådan att det i grafen finns en båge mellan varje par av noder. Annorlunda uttryckt är en klick en mängd av noder som inducerar en H i en graf G sådan att H är en komplett graf. Med storleken på en klick avses antalet noder som den innehåller. En klick i en graf bildar en oberoende mängd i dess komplementgraf. En graf G:s klicktal, ofta betecknat , är storleken på den största klicken i G. Detta kan även uttryckas som att är det största heltalet r så att den kompletta grafen är en delgraf till G. (sv) Кликой неориентированного графа называется подмножество его вершин, любые две из которых соединены ребром. Клики являются одной из основных концепций теории графов и используются во многих других математических задачах и построениях с графами. Клики изучаются также в информатике — задача определения, существует ли клика данного размера в графе (Задача о клике) является NP-полной. Несмотря на эту трудность, изучаются многие алгоритмы для поиска клик. (ru) |
| rdfs:label | Klika (teorie grafů) (cs) Clique (Graphentheorie) (de) Kliko (grafeteorio) (eo) Clique (graph theory) (en) Clique (es) Clique (théorie des graphes) (fr) Cricca (teoria dei grafi) (it) 클릭 (그래프 이론) (ko) Clique (grafentheorie) (nl) クリーク (グラフ理論) (ja) Klika (teoria grafów) (pl) Clique (pt) Клика (теория графов) (ru) Klick (sv) Кліка (теорія графів) (uk) 團 (圖論) (zh) |
| owl:sameAs | freebase:Clique (graph theory) yago-res:Clique (graph theory) wikidata:Clique (graph theory) dbpedia-cs:Clique (graph theory) dbpedia-de:Clique (graph theory) dbpedia-eo:Clique (graph theory) dbpedia-es:Clique (graph theory) dbpedia-fa:Clique (graph theory) dbpedia-fr:Clique (graph theory) dbpedia-he:Clique (graph theory) dbpedia-hu:Clique (graph theory) dbpedia-it:Clique (graph theory) dbpedia-ja:Clique (graph theory) dbpedia-ko:Clique (graph theory) dbpedia-nl:Clique (graph theory) dbpedia-pl:Clique (graph theory) dbpedia-pt:Clique (graph theory) dbpedia-ro:Clique (graph theory) dbpedia-ru:Clique (graph theory) dbpedia-sr:Clique (graph theory) dbpedia-sv:Clique (graph theory) dbpedia-uk:Clique (graph theory) dbpedia-vi:Clique (graph theory) dbpedia-zh:Clique (graph theory) https://global.dbpedia.org/id/4vREw |
| prov:wasDerivedFrom | wikipedia-en:Clique_(graph_theory)?oldid=1096684789&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/VR_complex.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Clique_(graph_theory) |
| is dbo:knownFor of | dbr:R._Duncan_Luce |
| is dbo:wikiPageDisambiguates of | dbr:Clique_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Clique_number dbr:Maximal_clique dbr:Maximum_clique dbr:K-clique |
| is dbo:wikiPageWikiLink of | dbr:Queen's_graph dbr:Rook's_graph dbr:List_of_algorithms dbr:Binary_logarithm dbr:Binary_relation dbr:András_Hajnal dbr:Answer_set_programming dbr:Antimatroid dbr:Apollonian_network dbr:List_of_graph_theory_topics dbr:Vertex_separator dbr:Independence_complex dbr:Independent_set_(graph_theory) dbr:Induced_subgraph dbr:Induced_subgraph_isomorphism_problem dbr:Intersection_number_(graph_theory) dbr:Kőnig's_theorem_(graph_theory) dbr:List_of_multiple_discoveries dbr:Pearls_in_Graph_Theory dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Matching_in_hypergraphs dbr:Matroid_parity_problem dbr:Median_graph dbr:Elizabeth_Currid-Halkett dbr:Geodetic_graph dbr:Small-world_network dbr:Partial_word dbr:Skew_partition dbr:Neural_clique dbr:Strahler_number dbr:Quadratic_pseudo-Boolean_optimization dbr:Quantum_algorithm dbr:Rado_graph dbr:Clique-sum dbr:Clique_problem dbr:Frank_Harary dbr:Glossary_of_graph_theory dbr:Graph_coloring dbr:Graph_coloring_game dbr:Graph_structure_theorem dbr:Cop-win_graph dbr:Equitable_coloring dbr:Equivalence_class dbr:Erdős–Dushnik–Miller_theorem dbr:Erdős–Hajnal_conjecture dbr:Erdős–Rényi_model dbr:Erdős–Stone_theorem dbr:L_(complexity) dbr:Andrew_M._Gleason dbr:Benjamin_Rossman dbr:Bernoulli_scheme dbr:Line_graph dbr:László_Pyber dbr:Chinese_dictionary dbr:Clique_complex dbr:Clique_cover dbr:Clique_game dbr:Clique_graph dbr:Clique_number dbr:Clique_percolation_method dbr:Cluster_analysis dbr:Clustering_coefficient dbr:Community_structure dbr:Complement_graph dbr:Clique_(disambiguation) dbr:Clique_graph_(disambiguation) dbr:Hamiltonian_decomposition dbr:Partition_function_(mathematics) dbr:Perfect_graph dbr:Mathematical_sociology dbr:Maximum_common_induced_subgraph dbr:Certifying_algorithm dbr:Topology_of_the_World_Wide_Web dbr:Tournament_(graph_theory) dbr:Transitive_closure dbr:Treewidth dbr:Triangle-free_graph dbr:Domatic_number dbr:Dually_chordal_graph dbr:K-tree dbr:Line_graph_of_a_hypergraph dbr:Link_farm dbr:Locally_linear_graph dbr:Takao_Nishizeki dbr:Abstract_simplicial_complex dbr:Barbell_graph dbr:Base-orderable_matroid dbr:Bron–Kerbosch_algorithm dbr:Brooks'_theorem dbr:Brouwer–Haemers_graph dbr:Centrality dbr:Dilworth's_theorem dbr:Global_element dbr:Graphical_model dbr:Graphical_models_for_protein_structure dbr:Kayles dbr:Strongly_connected_component dbr:Tree-depth dbr:Hadwiger_number dbr:Haven_(graph_theory) dbr:Intersection_graph dbr:Interval_graph dbr:JOELib dbr:Power_graph_analysis dbr:Chordal_graph dbr:Albertson_conjecture dbr:Keller's_conjecture dbr:Bipartite_dimension dbr:Block_graph dbr:Cocoloring dbr:Cograph dbr:Coherent_space dbr:Efficiency_(network_science) dbr:Henson_graph dbr:Hereditary_property dbr:Triangulation_(topology) dbr:Width_of_a_hypergraph dbr:Modular_product_of_graphs dbr:Distance-hereditary_graph dbr:Dominating_set dbr:Map_graph dbr:Bull_graph dbr:Split_graph dbr:Splittance dbr:Fibonacci_cube dbr:Greedy_coloring dbr:Greek_letters_used_in_mathematics,_science,_and_engineering dbr:Grothendieck_inequality dbr:Hugo_Hadwiger dbr:Image_segmentation dbr:Kneser_graph dbr:NetworkX dbr:Network_motif dbr:R._Duncan_Luce dbr:Rainbow-independent_set dbr:Ramsey's_theorem dbr:Search_problem dbr:Kirkwood_approximation dbr:Longest_increasing_subsequence dbr:Markov_logic_network dbr:Markov_random_field dbr:Simplex_graph dbr:Vertex_(graph_theory) dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Maria_Silvia_Lucido dbr:Turán's_theorem dbr:Strongly_chordal_graph dbr:Planted_clique dbr:Planted_motif_search dbr:Rent's_rule dbr:Sudoku_graph dbr:Finite_promise_games_and_greedy_clique_sequences dbr:Unfriendly_partition dbr:Stacked_polytope dbr:Strangulated_graph dbr:Maximal_clique dbr:Maximum_clique dbr:Perfect_graph_theorem dbr:Permutation_graph dbr:Topological_graph_theory dbr:Panbiogeography dbr:Vietoris–Rips_complex dbr:Parameterized_complexity dbr:Property_testing dbr:Subcoloring dbr:Turán_graph dbr:Skew-merged_permutation dbr:Twin-width dbr:Strong_positional_game dbr:K-clique |
| is dbp:knownFor of | dbr:R._Duncan_Luce |
| is foaf:primaryTopic of | wikipedia-en:Clique_(graph_theory) |
