TreeEdit

Uma árvore é um não-gráfico de G que satisfaz qualquer das seguintes condições equivalentes:

• G é ligado e acíclicas (não contém ciclos).
• G é acíclico, e um ciclo simples é formado se qualquer borda é adicionado ao G.
• G é ligado, mas viria a ser desconectado se qualquer aresta é removida do G.
• G é ligado e o 3-vértice gráfico completo K3 não é um menor de G.
• Quaisquer dois vértices em G podem ser ligados por um único caminho simples.

Se G tem finitamente muitos vértices, digamos n deles, então as afirmações acima são também equivalentes a qualquer uma das seguintes condições:

• G está conectado e tem n − 1 arestas.
• G é conectado, e cada subgrafo de G inclui pelo menos um vértice com bordas zero ou um incidente. (Isto é, G é conectado e 1-degenerado.)
• G não tem ciclos simples e tem arestas n – 1.

Como em outros lugares na teoria dos grafos, o grafo de ordem-zero (grafo sem vértices) não é geralmente considerado como uma árvore.: enquanto ele é vacuously connected as a graph( any two vertices can be connected by a path), it is not 0-connected (or even (-1)-connected) in algebraic topology, unlike non-empty trees, and violates the “one more vertex than edges” relation. Pode, no entanto, ser considerada uma floresta constituída por zero árvores.

um vértice interno (ou vértice interno ou vértice de ramo) é um vértice de grau pelo menos 2. Similarmente, um vértice externo (ou vértice externo, vértice terminal ou folha) é um vértice de grau 1.

uma árvore irredutível (ou árvore reduzida em série) é uma árvore na qual não há vértice do grau 2 (enumerado na sequência A000014 no OEIS).

ForestEdit

a forest é um grafo não direcionado no qual quaisquer dois vértices são conectados por no máximo um caminho. Equivalentemente, uma floresta é um grafo acíclico não direcionado, todos cujos componentes conectados são árvores; em outras palavras, o grafo consiste de uma união disjunta de árvores. Como casos especiais, o grafo de ordem-zero (uma floresta constituída por árvores zero), uma única árvore, e um grafo sem orlas, são exemplos de florestas.Uma vez que para cada árvore V − e = 1, podemos facilmente contar o número de árvores que estão dentro de uma floresta subtraindo a diferença entre vértices totais e arestas totais. TV-TE = número de árvores em uma floresta.

PolytreeEdit

uma polytree (ou árvore orientada ou rede conectada individualmente) é um grafo acíclico direcionado (DAG) cujo grafo não direcionado subjacente é uma árvore. Em outras palavras, se substituirmos suas arestas direcionadas por arestas não direcionadas, obtemos um grafo não direcionado que é conectado e acíclico.

alguns autores restringem a frase “árvore dirigida” ao caso em que as arestas são todas direcionadas para um vértice particular, ou todas direcionadas para longe de um vértice particular (veja arborescence).

Poliforestedit

a poliforest (or directed forest or oriented forest or oriented forest) é um grafo acíclico direcionado cujo grafo subjacente não direcionado é uma floresta. Em outras palavras, se substituirmos suas arestas direcionadas por arestas não direcionadas, obtemos um grafo não direcionado que é acíclico.

alguns autores restringem a frase “Floresta dirigida” ao caso em que as arestas de cada componente conectado são todas direcionadas para um vértice particular, ou todas direcionadas para longe de um vértice particular (veja ramificação).

árvore enraizada

uma árvore enraizada é uma árvore na qual um vértice foi designado a raiz. As bordas de uma árvore enraizada podem ser atribuídas a uma orientação natural, seja para longe ou para a raiz, caso em que a estrutura se torna uma árvore enraizada direcionada. Quando uma árvore enraizada dirigida tem uma orientação para longe da raiz, ela é chamada de arborescência ou Out-tree; quando ela tem uma orientação para a raiz, ela é chamada de anti-arborescência ou in-tree. A árvore de ordem é a ordem parcial sobre os vértices de uma árvore com u < v se, e somente se, o único caminho da raiz para v passa por u. Uma árvore T, que é um subgraph de alguns grafo G é normal árvore se as extremidades de cada T-caminho em G são comparáveis com esta árvore-ordem (Diestel, 2005, p. 15). Árvores enraizadas, muitas vezes com estrutura adicional, como a ordenação dos vizinhos em cada vértice, são uma estrutura de dados chave na ciência da computação; ver estrutura de dados de árvore.

In a context where trees are supposed to have a root, a tree without any designed root is called a free tree.

uma árvore marcada é uma árvore na qual cada vértice recebe um rótulo único. Os vértices de uma árvore rotulada em n vértices são normalmente dadas as etiquetas 1, 2,…, n. uma árvore recursiva é uma árvore enraizada rotulada onde as etiquetas de vértices respeitam a ordem da árvore (i.e., if u < v for two vertices u and v, then the label of u is smaller than the label of v).

numa árvore enraizada, o progenitor de um vértice v é o vértice ligado a v no caminho para a raiz; cada vértice tem um progenitor único, excepto a raiz que não tem nenhum Progenitor. Um filho de um vértice v é um vértice do qual v é o pai. Um ascendente de um vértice v é qualquer vértice que é o pai de v ou é (recursivamente) o ascendente do pai de v. Um descendente de um vértice v é qualquer vértice que é o filho de v ou (recursivamente) a descendente de qualquer dos filhos de v. Um irmão para um vértice v é qualquer vértice na árvore que tem o mesmo pai que v. Uma folha é um vértice sem filhos. Um vértice interno é um vértice que não é uma folha.

a altura de um vértice em uma árvore enraizada é o comprimento do caminho mais longo para baixo para uma folha a partir desse vértice. A altura da árvore é a altura da raiz. A profundidade de um vértice é o comprimento do caminho para sua raiz (caminho raiz). Isto é comumente necessário na manipulação das várias árvores auto-equilibradas, árvores AVL em particular. A raiz tem profundidade zero, as folhas têm altura zero, e uma árvore com apenas um único vértice (daí uma raiz e folha) tem profundidade e altura zero. Convencionalmente, uma árvore vazia (uma árvore sem vértices, se tal for permitido) tem profundidade e altura -1.

uma árvore K-ary é uma árvore enraizada na qual cada vértice tem, no máximo, K crianças. As árvores 2-ary são muitas vezes chamadas de árvores binárias, enquanto as árvores 3-ary são algumas vezes chamadas de árvores ternárias.

treeEdit ordenado

uma árvore ordenada (ou árvore plana) é uma árvore enraizada na qual uma ordem é especificada para os filhos de cada vértice. Isto é chamado de “árvore plana” porque uma ordenação das crianças é equivalente a uma incorporação da árvore no plano, com a raiz no topo e os filhos de cada vértice abaixo desse vértice. Dada uma incorporação de uma árvore enraizada no plano, se se fixa uma direção de crianças, digamos esquerda para a direita, então uma incorporação dá uma ordem das crianças. Inversamente, dada uma árvore ordenada, e convencionalmente desenhando a raiz no topo, então os vértices-filhos em uma árvore ordenada podem ser puxados da esquerda para a direita, produzindo uma incorporação planar essencialmente única.