Na teoria dos grafos, uma poli-árvore é um grafo direcionado com no máximo um caminho não-direcionado entre quaisquer outros dois vértices. Em outras palavras, uma poli-árvore é um grafo direcionado acíclico (GDA) onde não existem ciclos não-direcionados. Equivalentemente, uma poli-árvore é um grafo direcionado formado pela adição de um direcionamento a cada aresta de uma floresta.

O termo "poli-árvore" foi criado por ; . Poli-árvores são também referenciadas como redes individualmente conectadas. e árvores orientadas..

Estruturas Relacionadas Toda árvore direcionada (um grafo direcionado acíclico no qual existe apenas um nó-fonte que possui caminho único para cada outro nó) é uma poli-árvore, mas nem toda poli-árvore é uma árvore direcionada. Toda poli-árvore é uma multi-árvore, um grafo direcionado acíclico em que um subgrafo acessível a partir de qualquer nó forma uma árvore.

A relação de acessibilidade entre os nós de uma poli-árvore forma uma ordem parcial cuja ordem de dimensão é de no máximo 3. Se a ordem de dimensão é 3, deve existir um subconjunto de sete elemntos x, yi, e zi (para ) tal que, para cada i, ou , ou com estas seis desigualdades definindo a estrutura da poli-árvore para os 7 elementos..

Um poset zigue-zague é um caso especial de uma poli-árvore onde a árvore subjacente é um caminho, e as arestas possuem orientações que se alternam ao longo deste caminho.

Enumeração O número de poli-árvores distintas em n nós não marcados, para n = 1, 2, 3, ..., é 1, 1, 3, 8, 27, 91, 350, 1376, 5743, 24635, 108968, 492180, ... .

Conjectura de Sumner A Conjectura de Sumner, denominada em referência a David Sumner, afirma que um grafo orientado completo (GOC) são grafos universais para poli-árvores, no sentido de que cada GOC com 2n − 2 vértices comtém cada poli-árvore de n vértices como um subgrafo. Embora permaneça sem solução, tem-se provado que GOCs com 3n − 3 vértices são universais nesse sentido.Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2010-09-17.

Aplicações Poli-árvores tem sido usadas como um modelo gráfico para raciocínio probabilístico. Se uma rede Bayesiana possui a estrutura de uma poli-árvore, então a técnica de propagação de crença pode ser utilizada para executar inferências eficientes sobre ela.

A árvore de contorno de uma função real num espaço vetorial é uma poli-árvore que descreve o nível dessa função. Os nós da árvore de contorno são os níveis que passam através de um ponto crítico da função, e as arestas descrevem conjuntos contíguos de pontos sem a passagem por ponto crítico. A orientação de uma aresta é determinada pela comparação entre os valores da função nos dois níveis correspondentes..

Referências

Categoria:Teoria dos grafos