Centro
O centro do grafo G é o subconjunto de vértices de excentricidade mínima.
Ex: no exemplo acima, centro={c,d,e}

Lema:
Seja T uma árvore com pelo menos 3 vértices. Seja T' a árvore obtida pela exclusão das folhas de T. Então T e T' possuem o mesmo centro.

Prova:
Observe inicialmente que se um vértice f de T é uma folha, então f não pertence ao centro de T', isso porque o vértice g adjacente a f possui necessariamente excentricidade uma unidade menor do que a de f.
Seja agora um vértice v interior de T. O vértice w cuja distância a v é máxima, é necessariamente uma folha.
Logo, a exclusão de todas as folhas de T faz decrescer de uma unidade a excentricidade de cada um de seus vértices interiores. Isso completa a prova.

Teorema:
O centro de uma árvore possui um ou dois vértices.

Prova:
Se T possui até dois vértices, o teorema é trivial. Caso contrário, aplicar repetidamente o lema anterior.

Algoritmo: Determinação do centro de uma árvore

Dados: árvore T(V,E)
Enquanto |V|>2 executar: Excluir as folhas da árvore

Subgrafo Gerador
Ou subgrafo de espalhamento de um grafo G1(V1,E1) é um subgrafo G2(V2,E2) de G1 tal que V1=V2. Quando o subgrafo gerador é uma árvore, ele recebe o nome de árvore geradora (ou de espalhamento).

(b) e (c) são subgrafos geradores de (a)
(c) é subgrafo gerador de (a) e (b)

Todo grafo conexo G possui árvore geradora

Processo para obtenção de uma árvore geradora
Considere toda aresta e de G. Se G-e for conexo, remova e. Quando todas as arestas que permanecerem tiverem sido consideradas, o grafo resultante é uma árvore geradora de G.

Raiz
Uma árvore T(V,E) é denominada enraizada quando um vértice é escolhido como especial. Esse vértice é chamado raiz.
Uma árvore não enraizada é chamada livre.

Sejam v e w dois vértices de uma árvore T enraizada de raiz r. Suponha que v pertença ao caminho de r a w em T. Então v é ancestral de w, sendo w descendente de v.

Além disso, se v é diferente de w, v é ancestral próprio de w, e este descendente próprio de v. Se (v,w) é uma aresta de T, então v é pai de w, sendo w filhos de v.

Dois vértices que possuem o mesmo pai são chamados irmãos.
A raiz de uma árvore não possui pai, e todo vértice v diferente de r, possui um único pai.
Uma folha é um vértice que não possui filhos.

Nível de um vértice
Denomina-se nível de um vértice v (nível v) ao valor do máximo caminho da raiz a v.
Para dois vértices irmãos, nível(v)=nível(r)

Altura de uma árvore
É o valor máximo de nível(r) para todo vértice v de T.

ancestrais de j={j,e,c}           descendentes de j={j,i,k}
descendentes próprios de j={i,k}  pai de j=e
filhos de j={i,k}                 nível de j=2
altura da árvore =3

Subárvore
Seja T(V,E) uma árvore enraizada e v pertencente a V.
Uma subárvore Tv de T é uma árvore enraizada cuja raiz é v, definida pelo subgrafo induzido pelos descendentes de v.
A subárvore de raiz v é única para cada v pertencente a V.

Árvore enraizada ordenada
Na definição de árvore enraizada, é irrelevante a ordem em que os filhos de cada vértice v são considerados.
Caso a ordenação seja relevante a árvore é denominada enraizada ordenada.
Assim, para cada vértice v pode-se identificar o primeiro filho de v (o mais a esquerda), o segundo filho (o segundo mais a esquerda), etc.

Note: Se duas árvores são isomórfas, elas não o serão necessariamente como árvores enraizadas ordenadas, para tanto o isomorfismo deve preservar também a ordenação.

As árvores acima são isomórfas se consideradas enraizadas e não isomórfas se consideradas como enraizadas ordenadas.

Componentes de um Grafo

Árvore m-ária