Teoria dos Grafos
Nesta unidade, estudamos os conceitos fundamentais da Teoria dos Grafos, suas representações e aplicações práticas em redes, algoritmos de busca e árvores de decisão.
Conceitos Iniciais e Definição
Um grafo é uma estrutura composta por um conjunto de vértices (ou nós) conectados por arestas. Representado por (N, A, g), onde N são os vértices, A as arestas, e g a função que associa as arestas aos vértices.
- Exemplo: mapa do metrô de SP, conexões entre aeroportos.
- Aplicação histórica: problema das pontes de Königsberg.
Elementos de um Grafo
Os grafos podem conter vértices adjacentes, laços (quando uma aresta conecta um vértice a ele mesmo), arestas paralelas (mesmos extremos), e vértices isolados.
- Grafo simples: sem laços nem arestas paralelas.
- Grau do vértice: número de arestas conectadas ao vértice.
- Exemplo: Vértice 2 com grau 5, vértice 5 isolado (grau 0).
Caminhos, Ciclos e Grafos Direcionados
Um caminho é uma sequência de vértices e arestas. Um ciclo é um caminho fechado. Quando a ordem das conexões importa, temos grafos direcionados (ou dígrafos).
- Caminho: 1 → 2 → 3 → 4
- Ciclo: 1 → 2 → 3 → 1
- Direcionado: ordem das conexões faz diferença
Representação Computacional
Os grafos podem ser representados por meio de matrizes de adjacência, onde linhas e colunas representam vértices e os valores indicam a quantidade ou direção de arestas.
- Matriz não-direcionada: simétrica
- Matriz direcionada: usa 0 ou 1 (booleana), entrada e saída são diferenciadas
- Vértice isolado: linha e coluna nulas
Árvores e Florestas
Uma árvore é um grafo acíclico e conexo com uma raiz e ramos. Árvores não enraizadas não têm raiz definida. Florestas são grafos formados por várias árvores desconexas.
- Componentes: raiz, galhos, folhas
- Altura da árvore: caminho mais longo da raiz até uma folha
Árvores de Decisão e Algoritmos de Busca
Árvores de decisão representam escolhas e seus resultados. Vértices internos são ações, arestas são respostas, folhas são os resultados finais. Foram estudados dois algoritmos principais:
- Busca Sequencial: percorre todos os elementos até encontrar o valor (ou não encontrar)
- Busca Binária: eficiente para listas ordenadas, divide o problema pela metade a cada etapa
Árvores Binárias de Busca e Árvores Balanceadas
A estrutura da árvore influencia a eficiência da busca. Árvores binárias de busca organizam os dados em forma ordenada. Árvores balanceadas são obtidas reorganizando os elementos com base na mediana, garantindo menor profundidade.
- Balanceamento: melhora o desempenho de algoritmos de busca
- Exemplo prático: sequência de inserção impacta o formato da árvore