|
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
Referências
|
