Pseudofloresta
Em teoria dos grafos, uma pseudofloresta é um grafo não direcionado[1] em que cada componente conectado tem no máximo um ciclo. Ou seja, é um sistema de vértices e arestas que conectam pares de vértices, de tal modo que não há dois ciclos consecutivos de arestas compartilhando qualquer vértice com o outro, nem podem ser quaisquer dois ciclos ligados uns aos outros por um caminho de arestas consecutivos. Uma pseudoárvore é uma pseudofloresta conectada.
Os nomes são justificados por analogia em relação as árvores e florestas mais comumente estudadas (uma árvore é um grafo sem ciclos; uma floresta é uma união disjunta de árvores). Gabow e Tarjan [2] atribuem o estudo das pseudoflorestas ao livro de programação linear de Dantzig's (1993), em que pseudoflorestas surgem na solução de certos problemas de fluxo em redes[3]. Pseudoflorestas também formam modelos de grafos teóricos de funções e ocorrem em muitos problemas de algoritmos. Pseudoflorestas são grafos esparsos - eles tem muito poucas arestas em relação ao número de vértices - e sua estrutura matroide permite que muitas outras famílias de grafos esparsos sejam decompostas como a união de florestas e pseudoflorestas. O nome "pseudofloresta" vem de Picard & Queyranne (1982).
Notas
[editar | editar código-fonte]- ↑ O tipo de grafo não direcionado considerado aqui é frequentemente chamado de um multígrafo ou pseudógrafo, para realizar a distinção entre ele e um grafo simples.
- ↑ Gabow & Tarjan (1988).
- ↑ Dantzig (1963).
Referências
[editar | editar código-fonte]- Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), Network Flows: Theory, Algorithms and Applications (em inglês), ISBN 0-13-617549-X, Prentice Hall.
- Gabow, H. N.; Tarjan, R. E. (1988), «A linear-time algorithm for finding a minimum spanning pseudoforest», Information Processing Letters, 27 (5): 259–263, doi:10.1016/0020-0190(88)90089-0.
- Dantzig, G. B. (1963), Linear Programming and Extensions (em inglês), Princeton University Press.
- Picard, Jean-Claude; Queyranne, Maurice (1982), «A network flow solution to some nonlinear 0–1 programming problems, with applications to graph theory (em inglês)», Networks, 12 (2): 141–159, MR 670021, doi:10.1002/net.3230120206.
