![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/0/03/Directed_acyclic_graph_2.svg/langpt-640px-Directed_acyclic_graph_2.svg.png&w=640&q=50)
Conjunto de arcos de realimentação
De Wikipedia, a enciclopédia encyclopedia
Em teoria dos grafos, um grafo direcionado pode conter ciclos direcionados, um loop formado por um ciclo através de arestas. Em algumas aplicações, estes ciclos são indesejados, e queremos eliminá-los para obter um grafo acíclico direcionado (GAD). Uma maneira de fazer isso é simplesmente retirar arestas do grafo para remover os ciclos. Um conjunto de arcos de realimentação (CAR) ou conjunto de arestas de realimentação é um conjunto de arestas que, quando são retiradas do grafo, levam a um GAD. Em outras palavras é um conjunto que contém pelo menos uma aresta de cada ciclo existente no grafo.
![]() | As referências deste artigo necessitam de formatação. (Julho de 2015) |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/03/Directed_acyclic_graph_2.svg/220px-Directed_acyclic_graph_2.svg.png)
Estreitamente relacionado é o conjunto de vértices de realimentação, que é um conjunto de vértices que contém ao menos um vértice de cada ciclo no grafo direcionado, e a árvore de extensão mínima, que é a forma não dirigida do problema do conjunto de arcos de realimentação.
Um conjunto de arcos de realimentação mínimo (que não pode ser reduzido em tamanho por remoção de quaisquer arestas) tem a propriedade adicional de que, se as arestas forem invertidas ao invés de removidas, então o grafo permanece acíclico. Encontrar um pequeno conjunto de arestas com essa propriedade é um passo fundamental no desenho do grafo em camadas.
Às vezes é desejável retirar tão poucas arestas quanto possível, obtendo um conjunto de arcos de realimentação mínimo, ou um subgrafo acíclico máximo. Isto é um problema computacional difícil, para o qual várias soluções aproximadas foram criadas.