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

↑ 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

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 .