Durante nossa aula de hoje, mergulhamos no estudo dos grafos, uma das estruturas de dados mais versáteis e ubíquas na ciência da computação. Vimos como os grafos permitem modelar relações entre entidades — desde conexões em redes sociais até topologias de redes de computadores. O objetivo desta aula foi estabelecer as bases: definição formal, representação em memória, propriedades fundamentais e classificação.

1. O que é um grafo?

Um grafo é definido como um par ordenado G = (V, E), onde V é um conjunto de vértices (ou nós) e E é um conjunto de arestas (ou arcos). Cada aresta conecta dois vértices. Se as arestas possuem direção, chamamos de grafo direcionado; caso contrário, grafo não direcionado. Grafos simples não possuem arestas paralelas ou laços (arestas que ligam um vértice a ele mesmo).

Exemplos cotidianos incluem: mapa de ruas de uma cidade (vértices são interseções, arestas são ruas), a World Wide Web (páginas são vértices, hyperlinks são arestas direcionadas) e moléculas (átomos são vértices, ligações químicas são arestas).

2. Representação de grafos

Existem duas maneiras principais de representar grafos em algoritmos:

Matriz de Adjacência

Uma matriz binária (ou com pesos) de tamanho |V| × |V|. A entrada (i, j) indica se existe uma aresta entre o vértice i e o vértice j. Vantagens: consulta O(1) para verificar existência de aresta. Desvantagem: ocupa O(|V|²) de memória, ineficiente para grafos grandes e esparsos.

Lista de Adjacência

Para cada vértice, armazenamos uma lista de vértices vizinhos (ou arestas). O espaço total é O(|V| + |E|). Vantagens: mais econômica para grafos esparsos, fácil de iterar pelos vizinhos. Desvantagem: consulta de existência de aresta pode levar O(grau) no pior caso.

A escolha entre as duas depende da densidade do grafo. Em código Python, por exemplo:

# Matriz de adjacência
n = 5
adj_mat = [[0]*n for _ in range(n)]
adj_mat[0][1] = 1  # aresta 0-1

# Lista de adjacência
adj_list = [[] for _ in range(n)]
adj_list[0].append(1)  # aresta 0-1

3. Propriedades básicas

Algumas propriedades importantes que estudamos:

  • Grau de um vértice: número de arestas que incidem sobre ele. Em grafos direcionados, diferenciamos grau de entrada (indegree) e grau de saída (outdegree).
  • Caminho: sequência de vértices onde cada par consecutivo é adjacente. O comprimento de um caminho é o número de arestas.
  • Ciclo: caminho fechado (primeiro e último vértice igual) que não repete arestas (ciclo simples). Um grafo acíclico não possui ciclos.
  • Conexidade: um grafo não direcionado é conexo se existe um caminho entre qualquer par de vértices. As componentes conexas são as partes máximas conexas do grafo.
  • Subgrafo: grafo formado por subconjuntos dos vértices e arestas do original.
  • Grafo completo Kn: possui arestas entre todos os pares de vértices.

4. Tipos de grafos

Podemos classificar grafos de acordo com diversas características:

  • Quanto à direção: direcionados (dígrafos) vs. não direcionados.
  • Quanto à existência de pesos: ponderados (arestas com custo) vs. não ponderados.
  • Quanto à complexidade: simples (sem laços ou arestas paralelas) vs. multigrafos (permitem arestas paralelas).
  • Quanto à estrutura: completos, bipartidos (vértices divididos em dois conjuntos com arestas apenas entre eles), regulares (todos os vértices têm o mesmo grau), etc.

5. Árvores como casos especiais de grafos

Uma árvore é um grafo não direcionado, conexo e acíclico. Propriedades fundamentais:

  • Número de arestas = número de vértices − 1.
  • Entre quaisquer dois vértices existe um único caminho.
  • Adicionar qualquer aresta cria um ciclo.
  • Remover qualquer aresta desconecta o grafo.

Árvores são a base de estruturas de dados como árvores binárias de busca, heaps e árvores de expressão.

6. Aplicações de grafos

Grafos são usados em inúmeras aplicações práticas:

  • Redes de computadores: roteamento (OSPF, RIP) usa algoritmos de menor caminho.
  • Internet: PageRank modela a web como um grafo direcionado.
  • Redes sociais: recomendação de amigos, detecção de comunidades.
  • Mapas e GPS: cálculo de rotas (algoritmo de Dijkstra, A*).
  • Dependências de software: gerenciadores de pacotes resolvem dependências usando grafos acíclicos direcionados (DAG).
  • Inteligência artificial: grafos de estado em planejamento, redes neurais (grafos computacionais).
  • Biologia: redes de interação proteína-proteína.

Pontos principais

  • Grafos modelam relações entre entidades.
  • Duas representações principais: matriz de adjacência (consulta O(1), memória O(n²)) e lista de adjacência (memória O(n+m)).
  • Propriedades fundamentais: grau, caminho, ciclo, conexidade.
  • Classificação: direcionado, não direcionado, ponderado, simples, completo, bipartido.
  • Árvores são grafos conexos e acíclicos.
  • Inúmeras aplicações em computação e outras áreas.

Perguntas frequentes

Qual é a diferença entre um grafo direcionado e um não direcionado?

Em um grafo não direcionado, as arestas são pares não ordenados — a relação é simétrica. Em um direcionado, cada aresta tem uma direção, indo de um vértice origem para um destino, permitindo relações assimétricas.

Como decidir entre matriz de adjacência e lista de adjacência?

Para grafos densos (número de arestas próximo de |V|²), a matriz é mais simples e oferece consulta O(1). Para a maioria dos grafos reais, que são esparsos, a lista de adjacência é mais eficiente em memória e iteração.

O que é um grafo bipartido?

É um grafo cujos vértices podem ser divididos em dois conjuntos disjuntos U e V, de forma que toda aresta conecta um vértice de U a um vértice de V (não há arestas dentro de U ou V). São úteis para modelar problemas de emparelhamento (matching) e alocação de recursos.

Nota: estas são minhas anotações pessoais da aula. Podem conter imprecisões. Consulte os textos oficiais para aprofundamento.