In graph theory, a clique cover or partition into cliques of a given undirected graph is a partition of the vertices into cliques, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that uses as few cliques as possible. The minimum k for which a clique cover exists is called the clique cover number of the given graph.
| Attributes | Values |
|---|
| rdfs:label
| - Clique cover (en)
- Problema di copertura delle cricche (it)
- Partition en cliques (fr)
- 最小クリーク被覆問題 (ja)
- Задача о кликовом покрытии (ru)
- Cobertura clique (pt)
- Задача про клікове покриття (uk)
- 分團覆蓋問題 (zh)
|
| rdfs:comment
| - In graph theory, a clique cover or partition into cliques of a given undirected graph is a partition of the vertices into cliques, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that uses as few cliques as possible. The minimum k for which a clique cover exists is called the clique cover number of the given graph. (en)
- En théorie des graphes, une couverture par cliques ou une partition en cliques d'un graphe non orienté est une partition des sommets du graphe en cliques, c'est-à-dire en des ensembles de sommets à l'intérieur desquels deux sommets sont adjacents. Un couverture par cliques minimale est une couverture de taille minimale, c'est-à-dire par un nombre minimal de cliques. Le problème de la couverture par cliques est le problème algorithmique qui consiste à trouver une couverture par cliques minimale. (fr)
- 計算量理論において、最小のクリーク被覆（クリークひふく、英: clique cover）を求めることは、グラフ理論的NP完全問題である。クリーク被覆問題はの1つで、そのNP完全性は1972年の論文 "Reducibility Among Combinatorial Problems"（「組合せ論的問題間の還元可能性」）に示されている。 クリーク被覆問題（クリーク分割問題と呼ぶこともある）とは、与えられたグラフの頂点集合を k-個のクリークへ分割できるかを決定する問題である。頂点集合の k-個の集合への分割が与えられたとき、その各集合がクリークを成すかは多項式時間で判定することができるから、クリーク被覆問題はNPに属する。そのNP完全性はグラフの k-彩色可能性からの帰着である。これを見るには、まずグラフ G の k-彩色可能性をその補グラフ G′ に関する事実に翻訳すればよい。このとき G の k-個のクリークへの分割は G′ の k-個の独立集合への分割を求めることに対応する（各集合にそれぞれ別の1つの色を塗ることで k-彩色ができたことになる）。 この問題と関連して、問題は与えられたグラフの辺をすべて含むようなクリークの集合を考えるもので、これもまたNP完全問題である。 (ja)
- 在計算複雜度理論內，找一個最小的分團覆蓋（clique cover）是一個圖論的NP完全問題。這問題屬於卡普的二十一個NP-完全問題之一，由卡普在1972年的論文"Reducibility Among Combinatorial Problems"證明為NP完全。 分團覆蓋問題（有時叫做分成分團，partition into cliques）是問一個圖裡面的所有點可否分成k個。一旦給定了這個圖該怎麼分成k個分團，我們可以在多項式時間裡面檢證這個答案是否正確，因此我們可以知道這個問題屬於NP。 分團覆蓋問題是NP完全這件事情，可以藉由將此問題從k-圖著色問題（GRAPH k-COLOURABILITY）歸約出來而得證。要推出這個結果，首先我們將一個k-圖著色問題的輸入圖G轉成其補圖G'。那麼，求出G' 怎麼分出k個分團這問題就等同於求出G怎麼分出k個獨立集；我們能將每個獨立集設立一個顏色來得到k個顏色，並且保證G內所有相同顏色的點不會互相連接。因此，解出G' 的分團問題，即是解出G的著色問題。因為我們已知k-著色問題是NP完全問題，所以我們能藉由將所有NP的問題先歸約為k-著色問題，再歸約為分團覆蓋問題，而將所有NP完全問題歸約成分團覆蓋問題。故分團覆蓋問題是NP完全問題。 相關的問題則是考慮是否存在分團的集合能包含圖中所有的邊（edge）。這個問題也一樣是NP完全問題。 (zh)
- Nella teoria della complessità computazionale, trovare una copertura delle cricche minima è un problema NP-completo di teoria dei grafi. Il probalma era uno dei 21 problemi originali di Richard Karp che erano stati dimostrati NP-completi nel suo saggio del 1972 Riducibilità tra problemi combinatori (Reducibility among Combinatorial Problems). Il problema correlato della considera gli insiemi delle cricche che comprendono tutti gli spigoli di un dato grafo. Anch'esso è NP-completo. (it)
- Em complexidade computacional, encontrar uma cobertura de clique miníma é um problema NP-completo relacionado à Teoria dos grafos. Este problema foi um dos 21 problemas originais de Karp mostrados serem NP-completos em seu artigo de 1972 "Reducibility Among Combinatorial Problems" (Redutibilidade entre problemas combinatórios). O problema relacionado considera conjuntos de cliques que incluem todas as arestas de um dado caminho. Ele também é NP-completo. (pt)
- Задача о кликовом покрытии — вычислительная задача, заключающаяся в определении возможности разбить вершины графа на клик. Является NP-полной; входит в список из 21 NP-полных задач Карпа. Если дано разбиение вершин на множеств, то можно за полиномиальное время определить, что каждое множество образует клику так, что задача принадлежит классу NP. NP-полнота задачи о кликовом покрытии следует из сведения её к задаче раскраски графа: разложение графа на клик соответствует нахождению разложения вершин дополнения на независимых множеств (каждому из этих множеств можно назначить один цвет, что даст -раскраску). (ru)
- Задача про клікове покриття — обчислювальна задача, яка полягає у визначенні можливості розбити вершини графу на клік. Є NP-повною; входить до числа 21 NP-повних задач Карпа. Якщо дано розбиття вершин на множин, то можна за поліноміальний час визначити, що кожна множина утворює кліку так, що задача належить до класу NP. NP-повнота задачі про клікове покриття випливає зі зведення її до задачі розфарбовування графу: розкладання графу на клік відповідає знаходженню розкладу вершин доповнення на незалежних множин (кожній із цих множин можна призначити один колір, що дасть -розфарбування). (uk)
|
| dct:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - In graph theory, a clique cover or partition into cliques of a given undirected graph is a partition of the vertices into cliques, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that uses as few cliques as possible. The minimum k for which a clique cover exists is called the clique cover number of the given graph. (en)
- En théorie des graphes, une couverture par cliques ou une partition en cliques d'un graphe non orienté est une partition des sommets du graphe en cliques, c'est-à-dire en des ensembles de sommets à l'intérieur desquels deux sommets sont adjacents. Un couverture par cliques minimale est une couverture de taille minimale, c'est-à-dire par un nombre minimal de cliques. Le problème de la couverture par cliques est le problème algorithmique qui consiste à trouver une couverture par cliques minimale. (fr)
- Nella teoria della complessità computazionale, trovare una copertura delle cricche minima è un problema NP-completo di teoria dei grafi. Il probalma era uno dei 21 problemi originali di Richard Karp che erano stati dimostrati NP-completi nel suo saggio del 1972 Riducibilità tra problemi combinatori (Reducibility among Combinatorial Problems). IL problema di copertura delle cricche (a volte chiamato anche partizione in cricche) è il problema di determinare se i vertici di un grafo possono essere ripartiti in k cricche. Data una partizione dei vertici in k insiemi, si può verificare in tempo polinomiale che ciascun insieme forma una cricca, per cui il problema è in NP. La NP-completezza della copertura delle cricche consegue mediante riduzione dalla k-colorabilità del grafo. Per vedere questo, si trasformi dapprima un'istanza G di k-colorabilità del grafo nel suo grafo complemento G'. Una partizione di G' in k cricche corrisponde allora a trovare una partizione dei vertici di G in k insiemi indipendenti; a ognuno di questi insiemi si può allora assegnare un colore per creare una k-colorazione. Il problema correlato della considera gli insiemi delle cricche che comprendono tutti gli spigoli di un dato grafo. Anch'esso è NP-completo. (it)
- 計算量理論において、最小のクリーク被覆（クリークひふく、英: clique cover）を求めることは、グラフ理論的NP完全問題である。クリーク被覆問題はの1つで、そのNP完全性は1972年の論文 "Reducibility Among Combinatorial Problems"（「組合せ論的問題間の還元可能性」）に示されている。 クリーク被覆問題（クリーク分割問題と呼ぶこともある）とは、与えられたグラフの頂点集合を k-個のクリークへ分割できるかを決定する問題である。頂点集合の k-個の集合への分割が与えられたとき、その各集合がクリークを成すかは多項式時間で判定することができるから、クリーク被覆問題はNPに属する。そのNP完全性はグラフの k-彩色可能性からの帰着である。これを見るには、まずグラフ G の k-彩色可能性をその補グラフ G′ に関する事実に翻訳すればよい。このとき G の k-個のクリークへの分割は G′ の k-個の独立集合への分割を求めることに対応する（各集合にそれぞれ別の1つの色を塗ることで k-彩色ができたことになる）。 この問題と関連して、問題は与えられたグラフの辺をすべて含むようなクリークの集合を考えるもので、これもまたNP完全問題である。 (ja)
- Em complexidade computacional, encontrar uma cobertura de clique miníma é um problema NP-completo relacionado à Teoria dos grafos. Este problema foi um dos 21 problemas originais de Karp mostrados serem NP-completos em seu artigo de 1972 "Reducibility Among Combinatorial Problems" (Redutibilidade entre problemas combinatórios). O Problema da cobertura de clique (também chamado as vezes de partição em cliques) é o problema de se determinar se os vértices de um grafo podem ser particionados em k . Dada uma partição dos vertices em k conjuntos, pode ser verificado em [tempo polinomial] que cada conjunto forma um clique, então o problema está em NP. A NP-completude de uma cobertura clique segue de uma redução da k-Colorabilidade de um grafo. Para ver tal redução, primeiros transformamos uma instância G de um k-colorabilidade Grafo em seu Grafo complementar G'. Uma partição de G' em k cliques então corresponde a encontrar uma partição dos vertices de G em k ; a cada um desses conjuntos pode então ser atribuída uma cor para ser produzida uma k-coloração. O problema relacionado considera conjuntos de cliques que incluem todas as arestas de um dado caminho. Ele também é NP-completo. (pt)
- Задача о кликовом покрытии — вычислительная задача, заключающаяся в определении возможности разбить вершины графа на клик. Является NP-полной; входит в список из 21 NP-полных задач Карпа. Если дано разбиение вершин на множеств, то можно за полиномиальное время определить, что каждое множество образует клику так, что задача принадлежит классу NP. NP-полнота задачи о кликовом покрытии следует из сведения её к задаче раскраски графа: разложение графа на клик соответствует нахождению разложения вершин дополнения на независимых множеств (каждому из этих множеств можно назначить один цвет, что даст -раскраску). Минимальный размер кликового покрытия графа — наименьшее число , для которого кликовое покрытие существует. Связанная задача нахождения числа пересечения рассматривает множества клик, включающих все рёбра заданного графа; эта задача также NP-полна. (ru)
- 在計算複雜度理論內，找一個最小的分團覆蓋（clique cover）是一個圖論的NP完全問題。這問題屬於卡普的二十一個NP-完全問題之一，由卡普在1972年的論文"Reducibility Among Combinatorial Problems"證明為NP完全。 分團覆蓋問題（有時叫做分成分團，partition into cliques）是問一個圖裡面的所有點可否分成k個。一旦給定了這個圖該怎麼分成k個分團，我們可以在多項式時間裡面檢證這個答案是否正確，因此我們可以知道這個問題屬於NP。 分團覆蓋問題是NP完全這件事情，可以藉由將此問題從k-圖著色問題（GRAPH k-COLOURABILITY）歸約出來而得證。要推出這個結果，首先我們將一個k-圖著色問題的輸入圖G轉成其補圖G'。那麼，求出G' 怎麼分出k個分團這問題就等同於求出G怎麼分出k個獨立集；我們能將每個獨立集設立一個顏色來得到k個顏色，並且保證G內所有相同顏色的點不會互相連接。因此，解出G' 的分團問題，即是解出G的著色問題。因為我們已知k-著色問題是NP完全問題，所以我們能藉由將所有NP的問題先歸約為k-著色問題，再歸約為分團覆蓋問題，而將所有NP完全問題歸約成分團覆蓋問題。故分團覆蓋問題是NP完全問題。 相關的問題則是考慮是否存在分團的集合能包含圖中所有的邊（edge）。這個問題也一樣是NP完全問題。 (zh)
- Задача про клікове покриття — обчислювальна задача, яка полягає у визначенні можливості розбити вершини графу на клік. Є NP-повною; входить до числа 21 NP-повних задач Карпа. Якщо дано розбиття вершин на множин, то можна за поліноміальний час визначити, що кожна множина утворює кліку так, що задача належить до класу NP. NP-повнота задачі про клікове покриття випливає зі зведення її до задачі розфарбовування графу: розкладання графу на клік відповідає знаходженню розкладу вершин доповнення на незалежних множин (кожній із цих множин можна призначити один колір, що дасть -розфарбування). Найменший розмір клікового покриття графу — найменше число , для якого клікове покриття існує. Пов'язана задача знаходження числа перетинів розглядає множини клік, що включають усі ребра даного графу; ця задача також NP-повна. (uk)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)