| rdfs:comment
| - Dominancí grafu označujeme mohutnost minimální dominující množiny uzlů. Dominující množinou je taková množina uzlů, která svou množinou sousedních uzlů pokrývá všechny zbývají uzly grafu. (cs)
- El conjunto dominante de un grafo G = (V, E) es un subconjunto V' de V tal que cada vértice que no pertenezca a V' está unido a (al menos) un miembro de V'. El número dominante γ(G) es el cardinal del menor conjunto dominante de G. El problema de la dominación en grafos ha sido estudiado desde la década de los cincuenta, pero el interés por esta área creció significativamente a mediados de los setenta (Hedetniemi y Laskar, 1990). (es)
- En théorie des graphes, un ensemble dominant (ou dominating set en anglais) d'un graphe G = ( S, A ) est un sous-ensemble D de l'ensemble S des sommets tel que tout sommet qui n'appartient pas à D possède au moins une arête d'extrémité un sommet de D. Le problème de l'ensemble dominant est de déterminer, étant donnés G et un entier naturel k, si G possède un ensemble dominant d'au plus k sommets. Ce problème est NP-complet. (fr)
- 支配集合問題（しはいしゅうごうもんだい、英: dominating set）は、グラフ理論における有名なNP困難な問題の一つ。与えられたグラフ G(V, E) の頂点集合 V′ (⊆ V) で、V′ に属さない全ての頂点 v について、v の隣接頂点のいずれか一つが V′ に属するような V′ （支配集合）のうち、最小のものを求める問題。 この問題は、集合被覆問題に含まれるため、集合被覆問題への近似アルゴリズムを適用することで近似度 1 + log|V| の解を得ることができる。また、ある定数 c > 0 について、c log|V| 近似アルゴリズムが存在しないことも示されている。 しかし、平面グラフに対しては、 が存在することも知られている。 (ja)
- In de grafentheorie is een dominerende verzameling van een graaf een deelverzameling van de knopen waarmee elke knoop buiten de dominerende verzameling verbonden is. (nl)
- In graph theory, a dominating set for a graph G is a subset D of its vertices, such that any vertex of G is either in D, or has a neighbor in D. The domination number γ(G) is the number of vertices in a smallest dominating set for G. Dominating sets are of practical interest in several areas. In wireless networking, dominating sets are used to find efficient routes within ad-hoc mobile networks. They have also been used in document summarization, and in designing secure systems for electrical grids. (en)
- Zbiór dominujący (ang. Dominating set) grafu – taki podzbiór zbioru wierzchołków że każdy wierzchołek, który nie należy do ma w tym zbiorze co najmniej jednego sąsiada (jest połączony krawędzią z przynajmniej jednym wierzchołkiem z ). Liczba dominowania (ang. Domination number) grafu – liczba wierzchołków w najmniejszym zbiorze dominującym grafu Liczba dominowania jest oznaczana jako . Liczba totalnego dominowania (ang. Total domination number) grafu – liczba wierzchołków w najmniejszym zbiorze totalnie dominującym grafu Liczba totalnego dominowania jest oznaczana jako .
*
*
*
* (pl)
- Em teoria dos grafos, um conjunto dominante para um grafo G = (V, E) é um subconjunto D de V de tal modo que cada vértice que não está em D é adjacente a pelo menos um membro de D. O número de dominação γ(G) é o número de vértices em um menor conjunto dominante de G. O problema do conjunto dominante refere-se a testar se γ(G) ≤ K para um dado grafo G e entrada K; É um clássico problema de decisão NP-completo em teoria de complexidade computacional. Portanto, acredita-se que não existe um algoritmo eficiente que encontre um menor conjunto dominante para um dado grafo. (pt)
- В теории графов доминирующее множество для графа G = (V, E) — это подмножество D множества вершин V, такое, что любая вершина не из D смежна хотя бы одному элементу из D. Число доминирования γ(G) — это число вершин в наименьшем доминирующем множестве G. (ru)
- У теорії графів, домінівна множина для графа — така підмножина множини вершин що кожна вершина не з є суміжною зі щонайменше однією вершиною з Число домінування — число вершин у найменшій домінівній множині для Задача домінівної множини займається дослідженням чи для певного графа і заданого це класична NP-повна проблема вибору в теорії складності обчислень. Отже вважають, що не існує алгоритму з поліноміальним часом виконання, який знаходить найменшу домінівну множину для заданого графа. (uk)
|
![[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)