https://docs.google.com/presentation/d/e/2PACX-1vSdSC2sCa8TH4By7nkPvin8lGQkT3mqeOx59Z1GRRk9-FG2VZEijUN5Jo3tP9fzJA/pubembed?start=false&loop=false&delayms=3000

1. Introdução

A modelagem de problemas em Ciência da Computação frequentemente recorre a grafos e árvores como estruturas abstratas para representar relações entre entidades e hierarquias de dados1. Estas estruturas facilitam a formulação e a aplicação de algoritmos eficientes para buscas, caminhos mínimos, ordenações e outras operações essenciais em diversas áreas.

2. Grafos

2.1 Definição e Elementos

Um grafo $G(V,E)$ é composto por um conjunto de vértices $V$ e um conjunto de arestas $E$ que conectam pares de vértices1. A orientação e o peso das arestas determinam se o grafo é dirigido ou não dirigido e ponderado ou não ponderado.

2.2 Representações Computacionais

Para implementar grafos em programas, as representações mais comuns são:

• Lista de Adjacência: Para cada vértice, armazena uma lista de vértices vizinhos, economizando espaço em grafos esparsos2.
• Matriz de Adjacência: Matriz n×nn \times nn×n onde cada célula indica a presença ou ausência de uma aresta entre dois vértices, ideal para grafos densos3.
• Lista de Incidência: Variante orientada a objetos em que cada vértice guarda objetos que representam arestas, incluindo atributos como peso ou capacidade2.

Exemplo Visual: Lista de Adjacência

Diagrama de um grafo não direcionado com cinco nós e sua correspondência em lista de adjacência.

Diagrama de grafo e lista de adjacência

Exemplo Visual: Matriz de Adjacência

Exemplo de matriz de adjacência para um grafo com cinco vértices, destacando células preenchidas que representam arestas.

Exemplo de matriz de adjacência

2.3 Complexidades e Escolhas