Edge cover
http://dbpedia.org/resource/Edge_cover an entity of type: WikicatComputationalProblemsInGraphTheory
En teoría de Grafos , una cobertura de aristas de un grafo es un conjunto de aristas donde cada vértice del grafo es incidente en al menos en una arista del conjunto. En ciencias de la computación, el problema de la cobertura mínima de arista es el problema de encontrar una cobertura de aristas de tamaño mínimo. Este es un problema de optimización que pertenece a la clase de problemas de cobertura y puede resolverse en tiempo polinomial.
rdf:langString
In graph theory, an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set.In computer science, the minimum edge cover problem is the problem of finding an edge cover of minimum size. It is an optimization problem that belongs to the class of covering problems and can be solved in polynomial time.
rdf:langString
Nella teoria dei grafi, una copertura degli spigoli di un grafo è un insieme di spigoli tale che ogni vertice del grafo è incidente ad almeno uno spigolo dell'insieme. Nell'informatica, il problema della copertura minima degli spigoli è il problema di trovare una copertura degli spigoli di dimensione minima. È un problema di ottimizzazione che appartiene alla classe dei e può essere risolto nel tempo polinomiale.
rdf:langString
Em teoria dos grafos, uma cobertura de arestas de um grafo é um conjunto de arestas tal que todo vértice do grafo é incidente a pelo menos uma aresta do conjunto.Em ciência da computação, o problema da cobertura mínima de arestas é o problema de se encontrar uma cobertura de arestas de tamanho mínimo. É um problema de otimização que pertence a classe de e pode ser resolvido em .
rdf:langString
在图论中，图的边覆盖是指一组边的集合，且该集合满足图的每个顶点都在至少一条边上。在计算机科学中，最小边覆盖问题是寻找最小个数边的边覆盖问题。它是属于类的优化问题，可以在多项式时间内求解。
rdf:langString
Dalam Teori graf, edge cover adalah himpunan busur (edge) sehingga setiap simpul (vertex) pada graf insiden dengan setidaknya satu busur dari himpunan. Dalam ilmu komputer, masalah minimum edge cover adalah masalah untuk menemukan edge cover dengan ukuran yang paling minimal. Ini adalah masalah optimasi yang dapat diselesaikan dalam waktu polinomial. Secara formal, sebuah edge cover dari graf G adalah himpunan busur C sehingga setiap simpul insiden dengan setidaknya satu busur dalam himpunan busur C. Dengan kata lain, setiap simpul merupakan ujung dari salahsatu atau lebih busur dalam C. Gambar berikut menunjukkan menunjukkan contoh edge cover dari graf G.C = {(1,2),(1,3),(1,4),(1,5),(1,6)}Setiap simpul dalam V = {1,2,3,4,5,6} insiden dengan setidaknya satu busur di C. Simpul 1 insiden (me
rdf:langString
In de grafentheorie is een kantenbedekking (ook wel bogenbedekking, bogenoverdekking en kantenoverdekking) (Engels: edge cover) van een graaf G een deelverzameling C van de kanten uit de graaf waarvoor geldt dat elke knoop van G het begin- of eindpunt is van minstens een kant uit de verzameling C. Men zegt dan dat C de knopen van G bedekt. De volgende figuur toont twee voorbeelden van kantenbedekkingen:
rdf:langString
Рёберное покрытие графа — это множество рёбер C, такое, что каждая вершина графа инцидентна по меньшей мере одному ребру из C. Следующий рисунок показывает рёберное покрытие двух графов. Наименьшее рёберное покрытие — это рёберное покрытие наименьшего размера. Число рёбер в наименьшем рёберном покрытии графа называется числом рёберного покрытия и обозначается через (в книге Свами, Тхулалирамана — ). Следующий рисунок показывает примеры наименьших рёберных покрытий.
rdf:langString
Ребе́рне покриття́ графа — це множина ребер C, така, що кожна вершина графа інцидентна принаймні одному ребру з C. На малюнку показано реберне покриття двох графів. Найме́нше ребе́рне покриття́ — це реберне покриття найменшого розміру. Число ребер у найменшому реберному покритті графа називають число́м ребе́рного покриття́ і позначають (в книзі Свамі, Тхулалірамана — ). На малюнку показано приклади найменших реберних покриттів. Задача пошуку найменшого реберного покриття є задачею оптимізації, яка належить до класу і може бути розв'язана за поліноміальний час.
rdf:langString
rdf:langString
Kantenüberdeckung
rdf:langString
Cobertura de aristas
rdf:langString
Edge cover
rdf:langString
Edge cover
rdf:langString
Copertura degli spigoli
rdf:langString
Kantenbedekking
rdf:langString
Cobertura de arestas (teoria dos grafos)
rdf:langString
Рёберное покрытие
rdf:langString
Реберне покриття
rdf:langString
边覆盖
xsd:integer
4577392
xsd:integer
1094548179
rdf:langString
Edge Cover
rdf:langString
EdgeCover
rdf:langString
En teoría de Grafos , una cobertura de aristas de un grafo es un conjunto de aristas donde cada vértice del grafo es incidente en al menos en una arista del conjunto. En ciencias de la computación, el problema de la cobertura mínima de arista es el problema de encontrar una cobertura de aristas de tamaño mínimo. Este es un problema de optimización que pertenece a la clase de problemas de cobertura y puede resolverse en tiempo polinomial.
rdf:langString
In graph theory, an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set.In computer science, the minimum edge cover problem is the problem of finding an edge cover of minimum size. It is an optimization problem that belongs to the class of covering problems and can be solved in polynomial time.
rdf:langString
Dalam Teori graf, edge cover adalah himpunan busur (edge) sehingga setiap simpul (vertex) pada graf insiden dengan setidaknya satu busur dari himpunan. Dalam ilmu komputer, masalah minimum edge cover adalah masalah untuk menemukan edge cover dengan ukuran yang paling minimal. Ini adalah masalah optimasi yang dapat diselesaikan dalam waktu polinomial. Secara formal, sebuah edge cover dari graf G adalah himpunan busur C sehingga setiap simpul insiden dengan setidaknya satu busur dalam himpunan busur C. Dengan kata lain, setiap simpul merupakan ujung dari salahsatu atau lebih busur dalam C. Gambar berikut menunjukkan menunjukkan contoh edge cover dari graf G.C = {(1,2),(1,3),(1,4),(1,5),(1,6)}Setiap simpul dalam V = {1,2,3,4,5,6} insiden dengan setidaknya satu busur di C. Simpul 1 insiden (merupakan ujung) dengan busur (1,2), (1,3), (1,4), (1,5), dan (1,6). Simpul 2 insiden dengan busur (1,2). Simpul 3 insiden dengan busur (1,3). Simpul 4 insiden dengan busur (1,4). Simpul 5 insiden dengan busur (1,5). Dan simpul 6 insiden dengan busur (1,6).
rdf:langString
Nella teoria dei grafi, una copertura degli spigoli di un grafo è un insieme di spigoli tale che ogni vertice del grafo è incidente ad almeno uno spigolo dell'insieme. Nell'informatica, il problema della copertura minima degli spigoli è il problema di trovare una copertura degli spigoli di dimensione minima. È un problema di ottimizzazione che appartiene alla classe dei e può essere risolto nel tempo polinomiale.
rdf:langString
In de grafentheorie is een kantenbedekking (ook wel bogenbedekking, bogenoverdekking en kantenoverdekking) (Engels: edge cover) van een graaf G een deelverzameling C van de kanten uit de graaf waarvoor geldt dat elke knoop van G het begin- of eindpunt is van minstens een kant uit de verzameling C. Men zegt dan dat C de knopen van G bedekt. De volgende figuur toont twee voorbeelden van kantenbedekkingen: Een minimum-kantenbedekking is een kantenbedekking met het kleinst mogelijk aantal kanten. Dat aantal noemt men het kantenbedekkingsgetal (Engels: edge covering number) . De volgende figuur toont twee minimum-kantenbedekkingen: Merk op dat de figuur rechts tevens een koppeling voorstelt, en wel een perfecte koppeling M, waarin elke knoop van de graaf begin- of eindpunt is van exact een kant van M. Een perfecte koppeling is altijd een minimum-kantenbedekking. Het vinden van een minimum-kantenbedekking en dus van het kantenbedekkingsgetal is een probleem dat in polynomiale tijd kan opgelost worden door eerst een maximumkoppeling te vinden en daaraan kanten toe te voegen naar de zogenaamde onverzadigde knopen (die geen deel uitmaken van de koppeling). In tegenstelling hiermee is het verwante probleem van het vinden van een minimum-knopenbedekking een NP-moeilijk probleem.
rdf:langString
Рёберное покрытие графа — это множество рёбер C, такое, что каждая вершина графа инцидентна по меньшей мере одному ребру из C. Следующий рисунок показывает рёберное покрытие двух графов. Наименьшее рёберное покрытие — это рёберное покрытие наименьшего размера. Число рёбер в наименьшем рёберном покрытии графа называется числом рёберного покрытия и обозначается через (в книге Свами, Тхулалирамана — ). Следующий рисунок показывает примеры наименьших рёберных покрытий. Заметим, что покрытие правого графа является не только рёберным покрытием, но и паросочетанием. Более того, это паросочетание является совершенным паросочетанием — в нём каждая вершина инцидентна в точности одному ребру паросочетания. Совершенное паросочетание (если существует) всегда является наименьшим рёберным покрытием. Задача поиска наименьшего рёберного покрытия является задачей оптимизации, принадлежит классу и может быть решена за полиномиальное время.
rdf:langString
Em teoria dos grafos, uma cobertura de arestas de um grafo é um conjunto de arestas tal que todo vértice do grafo é incidente a pelo menos uma aresta do conjunto.Em ciência da computação, o problema da cobertura mínima de arestas é o problema de se encontrar uma cobertura de arestas de tamanho mínimo. É um problema de otimização que pertence a classe de e pode ser resolvido em .
rdf:langString
Ребе́рне покриття́ графа — це множина ребер C, така, що кожна вершина графа інцидентна принаймні одному ребру з C. На малюнку показано реберне покриття двох графів. Найме́нше ребе́рне покриття́ — це реберне покриття найменшого розміру. Число ребер у найменшому реберному покритті графа називають число́м ребе́рного покриття́ і позначають (в книзі Свамі, Тхулалірамана — ). На малюнку показано приклади найменших реберних покриттів. Зауважимо, що покриття правого графа є не тільки реберним покриттям, але й паруванням. Більш того, це парування є досконалим паруванням — у ньому кожна вершина відповідає рівно одному ребру парування. Досконале парування (якщо існує) завжди є найменшим реберним покриттям. Задача пошуку найменшого реберного покриття є задачею оптимізації, яка належить до класу і може бути розв'язана за поліноміальний час.
rdf:langString
在图论中，图的边覆盖是指一组边的集合，且该集合满足图的每个顶点都在至少一条边上。在计算机科学中，最小边覆盖问题是寻找最小个数边的边覆盖问题。它是属于类的优化问题，可以在多项式时间内求解。
xsd:nonNegativeInteger
3579
