| dbo:abstract
|
- V matematické disciplíně teorie grafů je vrcholové pokrytí grafu taková podmnožina vrcholů, že každá hrana grafu je incidentní aspoň s jedním vrcholem z této množiny. Minimální vrcholové pokrytí je klasický problém teoretické informatiky a je příkladem NP-úplnosti. Lze ho formulovat jako napůl celočíselný lineární program jehož je maximální párování grafu. (cs)
- Eine Knotenüberdeckung bezeichnet in der Graphentheorie eine Teilmenge der Knotenmenge eines Graphen, die von jeder Kante mindestens einen Endknoten enthält. Das Finden von kleinsten Knotenüberdeckungen gilt als algorithmisch schwierig, denn das damit eng verwandte Knotenüberdeckungsproblem ist NP-vollständig. (de)
- En la disciplina matemática de la teoría de grafos, una cobertura de vértices (en inglés, vertex cover) o simplemente cobertura de un grafo, es un conjunto de vértices tales que cada arista del grafo es incidente a al menos un vértice del conjunto. El problema de encontrar la menor cobertura de vértices en un grafo se denomina problema de la cobertura de vértices. En teoría de la complejidad computacional se ha demostrado que este es un problema NP-completo. La cobertura de vértices y aristas está muy relacionada con los conjuntos independientes y apareamientos o matchings. (es)
- En théorie des graphes et informatique théorique, le problème de couverture minimum par sommets (ou problème du transversal minimum, Vertex Cover en anglais) est un problème algorithmique classique. Il consiste, étant donné un graphe à trouver un ensemble minimum de sommets pour couvrir toutes les arêtes. Le problème de décision associé à ce problème d'optimisation est NP-complet, et fait partie des 21 problèmes NP-complets de Karp. Il est souvent utilisé en théorie de la complexité pour prouver que d'autres problèmes plus compliqués sont NP-complets. (fr)
- Di dalam disiplin matematika tentang teori graf, tutup verteks (bahasa Inggris: vertex cover) adalah himpunan simpul (vertex) di mana di setiap busur (edge) setidaknya dicakup oleh satu simpul (vertex) dari himpunan. Permasalahan yang ditemukan adalah bagaimana mencari vertex cover yang jumlahnya minimum. Permasalahan ini termasuk permasalahan optimasi yang sulit (Hard Problem) dalam ilmu komputer. (in)
- In teoria dei grafi, si dice copertura dei vertici o copertura tramite vertici (in inglese vertex cover) o copertura per nodi, un sottoinsieme S dei nodi di un grafo G=(V,E) tale che tutti gli archi in E abbiano almeno un estremo in S. Il problema di determinare la più piccola copertura tramite vertici di un grafo (detto problema di copertura dei vertici) è un noto problema di ottimizzazione, studiato in teoria della complessità come esempio di problema NP-completo. (it)
- In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimization problem. It is NP-hard, so it cannot be solved by a polynomial-time algorithm if P ≠ NP. Moreover, it is hard to approximate – it cannot be approximated up to a factor smaller than 2 if the unique games conjecture is true. On the other hand, it has several simple 2-factor approximations. It is a typical example of an NP-hard optimization problem that has an approximation algorithm. Its decision version, the vertex cover problem, was one of Karp's 21 NP-complete problems and is therefore a classical NP-complete problem in computational complexity theory. Furthermore, the vertex cover problem is fixed-parameter tractable and a central problem in parameterized complexity theory. The minimum vertex cover problem can be formulated as a half-integral, linear program whose dual linear program is the maximum matching problem. Vertex cover problems have been generalized to hypergraphs, see Vertex cover in hypergraphs. (en)
- Il problema di copertura dei vertici, detto anche in inglese vertex cover, appartiene alla classe di equivalenza dei problemi completi non deterministici, assieme al problema del commesso viaggiatore, il knapsack problem, ecc. Questa classe di problemi è detta NP-completo, si dice cioè che il vertex cover o problema di copertura dei vertici è un problema NP-completo. È utile al riguardo la dimostrazione di equivalenza fra tutti i problemi NP-completo, come premesso. Mediante questi problemi si ottengono, ad esempio, modelli per la logistica o per il calcolo delle spese nella produzione. Il problema complementare al vertex-cover è detto copertura degli spigoli o edge cover. In informatica, il problema di copertura tramite vertici è un problema NP-completo e fu uno dei 21 problemi NP-completi di Richard Karp. È spesso usato in complessità computazionale per dimostrare l'NP-completezza di problemi più complicati. (it)
- 最小頂点被覆問題（さいしょうちょうてんひふくもんだい）は、計算複雑性理論におけるNP困難な問題の一つ。 問題: グラフ G(V, E) の各枝 e について端点のいずれか少なくとも一方が、V′ に含まれるような V の部分集合 V′ のうち、|V′| が最小になるものを求めよ この問題の最適解を求めるのは、NP困難なため、決定性の多項式時間アルゴリズムは存在しないと考えられている。近似アルゴリズムに関して言えば、近似度2の貪欲アルゴリズムが存在することが知られているが、任意の ε > 0 について、近似度 2 - ε の近似度を達成するアルゴリズムも存在しないだろうと考えられている。2005年現在の最良の近似度の下限は、 である。 (ja)
- In de grafentheorie is een knopenbedekking of knopenoverdekking (Engels: vertex cover) van een graaf G een verzameling C van knopen uit de graaf waarvoor geldt dat elke kant van G incident is aan minstens een knoop uit de verzameling C. Anders gezegd: elke kant van G heeft minstens een eindpunt in C. Men zegt dan dat C de kanten van G bedekt. De volgende figuur toont twee voorbeelden van knopenbedekkingen (in het rood): Een minimum-knopenbedekking is een knopenbedekking met het kleinst mogelijk aantal knopen. Dat aantal noemt men het knopenbedekkingsgetal (Engels: vertex covering number) . De volgende figuur toont twee minimum-knopenbedekkingen: Als k knopen in de graaf een clique vormen (zoals de drie linkerknopen in de grafen hierboven), dan maken ten minste k-1 van die knopen deel uit van een minimum-knopenbedekking. Een totale knopenbedekking van G is een knopenbedekking C met de eigenschap dat elke knoop u in C een buur heeft in C. Met andere woorden: de geïnduceerde subgraaf van een totale knopenbedekking is een samenhangende graaf en bevat geen geïsoleerde knopen. De minimale cardinaliteit van alle totale knopenbedekkingen is het totale knopenbedekkingsgetal . Voorbeeld: voor een cyclische graaf met n knopen is het knopenbedekkingsgetal , en het totale knopenbedekkingsgetal . ( is het kleinste geheel getal dat groter of gelijk is aan x). Een totale knopenbedekking is tevens een totale dominerende verzameling. (nl)
- グラフ理論において、グラフGの頂点からなるある集合VがGの頂点被覆（ちょうてんひふく、英: vertex cover）であるとは、Gのどの辺をとってもその端点のどちらかがVに含まれるという意味である。最小頂点被覆を求める問題は計算機科学における古典的な最適化問題であり、近似アルゴリズムのある典型的なNP困難な問題でもある。その決定問題版である頂点被覆問題は計算複雑性理論における古典的なNP完全問題である。さらに頂点被覆問題には (fixed-parameter tractability) があり、の中心問題の1つである。 最小頂点被覆問題は、整数計画問題に定式化でき、その双対問題は最大マッチング問題である。 (ja)
- Pokrycie wierzchołkowe grafu G – taki podzbiór jego wierzchołków, że każda krawędź G jest incydentna do jakiegoś wierzchołka z tego podzbioru. Problem znajdowania najmniejszego pokrycia wierzchołkowego jest problemem NP-zupełnym.
* Przykładowe pokrycie wierzchołkowe w grafie
* Najmniejsze pokrycie wierzchołkowe w grafie (pl)
- Problem pokrycia wierzchołkowego – zagadnienie znajdowania w danym grafie pokrycia wierzchołkowego o najmniejszym rozmiarze, tj. zawierającego możliwie najmniejszą liczbę wierzchołków. Tak zdefiniowany problem pokrycia wierzchołkowego jest problemem optymalizacyjnym. W teorii złożoności obliczeniowej częściej jednak rozważa się problemy decyzyjne. Decyzyjna wersja problemu pokrycia wierzchołkowego, to problem stwierdzania czy w danym grafie istnieje pokrycie wierzchołkowe o danym rozmiarze (pl)
- Na matemática, na disciplina de teoria dos grafos, uma cobertura de vertices de um grafo é um conjunto de vértices tal que cada aresta do grafo é incidente a pelo menos um vértice do conjunto. Ou seja, É um conjunto de vértices que contém pelo menos uma das pontas de cada aresta. Em outras palavras, uma cobertura de vértices é um conjunto V de vértices dotado da seguinte propriedade: toda aresta do grafo tem pelo menos uma ponta em V. O problema de encontrar uma cobertura de vértices mínima é um clássico problema de otimização em ciência da computação e é um exemplo típico de um problema de otimização NP-difícil que tem um algoritmo de aproximação. Esta versão de problema de decisão, o problema da cobertura de vértices, foi um dos 21 problemas NP-completos de Karp e, portanto, um problema NP-completo clássico da teoria da complexidade computacional. Além disso, o problema de cobertura de vértices é tratável em parâmetros fixos e um problema central na teoria da complexidade parametrizada. O problema da cobertura de vértices mínima pode ser formulado como um semi-integral programa linear cujo programa linear dual é o problema do acoplamento máximo. (pt)
- Задача о вершинном покрытии — NP-полная задача информатики в области теории графов. Часто используется в теории сложности для доказательства NP-полноты более сложных задач. (ru)
- Вершинне покриття графа — це множина вершин така, що кожне ребро графа інцидентне хоча б одній вершині цієї множини. Задача знаходження найменшого вершинного покриття є класичною задачею оптимізації в інформатиці і типовим прикладом NP-складної задачі оптимізації, для якої відомий апроксимаційний алгоритм. Її версія у вигляді проблеми вибору, задача вершинного покриття, була однією з 21 NP-повної задачі Карпа і, отже, класичною NP-повною задачею в теорії складності обчислень. Задачу найменшого вершинного покриття можна сформулювати як напівцілочисельну задачу лінійного програмування чия є задача найбільшого парування. (uk)
- 图的覆盖是一個顶点的集合，使图中的每一条边都至少連結該集合中的一个顶点。寻找最小的顶点覆盖的问题称为顶点覆盖问题（），它是一个NP完全问题。 顶点覆盖和边覆盖分别与和匹配问题有关。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 20563 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:title
|
- Vertex Cover (en)
- Minimum Vertex Cover (en)
- Vertex Cover Number (en)
|
| dbp:urlname
|
- MinimumVertexCover (en)
- VertexCover (en)
- VertexCoverNumber (en)
|
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- V matematické disciplíně teorie grafů je vrcholové pokrytí grafu taková podmnožina vrcholů, že každá hrana grafu je incidentní aspoň s jedním vrcholem z této množiny. Minimální vrcholové pokrytí je klasický problém teoretické informatiky a je příkladem NP-úplnosti. Lze ho formulovat jako napůl celočíselný lineární program jehož je maximální párování grafu. (cs)
- Eine Knotenüberdeckung bezeichnet in der Graphentheorie eine Teilmenge der Knotenmenge eines Graphen, die von jeder Kante mindestens einen Endknoten enthält. Das Finden von kleinsten Knotenüberdeckungen gilt als algorithmisch schwierig, denn das damit eng verwandte Knotenüberdeckungsproblem ist NP-vollständig. (de)
- En la disciplina matemática de la teoría de grafos, una cobertura de vértices (en inglés, vertex cover) o simplemente cobertura de un grafo, es un conjunto de vértices tales que cada arista del grafo es incidente a al menos un vértice del conjunto. El problema de encontrar la menor cobertura de vértices en un grafo se denomina problema de la cobertura de vértices. En teoría de la complejidad computacional se ha demostrado que este es un problema NP-completo. La cobertura de vértices y aristas está muy relacionada con los conjuntos independientes y apareamientos o matchings. (es)
- En théorie des graphes et informatique théorique, le problème de couverture minimum par sommets (ou problème du transversal minimum, Vertex Cover en anglais) est un problème algorithmique classique. Il consiste, étant donné un graphe à trouver un ensemble minimum de sommets pour couvrir toutes les arêtes. Le problème de décision associé à ce problème d'optimisation est NP-complet, et fait partie des 21 problèmes NP-complets de Karp. Il est souvent utilisé en théorie de la complexité pour prouver que d'autres problèmes plus compliqués sont NP-complets. (fr)
- Di dalam disiplin matematika tentang teori graf, tutup verteks (bahasa Inggris: vertex cover) adalah himpunan simpul (vertex) di mana di setiap busur (edge) setidaknya dicakup oleh satu simpul (vertex) dari himpunan. Permasalahan yang ditemukan adalah bagaimana mencari vertex cover yang jumlahnya minimum. Permasalahan ini termasuk permasalahan optimasi yang sulit (Hard Problem) dalam ilmu komputer. (in)
- In teoria dei grafi, si dice copertura dei vertici o copertura tramite vertici (in inglese vertex cover) o copertura per nodi, un sottoinsieme S dei nodi di un grafo G=(V,E) tale che tutti gli archi in E abbiano almeno un estremo in S. Il problema di determinare la più piccola copertura tramite vertici di un grafo (detto problema di copertura dei vertici) è un noto problema di ottimizzazione, studiato in teoria della complessità come esempio di problema NP-completo. (it)
- 最小頂点被覆問題（さいしょうちょうてんひふくもんだい）は、計算複雑性理論におけるNP困難な問題の一つ。 問題: グラフ G(V, E) の各枝 e について端点のいずれか少なくとも一方が、V′ に含まれるような V の部分集合 V′ のうち、|V′| が最小になるものを求めよ この問題の最適解を求めるのは、NP困難なため、決定性の多項式時間アルゴリズムは存在しないと考えられている。近似アルゴリズムに関して言えば、近似度2の貪欲アルゴリズムが存在することが知られているが、任意の ε > 0 について、近似度 2 - ε の近似度を達成するアルゴリズムも存在しないだろうと考えられている。2005年現在の最良の近似度の下限は、 である。 (ja)
- グラフ理論において、グラフGの頂点からなるある集合VがGの頂点被覆（ちょうてんひふく、英: vertex cover）であるとは、Gのどの辺をとってもその端点のどちらかがVに含まれるという意味である。最小頂点被覆を求める問題は計算機科学における古典的な最適化問題であり、近似アルゴリズムのある典型的なNP困難な問題でもある。その決定問題版である頂点被覆問題は計算複雑性理論における古典的なNP完全問題である。さらに頂点被覆問題には (fixed-parameter tractability) があり、の中心問題の1つである。 最小頂点被覆問題は、整数計画問題に定式化でき、その双対問題は最大マッチング問題である。 (ja)
- Pokrycie wierzchołkowe grafu G – taki podzbiór jego wierzchołków, że każda krawędź G jest incydentna do jakiegoś wierzchołka z tego podzbioru. Problem znajdowania najmniejszego pokrycia wierzchołkowego jest problemem NP-zupełnym.
* Przykładowe pokrycie wierzchołkowe w grafie
* Najmniejsze pokrycie wierzchołkowe w grafie (pl)
- Problem pokrycia wierzchołkowego – zagadnienie znajdowania w danym grafie pokrycia wierzchołkowego o najmniejszym rozmiarze, tj. zawierającego możliwie najmniejszą liczbę wierzchołków. Tak zdefiniowany problem pokrycia wierzchołkowego jest problemem optymalizacyjnym. W teorii złożoności obliczeniowej częściej jednak rozważa się problemy decyzyjne. Decyzyjna wersja problemu pokrycia wierzchołkowego, to problem stwierdzania czy w danym grafie istnieje pokrycie wierzchołkowe o danym rozmiarze (pl)
- Задача о вершинном покрытии — NP-полная задача информатики в области теории графов. Часто используется в теории сложности для доказательства NP-полноты более сложных задач. (ru)
- 图的覆盖是一個顶点的集合，使图中的每一条边都至少連結該集合中的一个顶点。寻找最小的顶点覆盖的问题称为顶点覆盖问题（），它是一个NP完全问题。 顶点覆盖和边覆盖分别与和匹配问题有关。 (zh)
- In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimization problem. It is NP-hard, so it cannot be solved by a polynomial-time algorithm if P ≠ NP. Moreover, it is hard to approximate – it cannot be approximated up to a factor smaller than 2 if the unique games conjecture is true. On the other hand, it has several simple 2-factor approximations. It is a typical example of an NP-hard optimization problem that has an approximation algorithm. Its decision version, the vertex cover problem, was one of Karp's 21 NP-complete problems and is therefore a classical NP-complete problem in computational complexity th (en)
- Il problema di copertura dei vertici, detto anche in inglese vertex cover, appartiene alla classe di equivalenza dei problemi completi non deterministici, assieme al problema del commesso viaggiatore, il knapsack problem, ecc. In informatica, il problema di copertura tramite vertici è un problema NP-completo e fu uno dei 21 problemi NP-completi di Richard Karp. È spesso usato in complessità computazionale per dimostrare l'NP-completezza di problemi più complicati. (it)
- Na matemática, na disciplina de teoria dos grafos, uma cobertura de vertices de um grafo é um conjunto de vértices tal que cada aresta do grafo é incidente a pelo menos um vértice do conjunto. Ou seja, É um conjunto de vértices que contém pelo menos uma das pontas de cada aresta. Em outras palavras, uma cobertura de vértices é um conjunto V de vértices dotado da seguinte propriedade: toda aresta do grafo tem pelo menos uma ponta em V. O problema da cobertura de vértices mínima pode ser formulado como um semi-integral programa linear cujo programa linear dual é o problema do acoplamento máximo. (pt)
- In de grafentheorie is een knopenbedekking of knopenoverdekking (Engels: vertex cover) van een graaf G een verzameling C van knopen uit de graaf waarvoor geldt dat elke kant van G incident is aan minstens een knoop uit de verzameling C. Anders gezegd: elke kant van G heeft minstens een eindpunt in C. Men zegt dan dat C de kanten van G bedekt. De volgende figuur toont twee voorbeelden van knopenbedekkingen (in het rood): Een totale knopenbedekking is tevens een totale dominerende verzameling. (nl)
- Вершинне покриття графа — це множина вершин така, що кожне ребро графа інцидентне хоча б одній вершині цієї множини. Задача знаходження найменшого вершинного покриття є класичною задачею оптимізації в інформатиці і типовим прикладом NP-складної задачі оптимізації, для якої відомий апроксимаційний алгоритм. Її версія у вигляді проблеми вибору, задача вершинного покриття, була однією з 21 NP-повної задачі Карпа і, отже, класичною NP-повною задачею в теорії складності обчислень. (uk)
|
| rdfs:label
|
- Vrcholové pokrytí (cs)
- Knotenüberdeckung (de)
- Knotenüberdeckungsproblem (de)
- Cobertura de vértices (es)
- Tutup verteks (in)
- Problème de couverture par sommets (fr)
- Problema di copertura dei vertici (it)
- Copertura dei vertici (it)
- 最小頂点被覆問題 (ja)
- 頂点被覆 (ja)
- Knopenbedekking (nl)
- Problem pokrycia wierzchołkowego (pl)
- Pokrycie wierzchołkowe (pl)
- Cobertura de vértices (teoria dos grafos) (pt)
- Задача о вершинном покрытии (ru)
- Vertex cover (en)
- Вершинное покрытие (ru)
- 覆盖 (图论) (zh)
- Вершинне покриття (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
