Este post é sobre a piada das árvores em computação crescerem de cima para baixo...
Relaciona-se aos temas "tipos abstratos de dados", "arrays" e "matrizes" do conteúdo de ACH2001. O conteúdo deste post será melhorado aos poucos.
Grafos são trincas G=(V,A,f) onde V é um conjunto de vértices ou nós (são os pontos da figura), A é um conjunto de arcos, ou arestas (são as linhas das figuras) cada extremidade da aresta incide em um único vértice, então arestas ligam dois vértices. f é uma função que informa como essa ligação é feita.
Passeio em um grafo é uma sequencia alternante de vértices e arestas iniciada e terminada em vértices.
Caminho em um grafo é uma sequencia alternante de vértices e arestas iniciada e terminada em vértices Sem repetição.
Circuito em um grafo é um caminho que inicia e termina no mesmo vértice.
Árvores são grafos acíclicos.
Qualquer vértice de uma árvore pode ser raiz (imagine que o grafo é um conjunto de bolas e que as arestas são fios ligando as bolas. Escolha qualquer bola, segure e levante-a - as outras sobem puxadas pelas arestas, no formato de árvore com raiz.
O que informa a necessidade de escolher um vértice como raiz e qual é ele é o uso que faremos da árvore.
Nenhum comentário:
Postar um comentário