Poliárvore

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Uma poli-árvore simples

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 Rebane & Pearl (1987);[1] Poli-árvores são também referenciadas como redes individualmente conectadas[2] e árvores orientadas.[3] [4]

Estruturas Relacionadas[editar | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

  1. a b Rebane, George; Pearl, Judea (1987), "The recovery of causal poly-trees from statistical data", Proceedings of UAI, pp. 222–228, ftp://www.cs.ucla.edu/tech-report/198_-reports/870031.pdf .
  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 
  4. Simion, Rodica (1991), "Trees with 1-factors and oriented trees", Discrete Mathematics 88 (1): 93–104, 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, 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, http://portal.acm.org/citation.cfm?id=338659 .