| 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)
|
| 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)
|
