Árbore (teoría de grafos)

árbore binaria orientada

árbore non orientada (un xeito de velo pode ser coa raíz no vértice 6)

Na teoría de grafos, unha árbore é un grafo non orientado no que dous vértices calquera están conectados por exactamente un camiño, ou equivalentemente un grafo acíclico non orientado. Un bosque é un grafo non orientado no que dous vértices calquera están conectados por como máximo un camiño, ou equivalentemente un grafo acíclico non orientado, ou equivalentemente unha unión disxunta de árbores.

Os distintos tipos de estruturas de datos denominadas árbores en informática teñen grafos subxacentes que son árbores na teoría de grafos, aínda que esas estruturas de datos son xeralmente árbores con raíz.

O termo árbore foi acuñado en 1857 polo matemático británico Arthur Cayley.

Definicións

Árbore

Unha árbore é un grafo non orientado G que cumpre algunha das seguintes condicións equivalentes:

• G é conexo e acíclico (non contén ciclos).
• G é acíclico, e fórmase un ciclo simple se se lle engade calquera aresta a G.
• G é conexo, mais deixaría de ser conexo se se saca claquera aresta de G.
• G é conexo e a maiores o grafo completo K₃ non é un menor de G.
• Calquera dous vértices de G poden ser comunicados por un camiño simple.

Se G ten un número finito de vértices, digamos n deles, entón as afirmacións anteriores tamén son equivalentes a calquera das seguintes condicións:

• G é conexo e ten n − 1 vértices.
• G é conexo, e todo subgrafo de G inclúe polo menos un vértice con cero ou máis arestas incidentes.
• G non ten ciclos simples e ten n − 1 arestas.

Un vértice interno é un vértice de grao polo menos 2. Do mesmo xeito, un vértice externo (vértice terminal ou folla) é un vértice de grao 1. Un vértice de rama nunha árbore é un vértice de grao polo menos 3.

Unha árbore irredutíbel é unha árbore na que non hai un vértice de grao 2 (enumerado na secuencia (secuencia A000014 na OEIS).

Bosque

Un bosque é un grafo acíclico non orientado ou equivalentemente unha unión disxunta de árbores.

Poliárbore

Unha poliárbore (árbore orientada ou rede conectada individualmente ) é un grafo acíclico orientado (DAG) cuxo grafo non orientado subxacente é unha árbore.

Árbore con raíz

Unha árbore con raíz é unha árbore na que un vértice desígnase como raíz. As arestas dunha árbore con raíz poden ter unha orientación natural, ben apartándose da ráiz ou cara á raíz. Así a estrutura convértese nunha árbore con raíz orientada.

Cando unha árbore con raíz orientada ten unha orientación apartándose da raíz, chámase arborescencia ou árbore externa; cando ten unha orientación cara á raíz, chámase anti-arborescencia ou árbore interna.

A orde nunha árbore é a ordenación parcial dos vértices da árbore con u < v se e só se o camiño único desde a raíz ata v pasa por u.

Unha árbore con raíz T que é un subgrafo dalgún grafo G é unha árbore normal se os extremos de cada camiño T en G son comparábeis nesta orde de árbores (Diestel 2005, p. 15) .

As árbores con raíz, moitas veces cunha estrutura adicional como unha ordenación dos veciños en cada vértice, son unha estrutura de datos clave en informática; ver estrutura de datos da árbore.

Unha árbore etiquetada é unha árbore na que cada vértice recibe unha etiqueta única. Os vértices dunha árbore etiquetada en n vértices (para enteiros non negativos n ) reciben normalmente as etiquetas 1, 2, …, n . Unha árbore recursiva é unha árbore con raíz etiquetada onde as etiquetas dos vértices respectan a orde da árbore (é dicir, se u < v para dous vértices u e v, entón a etiqueta de u é menor que a etiqueta de v).

Nunha árbore con raíz, o pai dun vértice v é o vértice ligado a v no camiño ata a raíz; cada vértice ten un pai único, agás a raíz que non ten pai ningún. Un fillo dun vértice v é un vértice do que v é o pai.

Un ascendente dun vértice v é calquera vértice que sexa o pai de v ou que sexa (recursivamente) un ascendente dun pai de v. Un descendente dun vértice v é calquera vértice que sexa fillo de v ou que sexa (recursivamente) un descendente dun fillo de v. Un irmán dun vértice v é calquera outro vértice da árbore que comparte un pai con v. Unha folla é un vértice sen fillos. Un vértice interno é un vértice que non é unha folla.

A altura dun vértice nunha árbore con raíz é a lonxitude do camiño descendente máis longo ata unha folla desde ese vértice. A altura da árbore é a altura da raíz.

A profundidade dun vértice é a lonxitude do camiño ata a súa raíz (camiño raíz). A profundidade dunha árbore é a profundidade máxima de calquera vértice. A profundidade é comunmente necesaria na manipulación das distintas árbores de autoequilibrio, en particular das árbores AVL. A raíz ten profundidade cero, as follas teñen altura cero e unha árbore cun só vértice (polo tanto, raíz e folla) ten profundidade e altura cero. Convencionalmente, unha árbore baleira (unha árbore sen vértices, se están permitidos) ten profundidade e altura -1.

Unha árbore k-aria (para enteiros non negativos k) é unha árbore con raíz na que cada vértice ten como máximo k fillos. As árbores 2-arias denomínanse a miúdo árbores binarias, mentres que as árbores 3-arias ás veces chámanse árbores ternarias.

Árbore ordenada

Unha árbore ordenada (alternativamente, árbore plana ou árbore posicional ) é unha árbore con raíz na que se especifica unha ordenación para os fillos de cada vértice Isto chámase "árbore plana" porque unha ordenación dos fillos equivale a un mergullo da árbore no plano, coa raíz na parte superior e os fillos de cada vértice máis baixo que ese vértice.

Propiedades

• Toda árbore é un grafo bipartito. Un grafo é bipartito se e só se non contén ciclos de lonxitude impar. Dado que unha árbore non contén ciclos, é bipartita.
• Toda árbore con só moitos vértices contábeis é un grafo plano.
• Todo grafo conexo G admite unha árbore de expansión, que é unha árbore que contén todos os vértices de G e cuxas arestas son arestas de G. Por exemplo árbores busca en profundidade e árbores de busca en anchura.
• Todo grafo conex cun número de vértices numerábel ten unha árbore de Trémaux. Porén, algúns grafos de orde non numerábel non teñen tal árbore.
• Toda árbore finita con n vértices, con n > 1, ten polo menos dous vértices terminais (follas). Este número mínimo de follas é característico dos grafos de camiño; o número máximo, n − 1, só se consegue mediante os grafos de estrela. O número de follas é polo menos o máximo grao de vértice.
• Para tres vértices calquera dunha árbore, os tres camiños entre eles teñen exactamente un vértice en común.
• Toda árbore ten un centro formado por un ou dous vértices adxacentes. O centro é o vértice medio ou os dous vértices do medio en cada camiño máis longo.
• Os cliques máximos dunha árbore son precisamente as súas arestas, o que implica que a clase de árbores ten poucos cliques.

Tipos de árbores

• Un grafo de camiño (ou grafo linear) consta de n vértices dispostos nunha liña, de xeito que os vértices i e i + 1 están ligados por unha aresta para i = 1, …, n – 1.
• Unha árbore en forma de estrela consiste nun vértice central chamado raíz e varios grafos de camiño unidos a el. Máis formalmente, unha árbore é de estrela se ten exactamente un vértice de grao maior que 2.
• Unha árbore de estrela é unha árbore que consta dun único vértice interno (e n – 1 follas).
• Unha árbore de eiruga é unha árbore na que todos os vértices están dentro da distancia 1 dun subgrafo do camiño central.
• Unha árbore de lagosta é unha árbore na que todos os vértices están dentro da distancia 2 dun subgrafo do camiño central.
• Unha árbore regular de grao d é a árbore infinita con d arestas en cada vértice. Estas xorden como os grafos de Cayley de grupos libres e na teoría dos edificios de Tits. En mecánica estatística coñécense como retículas de Bethe.

Véxase tamén

Bibliografía

• Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability. 
• Dasgupta, Sanjoy (1999). "Learning polytrees". Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Stockholm, Sweden, July–August 1999 (PDF). pp. 134–141. .
• Deo, Narsingh (1974). Graph Theory with Applications to Engineering and Computer Science (PDF). Englewood, New Jersey: Prentice-Hall. ISBN 0-13-363473-6. Arquivado dende o orixinal (PDF) o 2019-05-17. 
• Harary, Frank; Prins, Geert (1959). The number of homeomorphically irreducible trees, and other species. Acta Mathematica (en inglés) 101. pp. 141–162. ISSN 0001-5962. doi:10.1007/BF02559543. 
• Harary, Frank; Sumner, David (1980). The dichromatic number of an oriented tree. Journal of Combinatorics, Information & System Sciences 5. pp. 184–187. MR 603363. .
• Kim, Jin H.; Pearl, Judea (1983). "A computational model for causal and diagnostic reasoning in inference engines". Proc. 8th International Joint Conference on Artificial Intelligence (IJCAI 1983), Karlsruhe, Germany, August 1983 (PDF). pp. 190–193. .
• Li, Gang (1996). "Generation of Rooted Trees and Free Trees". M.S. Thesis, Dept. of Computer Science, University of Victoria, BC, Canada (PDF). p. 9. .
• Simion, Rodica (1991). Trees with 1-factors and oriented trees. Discrete Mathematics 88. pp. 93–104. MR 1099270. doi:10.1016/0012-365X(91)90061-6. .

Outros artigos

• Árbore de decisión
• Pescuda binaria
• Árbore bipartita

Ligazóns externas

• Introduçao á teoría de grafos