Poliárvore
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 x ≤ yi ≥ zi, ou x ≥ yi ≤ zi, 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, ..., é
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]- ↑ a b Rebane, George; Pearl, Judea (1987), «The recovery of causal poly-trees from statistical data», Proceedings of UAI (PDF), pp. 222–228.
- ↑ 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.
- ↑ Harary, Frank; Sumner, David (1980), «The dichromatic number of an oriented tree», Journal of Combinatorics, Information & System Sciences, 5 (3): 184–187, MR 603363
- ↑ 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.
- ↑ 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.
- ↑ Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2010-09-17.
- ↑ 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
- ↑ 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.