Grafos

Definição Básica:

Um grafo é formado por conjunto de vértices (nó) e arestas.
Nos computadores um Grafo é normalmente representado por sua matriz de adjacências.

Grafo Trivial: Possui apenas um vértice(nó) e não contem arestas.

Grafos direcionados: Grafos com arestas direcionada.

Sumidouro: Vértice que recebe as arestas

Fonte: Vértice que sai as arestas

Grafos não-direcionados: Grafos com arestas sem direção.

Multi-Grafo: Grafos com vértices com mais de uma arestas.

Laços: Grafos com aresta de entrada e saída no mesmo vértice.

Matriz de adjacências:

|  | v1 | v2 | v3
v1 |  | 0 | 1 | 1
v2 |  | 1 | 0 | 0
v3 |  | 1 | 0 | 0

Caminho: Sequência de vértices

Diâmetro: Maior caminho do grafo.

Ciclo: Sequência de vértices v1...vj, tal que v1= vj.

Acíclico: Grafos que não possuem ciclo

Comprimento: Número de caminho do grafo.

Grau: Números de arestas do vértice.

Grau máximo: Vértice com maior grau.

Triângulos: Grafo com ciclo de tamanho 3.

Completo: Todos os vértices possuem todas as arestas possíveis.

Regular: Todos os vértices possuem o mesmo grau.

Ponderado: As arestas possuem peso.

Subgrafo: Grafo menor pertencente a um grafo maior.

Isomorfismo: Grafos com o mesmo número de arestas e número de grau.

Bipartido: Não possui ciclo impar.

Conexo: Existe um caminho entre todos os pares de vértices.

Desconexo: Grafo não conexo/não possui caminho entre todos os pares de vértices.

Biconexo: Para qualquer dois vértices existe dois caminhos distintos entre eles.

Articulação: Vértices que quando removido desconecta o grafo.

Ponte: Aresta que quanto removida desconecta o grafo.(em uma árvore todas as arestas são pontes).

Euleriano: Passa por cada arestas somente uma vez. Um grafo é euleriano se, e somente se possuir todos os vértices com grau par.

Hamiltoniano: Passa por cada vértice uma única vez. Não possui articulação.

Coloração: Vértices adjacentes não podem possuir a mesma cor. Em um grafo bipartido é possível colorir com duas cores.

Planaridade: Podem ser desenhados em um plano e uma esfera sem cruzamento de arestas.

Busca:

Largura: Busca em fila

Profundidade: Busca em pilha

Algoritmo de Dijkstra

Algoritmo Guloso

Árvores

Árvores são estruturas de dados extremamente úteis em muitas aplicações computacionais, principalmente por:

Suportar relações hierárquicas.

Permitir diversos métodos de busca.

Ter seus algoritmos de manipulação facilmente construídos de forma recursiva

Definição Básica:

Grafo conexo
Acíclico
V = E + 1
Uma árvore é formada por um conjunto finito T de elementos denominados vértices ou nós interligados por arestas
Se T = 0, a árvore é vazia
Se T >= 1, temos um nó especial chamado raiz da árvore, representado pela notação r

Se n é um nó da árvore T, então Tn indica uma subárvore de T com raiz no nó n.

O número de filhos de um nó é chamado de grau de saída deste nó.

Operações em árvore binária:

Busca Recursiva

Se a árvore está vazia, o valor procurado não pode existir na árvore

Caso contrário, se o valor é igual a raiz, a busca foi bem sucedida.

Se o valor é menor do que a raiz, a busca segue pela sub-árvore esquerda

Similarmente, se o valor é maior do que a raiz, a busca segue pela subárvore da direita

Inserção:

A raiz é examinada

Introduz-se um nó novo na subárvore da esquerda se o valor novo for menor do que a raiz

Ou na subárvore da direita se o valor novo for maior do que a raiz

Percorrer árvore binária:

3 métodos para percorrer árvores binárias

Pré-ordem: raiz, esquerda, direita

Ordem simetrica/Em ordem: esquerda, raiz, direita

Pós-ordem: esquerda, direita, raiz

Árvores Binarias Balanceadas – AVL

Cada nó de uma árvore balanceada tem balanceamento igual a -1, 0 ou 1
Vantagem em balancear uma árvore: a busca por um elemento se torna na média mais rápido