| 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)
|
![[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)
![[RDF Data]](/fct/images/sw-rdf-blue.png)