Em teoria dos grafos, uma pseudofloresta é um grafo não direcionadoO 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. 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 . 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.. 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 .
Notas
Referências
. . . .
Categoria:Teoria dos grafos