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.

Uma poli-árvore simples

O termo "poli-árvore" foi criado por Rebane & Pearl (1987);[1] Poli-árvores são também referenciadas como redes individualmente conectadas[2] e árvores orientadas.[3][4]

Estruturas Relacionadas editar

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 i = 0, 1, 2) tal que, para cada i, ou xyizi, ou xyizi, com estas seis desigualdades definindo a estrutura da poli-árvore para os 7 elementos.[5]

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 editar

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, ... (sequência A000238 na OEIS).

Conjectura de Sumner editar

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.[6][7]

Aplicações editar

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.[1][2]

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.[8]

Referências editar

  1. a b Rebane, George; Pearl, Judea (1987), «The recovery of causal poly-trees from statistical data», Proceedings of UAI (PDF), pp. 222–228 .
  2. a b Kim, J., J. H.; Pearl (1983), «A computational model for causal and diagnostic reasoning in inference engines», Proc. of the Eighth International Joint Conference on Artificial Intelligence, pp. 190–193 .
  3. Harary, Frank; Sumner, David (1980), «The dichromatic number of an oriented tree», Journal of Combinatorics, Information & System Sciences, 5 (3): 184–187, MR 603363 
  4. Simion, Rodica (1991), «Trees with 1-factors and oriented trees», Discrete Mathematics, 88 (1): 93–104, MR 1099270, doi:10.1016/0012-365X(91)90061-6 .
  5. Trotter, William T., Jr.; Moore, John I., Jr. (1977), «The dimension of planar posets», Journal of Combinatorial Theory, Series B, 22 (1): 54–67, doi:10.1016/0095-8956(77)90048-X .
  6. Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2010-09-17.
  7. El Sahili, A. (2004), «Trees in tournaments», Journal of Combinatorial Theory. Series B, 92 (1): 183–187, MR 2078502, doi:10.1016/j.jctb.2004.04.002 
  8. Carr, Hamish; Snoeyink, Jack; Axen, Ulrike (2000), «Computing contour trees in all dimensions», Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), pp. 918–926 .