Please enable JavaScript.
Coggle requires JavaScript to display documents.
REPRESENTAÇÃO GRÁFICA, Binary Tree Traversals and Related Properties -…
REPRESENTAÇÃO GRÁFICA
GRÁFICO
Um gráfico é informalmente pensado como uma coleção de pontos no plano chamados "vértices" ou "nós", alguns deles conectados por segmentos de linha chamados "arestas" ou "arcos"
Gráfico ponderado(ou dígrafo ponderado) é um gráfico(ou dígrafo) com números atribuídos às suas arestas. Esses números são chamados pesos ou custos
Os gráficos para algoritmos de computador são geralmente representados em uma das duas formas: a matriz de adjacência e as listas de adjacência
listas de adjacência de um gráfico ou dígrafo é uma coleção de listas encadeadas, uma para cada vértice, que contém todos os vértices adjacentes ao vértice da lista (ou seja, todos os vértices conectados a ela por uma aresta)
Diz-se que um gráfico é conectado se para cada par de seus vértices você e v há um caminho de você para v
Caminho direcionado é uma sequência de vértices na qual cada par consecutivo de vértices é conectado por uma aresta direcionada do vértice listado primeiro para o vértice listado a seguir
-
Árvores Enraizadas
Esta propriedade torna possível selecionar um vértice arbitrário em uma árvore livre e considerá-lo como o raiz do assim chamado árvore enraizada
Outra propriedade muito importante das árvores é o fato de que para cada dois vértices em uma árvore, sempre existe exatamente um caminho simples de um desses vértices para o outro
Uma árvore enraizada é geralmente representada colocando sua raiz no topo (nível 0 da árvore), os vértices adjacentes à raiz abaixo dela (nível 1), os vértices duas arestas além da raiz ainda abaixo (nível 2), e assim por diante.
ÁRVORE(mais precisamente, uma árvore livre) é um gráfico acíclico conectado
Um gráfico que não tem ciclos, mas não está necessariamente conectado, é chamado de floresta: cada um de seus componentes conectados é uma árvore
Árvores Ordenadas
Um árvore ordenada é uma árvore com raiz na qual todos os filhos de cada vértice são ordenados. É conveniente supor que no diagrama de uma árvore, todos os filhos são ordenados da esquerda para a direita
O profundidade de um vértice v é o comprimento do caminho simples da raiz até v. o altura de uma árvore é o comprimento do caminho simples mais longo da raiz até uma folha
Árvore Binária
pode ser definida como uma árvore ordenada em que cada vértice não tem mais do que dois filhos e cada filho é designado como um criança esquerda ou um criança certa de seu pai; uma árvore binária também pode estar vazia
As árvores têm várias propriedades importantes que outros gráficos não têm. Em particular, o número de arestas em uma árvore é sempre um a menos que o número de seus vértices: E = V - 1
-