| dbo:abstract
|
- 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)
- 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. The dominating set problem concerns testing whether γ(G) ≤ K for a given graph G and input K; it is a classical NP-complete decision problem in computational complexity theory. Therefore it is believed that there may be no efficient algorithm that can compute γ(G) for all graphs G. However, there are efficient approximation algorithms, as well as efficient exact algorithms for certain graph classes. 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)
- 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)
- 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. As figuras (a)-(c) à direita mostram exemplos de árvores para conjuntos dominantes de um grafo. Em cada exemplo, cada vértice branco é adjacente a pelo menos um vértice vermelho, e dizemos que o vértice branco é dominado pelo vértice vermelho. O número de dominação do grafo é 2: Os exemplos (b)-(c) mostram que cada conjunto dominante possui dois vértices, e que pode ser verificado que não há conjunto dominante com apenas um vértice. (pt)
- 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 . Zbiór totalnie dominujący (ang. Total dominating set) grafu – taki zbiór dominujący w którym każdy wierzchołek z ma co najmniej jednego sąsiada w Oznacza to, że każdy wierzchołek z jest incydentalny do innego wierzchołka z . 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 .
* Przykładowy zbiór dominujący (nie totalnie) w grafie
* Przykładowy zbiór totalnie dominujący w grafie
* Najmniejszy zbiór dominujący (nie totalnie), liczba dominowania – 3
* Najmniejszy zbiór totalnie dominujący, liczba totalnego dominowania – 3 (pl)
- В теории графов доминирующее множество для графа G = (V, E) — это подмножество D множества вершин V, такое, что любая вершина не из D смежна хотя бы одному элементу из D. Число доминирования γ(G) — это число вершин в наименьшем доминирующем множестве G. Задача о доминирующем множестве заключается в проверке, верно ли неравенство γ(G) ≤ K для заданного графа G и числа K. Задача является классической NP-полной проблемой разрешимости в теории вычислительной сложности. Таким образом полагают, что не существует эффективного алгоритма для нахождения наименьшего доминирующего множества для заданного графа. Рисунки (a)-(c) справа показывают три примера доминирующих множеств графа. В этих примерах каждая белая вершина смежна по меньшей мере одной красной вершине и говорят, что белые вершины доминируются красными вершинами. Доминирующее число этого графа равно 2 — примеры (b) и (c) показывают, что существует доминирующее множество с 2 вершинами, и можно проверить, что для данного графа не существует доминирующего множества лишь с одной вершиной. (ru)
- У теорії графів, домінівна множина для графа — така підмножина множини вершин що кожна вершина не з є суміжною зі щонайменше однією вершиною з Число домінування — число вершин у найменшій домінівній множині для Задача домінівної множини займається дослідженням чи для певного графа і заданого це класична NP-повна проблема вибору в теорії складності обчислень. Отже вважають, що не існує алгоритму з поліноміальним часом виконання, який знаходить найменшу домінівну множину для заданого графа. Зображення (a)–(c) праворуч, наводять три приклади домінівних множин на графі. У кожному прикладі, кожна біла вершина є суміжною хоча б з однією червоною вершиною, у такому випадку кажуть, що червоні вершини домінують над білими. Число домінування цього графа є 2: Приклади (b) і (c) показують, що існують домінівні множини з 2 вершинами, і можна перевірити, що для цього графа немає домінівної множини, що складається з 1 вершини. (uk)
|
| 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)
|
