Conjunto de arcos de realimentação: diferenças entre revisões

Origem: Wikipédia, a enciclopédia livre.
Explorar interativamente o histórico
← Ver a alteração anteriorVer a alteração posterior →
Conteúdo apagado Conteúdo adicionado
VisualTexto wiki
Os links das referências foram colocados como ligação externa.
concordancia
Linha 1: Linha 1:
{{Formatar referências|data=julho de 2015}}
{{Formatar referências|data=julho de 2015}}
[[Imagem:Directed_acyclic_graph_2.svg|thumb|Este grafo não contém ciclos: Não é possível chegar em um vértice (ponto) e voltar para o mesmo ponto, seguindo as conexões nas direções indicadas pelas setas.]]
[[Imagem:Directed_acyclic_graph_2.svg|thumb|Este grafo não contém ciclos: Não é possível chegar em um vértice (ponto) e voltar para o mesmo ponto, seguindo as conexões nas direções indicadas pelas setas.]]
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 dirigido (GAD). Uma maneira de fazer isso é simplesmente retirar arestas do grafo para retirar 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.
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.


São estreitamente relacionadas com o conjunto de vértices de realimentação, que é um conjunto de vértices que contem ao menos um vértice de cada ciclo no grafo dirigido, e a árvore de extensão mínima, que é a forma não dirigida do problema do conjunto de arcos de realimentação.
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 que, as arestas são invertidas ao invés de removidas, onde o grafo permanece acíclico. Encontrar um pequeno conjunto de arestas com essa propriedade é um passo fundamental no desenho do grafo em camadas.
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 tantas poucas arestas quanto o 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.
À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.


== Exemplo ==
== Exemplo ==
Como um simples exemplo, considere a seguinte situação hipotética, onde a fim de alcançar algo, certas coisas devem ser alcançadas antes de outras coisas:
Como um exemplo simples, considere a seguinte situação hipotética, onde a fim de alcançar algo, certas coisas devem ser alcançadas antes de outras coisas:
* Seu objetivo é obter um cortador de grama.
* Seu objetivo é obter um cortador de grama.
* George diz que ele vai dar-lhe um piano, mas apenas em troca de um cortador de grama.
* George diz que ele vai dar-lhe um piano, mas apenas em troca de um cortador de grama.
* Harry diz que vai lhe dar um cortador de grama, mas apenas em troca de um micro-ondas.
* Harry diz que vai lhe dar um cortador de grama, mas apenas em troca de um micro-ondas.
* Jane diz que ela vai lhe dar um micro-ondas, mas apenas em troca de um piano.
* Jane diz que ela vai lhe dar um micro-ondas, mas apenas em troca de um piano.
Podemos expressar isso como um problema de grafo. Pegue cada vértice que representa um item e adicione uma aresta de A para B, se você deve ter A para poder obter B. Infelizmente, você não tem qualquer um dos três itens, e como este grafo é cíclico, você não é pode obter qualquer um deles também.
Podemos expressar isso como um problema de grafo. Pegue cada vértice que representa um item e adicione uma aresta de A para B, se você deve ter A para poder obter B. Infelizmente, você não tem nenhum dos três itens, e como este grafo é cíclico, você não pode obter nenhum deles também.


No entanto, suponha que você oferece $100 a George pelo piano. Se ele aceitar, isso efetivamente remove a aresta do cortador de grama para o piano, porque você não precisa mais do cortador de grama para obter o piano. Consequentemente, o ciclo é quebrado, e você pode negociar duas vezes para obter o cortador de grama. Esta aresta constitui um conjunto de arcos de realimentação.
No entanto, suponha que você ofereça $100 a George pelo piano. Se ele aceitar, isso efetivamente remove a aresta do cortador de grama para o piano, porque você não precisa mais do cortador de grama para obter o piano. Consequentemente, o ciclo é quebrado, e você pode negociar duas vezes para obter o cortador de grama. Esta aresta constitui um conjunto de arcos de realimentação.


== Conjunto de arcos de realimentação mínimo ==
== Conjunto de arcos de realimentação mínimo ==
Tal como no exemplo acima, há geralmente um custo associado com a remoção de uma aresta. Por esta razão, nós gostaríamos de remover tantas poucas arestas quanto possível. Remover uma das arestas em um ciclo simples é suficiente, mas, em geral, descobrir o número mínimo de arestas a serem removidas é um problema [[NP-difícil|NP-Difícil]] chamado de conjunto de arcos de realimentação mínimo ou problema do subgrafo acíclico máximo.
Tal como no exemplo acima, há geralmente um custo associado com a remoção de uma aresta. Por esta razão, gostaríamos de remover tão poucas arestas quanto possível. Remover uma das arestas em um ciclo simples é suficiente, mas, em geral, descobrir o número mínimo de arestas a serem removidas é um problema [[NP-difícil|NP-Difícil]] chamado de conjunto de arcos de realimentação mínimo ou problema do subgrafo acíclico máximo.


=== Resultados Teóricos ===
=== Resultados Teóricos ===
Este problema é particularmente difícil no [[grafo k-aresta-conexo|<nowiki/>]][[Grafo k-aresta-conexo]] para largura k, onde cada aresta recai em muitos ciclos diferentes. A versão de decisão do problema, que é NP-completo, pergunta se todos os ciclos podem ser quebrados pela remoção da maior quantidade de k arestas; este foi um dos 21 problemas NP-completos de [[Richard Karp|Richard M. Karp]], provados através da redução da [[Cobertura de vértices (teoria dos grafos)|cobertura de vértices]].
Este problema é particularmente difícil no [[grafo k-aresta-conexo|<nowiki/>]][[Grafo k-aresta-conexo]] para largura k, onde cada aresta recai em muitos ciclos diferentes. A versão de decisão do problema, que é NP-completo, pergunta se todos os ciclos podem ser quebrados pela remoção da maior quantidade de k arestas; este foi um dos 21 problemas NP-completos de [[Richard Karp|Richard M. Karp]], provados a partir da redução da [[Cobertura de vértices (teoria dos grafos)|cobertura de vértices]].


Apesar de ser NP-completo, o conjunto de arcos de realimentação e um [[:en:Parameterized_complexity#FPT|ftp]]: existe um algoritmo para soluciona-lo o qual o tempo te execução é polinomial no tamanho do grafo de entrada (independentemente do numero de arestas no conjunto)mas exponencial no numero de vértices no conjunto de arcos de realimentação
Embora NP-completo, o conjunto de arcos de realimentação é um [[:en:Parameterized_complexity#FPT|ftp]]: existe um algoritmo para solucioná-lo cujo tempo de execução é um polinômio fixado no tamanho do grafo de entrada (independentemente do número de arestas no conjunto) mas exponencial no número de vértices no conjunto de arcos de realimentação.


Viggo Kann mostrou em 1992 que o problema do conjunto de arcos de realimentação mínimo é [[Apx completude]], isso significa que existe uma constante c, tal que, assumindo que P≠NP, não existe um algoritmo de aproximação de tempo polinomial que sempre encontram um conjunto de arestas no máximo c vezes maior que o resultado ótimo. A partir de <span>2006</span><sup class="plainlinks noprint asof-tag update" style="display:none;">[//en.wikipedia.org/w/index.php?title=Feedback_arc_set&action=edit &#x5B;update&#x5D;][//en.wikipedia.org/w/index.php?title=Feedback_arc_set&action=edit]</sup>, o maior valor de c para tal qual um resultado improvável conhecido é ''c'' = 1.3606. O melhor algoritmo de aproximação conhecido tem tempo ''O''(log ''n'' log log ''n''). Para o duplo problema de aproximar o máximo numero de arestas em um subgrafo acíclico a uma aproximação um pouco melhor que 1/2 é possível.
Viggo Kann mostrou em 1992 que o problema do conjunto de arcos de realimentação mínimo é Apx-difícil, isso significa que existe uma constante c, tal que, assumindo que P≠NP, não existe um algoritmo de aproximação de tempo polinomial que sempre encontra um conjunto de arestas no máximo c vezes maior que o resultado ótimo. A partir de <span>2006</span><sup class="plainlinks noprint asof-tag update" style="display:none;">[//en.wikipedia.org/w/index.php?title=Feedback_arc_set&action=edit &#x5B;update&#x5D;][//en.wikipedia.org/w/index.php?title=Feedback_arc_set&action=edit]</sup>, o maior valor de c para o qual um resultado de impossibilidade é conhecido é ''c'' = 1.3606. O melhor algoritmo de aproximação conhecido tem tempo ''O''(log ''n'' log log ''n''). Para o duplo problema de aproximar o máximo número de arestas em um subgrafo acíclico, uma aproximação um pouco melhor que 1/2 é possível.


Se os dígrafos de entrada são restritos para serem desafiadores, o problema resultante é conhecido como o problema de conjunto de arcos de realimentação mínimo sobre torneios ''(FAST)''. Este problema restrito admite um [[:en:Polynomial-time_approximation_scheme|esquema de aproximação de tempo polinomial]], E ele ainda é valido para a versão ponderada do problema. Um algoritmo de parâmetro fixo subexponencial para ponderar rapidamente FAST foi dado por {{Harvtxt|Karpinski|Schudy|2010}}.
Se os dígrafos de entrada são restritos a torneios (do inglês, ''tournaments''), o problema resultante é conhecido como o ''problema de conjunto de arcos de realimentação mínimo sobre torneios'' ''(FAST)''. Este problema restrito admite um [[:en:Polynomial-time_approximation_scheme|esquema de aproximação de tempo polinomial]], e isso ainda é valido para a versão ponderada do problema. Um algoritmo de parâmetro fixo subexponencial para ponderar rapidamente FAST foi dado por {{Harvtxt|Karpinski|Schudy|2010}}.


Por outro lado, se as arestas são uni-direcionadas, o problema de remover arestas para fazer o grafo de ciclo liver é equivalente a encontrar uma [[Árvore de extensão mínima|Arvore de extensão mínima]] , a qual pode ser feita facilmente em tempo polinomial.
Por outro lado, se as arestas são não-direcionadas, o problema de remover arestas para tornar o grafo livre de ciclo é equivalente a encontrar uma [[Árvore de extensão mínima|Arvore de extensão mínima]], a qual pode ser feita facilmente em tempo polinomial.


=== Aproximações ===
=== Aproximações ===
Vários algoritmos de aproximação para o problema tem sido desenvolvidos. Um algoritmo particularmente simples é descrito a seguir:
Vários algoritmos de aproximação para o problema têm sido desenvolvidos. Um algoritmo particularmente simples é descrito a seguir:
* Corrigir uma permutação arbitraria dos vértices, ou seja, rotula-los de 1 a {{Mvar|n}}.
* Fixe uma permutação arbitrária dos vértices, ou seja, rotule-os de 1 a {{Mvar|n}}.
* Construa dois subgrafos L e R, que contém as arestas (u, v), onde u < v, e aqueles em que u > v, respectivamente.
* Construa dois subgrafos L e R, que contém as arestas (u, v), onde u < v, e aqueles em que u > v, respectivamente.
Agora ambos L e R são subgrafos acíclicos de L, e pelo menos um deles é pelo menos metade do tamanho do subgrafo máximo acíclico.
Agora ambos L e R são subgrafos acíclicos de L, e pelo menos um deles é pelo menos metade do tamanho do subgrafo máximo acíclico.

Revisão das 15h59min de 17 de julho de 2015

Este grafo não contém ciclos: Não é possível chegar em um vértice (ponto) e voltar para o mesmo ponto, seguindo as conexões nas direções indicadas pelas setas.

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.

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.

Exemplo

Como um exemplo simples, considere a seguinte situação hipotética, onde a fim de alcançar algo, certas coisas devem ser alcançadas antes de outras coisas:

  • Seu objetivo é obter um cortador de grama.
  • George diz que ele vai dar-lhe um piano, mas apenas em troca de um cortador de grama.
  • Harry diz que vai lhe dar um cortador de grama, mas apenas em troca de um micro-ondas.
  • Jane diz que ela vai lhe dar um micro-ondas, mas apenas em troca de um piano.

Podemos expressar isso como um problema de grafo. Pegue cada vértice que representa um item e adicione uma aresta de A para B, se você deve ter A para poder obter B. Infelizmente, você não tem nenhum dos três itens, e como este grafo é cíclico, você não pode obter nenhum deles também.

No entanto, suponha que você ofereça $100 a George pelo piano. Se ele aceitar, isso efetivamente remove a aresta do cortador de grama para o piano, porque você não precisa mais do cortador de grama para obter o piano. Consequentemente, o ciclo é quebrado, e você pode negociar duas vezes para obter o cortador de grama. Esta aresta constitui um conjunto de arcos de realimentação.

Conjunto de arcos de realimentação mínimo

Tal como no exemplo acima, há geralmente um custo associado com a remoção de uma aresta. Por esta razão, gostaríamos de remover tão poucas arestas quanto possível. Remover uma das arestas em um ciclo simples é suficiente, mas, em geral, descobrir o número mínimo de arestas a serem removidas é um problema NP-Difícil chamado de conjunto de arcos de realimentação mínimo ou problema do subgrafo acíclico máximo.

Resultados Teóricos

Este problema é particularmente difícil no Grafo k-aresta-conexo para largura k, onde cada aresta recai em muitos ciclos diferentes. A versão de decisão do problema, que é NP-completo, pergunta se todos os ciclos podem ser quebrados pela remoção da maior quantidade de k arestas; este foi um dos 21 problemas NP-completos de Richard M. Karp, provados a partir da redução da cobertura de vértices.

Embora NP-completo, o conjunto de arcos de realimentação é um ftp: existe um algoritmo para solucioná-lo cujo tempo de execução é um polinômio fixado no tamanho do grafo de entrada (independentemente do número de arestas no conjunto) mas exponencial no número de vértices no conjunto de arcos de realimentação.

Viggo Kann mostrou em 1992 que o problema do conjunto de arcos de realimentação mínimo é Apx-difícil, isso significa que existe uma constante c, tal que, assumindo que P≠NP, não existe um algoritmo de aproximação de tempo polinomial que sempre encontra um conjunto de arestas no máximo c vezes maior que o resultado ótimo. A partir de 2006, o maior valor de c para o qual um resultado de impossibilidade é conhecido é c = 1.3606. O melhor algoritmo de aproximação conhecido tem tempo O(log n log log n). Para o duplo problema de aproximar o máximo número de arestas em um subgrafo acíclico, uma aproximação um pouco melhor que 1/2 é possível.

Se os dígrafos de entrada são restritos a torneios (do inglês, tournaments), o problema resultante é conhecido como o problema de conjunto de arcos de realimentação mínimo sobre torneios (FAST). Este problema restrito admite um esquema de aproximação de tempo polinomial, e isso ainda é valido para a versão ponderada do problema. Um algoritmo de parâmetro fixo subexponencial para ponderar rapidamente FAST foi dado por Karpinski & Schudy (2010).

Por outro lado, se as arestas são não-direcionadas, o problema de remover arestas para tornar o grafo livre de ciclo é equivalente a encontrar uma Arvore de extensão mínima, a qual pode ser feita facilmente em tempo polinomial.

Aproximações

Vários algoritmos de aproximação para o problema têm sido desenvolvidos. Um algoritmo particularmente simples é descrito a seguir:

  • Fixe uma permutação arbitrária dos vértices, ou seja, rotule-os de 1 a n.
  • Construa dois subgrafos L e R, que contém as arestas (u, v), onde u < v, e aqueles em que u > v, respectivamente.

Agora ambos L e R são subgrafos acíclicos de L, e pelo menos um deles é pelo menos metade do tamanho do subgrafo máximo acíclico.

Referências

  1. Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), "Layered Drawings of Digraphs", Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, pp. 265–302, ISBN 9780133016154.
  2. Bastert, Oliver; Matuszewski, Christian (2001), "Layered drawings of digraphs", in Kaufmann, Michael; Wagner, Dorothea, Drawing Graphs: Methods and Models, Lecture Notes in Computer Science 2025, Springer-Verlag, pp. 87–120,doi:10.1007/3-540-44969-8_5.
  3. Karp, Richard M. (1972), "Reducibility Among Combinatorial Problems", Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., New York: Plenum, pp. 85–103.
  4. Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, A1.1: GT8, p. 192, ISBN 0-7167-1045-5.
  5. Chen, Jianer; Liu, Yang; Lu, Songjian; O'Sullivan, Barry; Razgon, Igor (2008), "A fixed-parameter algorithm for the directed feedback vertex set problem", Journal of the ACM 55 (5), doi:10.1145/1411509.1411511.
  6. Kann, Viggo (1992), On the Approximability of NP-complete Optimization Problems (PDF), Ph.D. thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm.
  7. Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000), "Minimum Feedback Arc Set", A compendium of NP optimization problems.
  8. Dinur, Irit; Safra, Samuel (2005), "On the hardness of approximating minimum vertex cover" (PDF), Annals of Mathematics 162 (1): 439–485, doi:10.4007/annals.2005.162.439. (Preliminary version in STOC 2002, titled "The importance of being biased", doi:10.1145/509907.509915.)
  9. Even, G.; Naor, J.; Schieber, B.; Sudan, M. (1998), "Approximating minimum feedback sets and multicuts in directed graphs", Algorithmica 20 (2): 151–174, doi:10.1007/PL00009191, MR 1484534.
  10. Berger, B.; Shor, P. (1990), "Approximation algorithms for the maximum acyclic subgraph problem", Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA’90), pp. 236–243.
  11. Eades, P.; Lin, X.; Smyth, W. F. (1993), "A fast and effective heuristic for the feedback arc set problem", Information Processing Letters 47: 319–323, doi:10.1016/0020-0190(93)90079-O.
  12. Kenyon-Mathieu, Claire; Schudy, Warren (2007), "How to rank with few errors: a PTAS for weighted feedback arc set on tournaments", Proc. 39th ACM Symposium on Theory of Computing (STOC '07), pp. 95–103,doi:10.1145/1250790.1250806, MR 2402432. See also author's extended version.
  13. Karpinski, M.; Schudy, W. (2010), "Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament", Proc. 21st ISAAC (2010), Lecture Notes in Computer Science 6506, pp. 3–14,doi:10.1007/978-3-642-17517-6_3.
  14. Hassin, Refael; Rubinstein, Shlomi (1994). "Approximations for the maximum acyclic subgraph problem". Information Processing Letters 51 (3): 133–140. doi:10.1016/0020-0190(94)00086-7. CiteSeerX: 10.1.1.39.7717. 
  15. Skiena, Steven (2010). The Algorithm Design Manual (2nd ed.). Springer Science+Business Media. pp. 348; 559–561.ISBN 1-849-96720-2.
Obtida de "https://pt.wikipedia.org/w/index.php?title=Conjunto_de_arcos_de_realimentação&oldid=42890385"