Tópicos Eduardo (1)

Conjuntos de pontos ou nodos
chamados vérices

Conectados por linhas chamadas
de arestas ou arcos, que podem
ou não ter direção.

Se todas as arestas apontam
uma direção temos um
Grafo Dirigido

Grafo não dirigido é aquele que
nehuma de suas arestas aponta
para nenhuma direção

Misto é o grafo que tem tanto
arestas que não apontam p/
nenhuma direção como outras
que apontam.

Definições

Nº de arestas ligadas a
um Véricie

Grau de entrada:
Número de setas q chegam
a um vértice

Grau de saida:
Nº de setas que saem de um
vértice

Fonte:
Todo vértice cujo grau de
entrada é zero.

Sumidouro:
Todo vértice cujo grau de
saida é zero.

Todo nodo tem, no
máximo 2 filhos

Imprópria

Tem algum nodo com
somente 1 filho

Própria

Todo nodo interno tem
exatamente 2 filhos

Camin. Interfixado

Vista-se da esquerda
para a direita

Inicia no nodo interno
Mais a esquerda

Visite seu filho a esquerda

Visite o Pai

Visite o filho
à direita

Reinicie no próximo nodo

Camin. Euler

Inicie pela raiz e va descendo
pela "parede" em direção ao
filho mais a esquerda que deve
ser considerado o 1º

Apos considerar o filho
mais a esquerda, pegue
o proximo no caminho de
Volta (Subindo)

Após subir um nó, continue
descendo p/ considerar o
proximo ramo

Continue neste "zig-zag"

Tipo abstrato de dados

Armazena dados de
forma hierárquica

Raiz = Elemento do topo

Nodo Externo ou Folha =
Não tem filhos

Nodo Interno = Tem 1
ou mais filhos

Um nodo filho é ancestral
tanto de seu pai (direto)
como de seu avô.

A profundidade de um nodo
É o nº de seus ancestrais,
excluindo o próprio nodo.

A profundidade da raiz = 0

Altura de um nodo

Comprimento do caminho
mais longo dele até um
nó folha

A altura de uma árvore =
Altura do nodo raiz

Percurso préfixado

Os nodos são visitados
Antes de seus descendentes

Incio pela raiz

Percurso pós fixado

Os nodos são visitados
após seus descendentes

Inicios pelo nó externo
(folha) mais a esquerda