Árvore (grafo)
Origem: Wikipédia, a enciclopédia livre.
Em teoria dos grafos, uma árvore é um grafo conexo (existe caminho entre quaisquer dois de seus vértices) e acíclico (não possui ciclos). Caso o grafo seja acíclico mas não conexo, ele é dito uma floresta. Uma floresta também é definida como uma união disjunta de árvores.
[editar] Propriedades
Em uma árvore, há exatamente um caminho entre dois vértices quaisquer. Já em uma floresta, há no máximo um caminho entre dois vértices, devido à não-conectividade.
Toda árvore é um grafo bipartido e planar.
Todo grafo conexo possui pelo menos uma árvore de extensão associada, composta de todos os seus vértices e algumas de suas arestas.