Árvore (grafo)

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Disambig grey.svg Nota: Para outros significados de Árvore, veja Árvore (desambiguação).
Uma árvore com 5 arestas e 6 vértices.

Na teoria dos grafos, uma árvore é um grafo conexo (existe caminho entre quaisquer dois de seus vértices) e acíclico (não possui ciclos)[1] [2] . 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.

Toda árvore é um grafo, mas nem todo grafo é uma árvore. 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.

Propriedades[editar | editar código-fonte]

Seja G um grafo. G é uma árvore se satisfaz as seguintes condições:

  • G é conexo e 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.
  • G é acíclico, e um simples ciclo é formado se qualquer aresta for adicionada a G.
  • G é conexo, e deixará de ser conexo se qualquer aresta for removida de G.
  • G é conexo, acíclico e tem n − 1 arestas.

Definições[editar | editar código-fonte]

  • Uma árvore é denominada enraizada se um vértice é escolhido como especial. Esse vértice é chamado raiz. Uma árvore que não é enraizada é denominada livre.
  • Um grafo G é uma árvore se e somente se existir um único caminho entre cada par de vértices de G[2] .

Referências

  1. BARBOSA, Ruy Madsen (1975). Combinatória e Grafos 2 (São Paulo: Livraria Nobel). p. 196.  Parâmetro desconhecido |volumes= ignorado (|volume=) (Ajuda)
  2. a b SZWARCFITER, Jayme Luiz (1988). Grafos e algoritmos computacionais (Rio de Janeiro: Campus). p. 43-45. ISBN 85-7001-341-8. 
Ícone de esboço Este artigo sobre Informática é um esboço. Você pode ajudar a Wikipédia expandindo-o.
Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.