Loading AI tools
Da Wikipédia, a enciclopédia livre
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[1]. 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 problemas de cobertura e pode ser resolvido em tempo polinomial.
Formalmente, uma cobertura de arestas de um grafo G é um conjunto de arestas C de tal forma que cada vértice é incidente a pelo menos uma aresta em C. O conjunto C é dito cobrir os vértices de G. A figura a seguir mostra exemplos de coberturas de arestas em dois grafos.
Uma cobertura mínima de arestas é uma cobertura de arestas de menor tamanho possível. O número de cobertura de arestas é o tamanho de uma cobertura mínima de arestas. A figura a seguir mostra exemplos de coberturas de arestas mínimas.
Note que a figura à direita não é apenas uma cobertura de arestas, mas também um acoplamento. Em particular, é um acoplamento perfeito: um acoplamento M, em que cada vértice é incidente a exatamente uma aresta em M. Um acoplamento perfeito é sempre uma cobertura de arestas mínima.
Uma cobertura mínima de arestas pode ser encontrada em tempo polinomial encontrando-se um acoplamento máximo e estendendo-a gulosamente, de modo que todos os vértices sejam cobertos. Na figura a seguir, um acoplamento máximo é marcado com vermelho; as arestas extras que foram adicionadas para cobrir nós não-acoplados são marcadas com azul. (A figura da direita mostra um grafo em que um acoplamento máximo é um acoplamento perfeito; daí que já cobre todos os vértices e nenhuma aresta extra é necessária.)
Por outro lado, o problema relacionado de encontrar uma menor cobertura de vértices e´um problema NP-difícil[2][Nota 1].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.