1.1 O vocabulário mínimo

1.2 As três representações

# Lista de adjacência — o padrão para grafos esparsos
adj = { "A": [("B", 3), ("C", 1)], "B": [("C", 7)], "C": [] }
# espaço O(V+E); vizinhos de um nó em O(grau); "existe aresta A-B?" em O(grau)

# Matriz de adjacência — boa para grafos densos e operações de álgebra linear
#     A  B  C
# A [ 0  3  1 ]   espaço O(V²); "existe aresta?" em O(1); vizinhos em O(V)

# CSR (Compressed Sparse Row) — o formato de bibliotecas de alto desempenho
# dois arrays (indptr, indices [+ data]); cache-friendly, imutável; usado por SciPy, cuGraph, PyG

2.1 Os dois esqueletos

# BFS — fila; visita por "camadas" (distância crescente em nº de arestas)
from collections import deque
def bfs(adj, s):
    dist = {s: 0}; q = deque([s])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

# DFS — pilha/recursão; vai fundo antes de voltar
def dfs(adj, u, seen):
    seen.add(u)
    for v in adj[u]:
        if v not in seen:
            dfs(adj, v, seen)

Ambas: O(V+E) com lista de adjacência. BFS usa fila; DFS usa pilha (ou a de chamadas — cuidado com o limite de recursão em grafos grandes; use pilha explícita).

2.2 O mapa "problema → algoritmo"

3.1 A tabela de decisão

3.2 Dijkstra — o cavalo de batalha

import heapq
def dijkstra(adj, s):                 # adj[u] = [(v, w), ...], w >= 0
    dist = {s: 0}; pq = [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float("inf")): continue   # entrada obsoleta
        for v, w in adj[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

• Por que não aceita peso negativo: Dijkstra "fecha" um nó ao tirá-lo do heap, assumindo que nenhum caminho futuro o melhora — uma aresta negativa quebra essa premissa.
• Reconstruir o caminho: guardar prev[v] = u a cada relaxamento e caminhar de trás para frente.

3.3 A* — Dijkstra com palpite

A* prioriza pela soma f(n) = g(n) + h(n), onde g é o custo real até n e h é uma estimativa do custo de n até o destino. Se h nunca superestima (admissível) — ex.: distância em linha reta num mapa — A* acha o caminho ótimo explorando muito menos nós que Dijkstra. É o algoritmo de rotas de GPS e de pathfinding em jogos.

3.4 Bellman-Ford e Floyd-Warshall

• Bellman-Ford: relaxa todas as arestas V−1 vezes. Se na V-ésima passada ainda dá para relaxar, há ciclo negativo — o que é útil por si só (arbitragem em câmbio: um ciclo de conversões que gera lucro é um ciclo negativo no grafo de −log(taxa)).
• Floyd-Warshall: três loops aninhados; d[i][j] = min(d[i][j], d[i][k] + d[k][j]). Simples, O(V³) — só para grafos pequenos (algumas centenas de nós) quando você quer a matriz completa de distâncias.

4.1 Árvore Geradora Mínima (MST)

Conectar todos os nós com o menor custo total de arestas, sem ciclos. Aplicações: projetar redes (elétrica, fibra, água) com custo mínimo; clustering (remover as arestas mais caras da MST separa grupos); aproximações para o caixeiro viajante.

Kruskal brilha em grafo esparso; Prim, em denso (com heap) ou quando você já tem uma matriz.

4.2 Componentes Fortemente Conexos (SCC) grafo dirigido

Um SCC é um subconjunto máximo onde todo nó alcança todo outro (ida e volta). Contrair cada SCC num super-nó transforma qualquer grafo dirigido num DAG — o que permite ordenação topológica e análise de dependências mesmo com ciclos presentes.

• Tarjan (uma DFS, com low-link) ou Kosaraju (duas DFS, uma no grafo transposto). Ambos O(V+E).
• Usos: achar módulos com dependência circular num codebase; comunidades "de mão dupla" numa rede de citações/menções; resolver 2-SAT (satisfatibilidade) via SCC no grafo de implicações.

4.3 Pontes e pontos de articulação robustez

• Ponte: aresta cuja remoção desconecta o grafo. Ponto de articulação: nó cuja remoção desconecta.
• Achados por uma DFS com discovery time e low (o menor tempo alcançável por back-edges).
• Aplicação direta: single points of failure numa rede (um roteador/enlace cuja queda parte a rede em duas), pontos críticos numa malha logística, gargalos estruturais.

5.1 Fluxo máximo / corte mínimo

Dado um grafo com capacidades nas arestas, uma fonte e um sorvedouro, qual o fluxo máximo que passa da fonte ao sorvedouro? O teorema max-flow / min-cut diz que esse valor é igual à capacidade do menor conjunto de arestas cuja remoção separa fonte e sorvedouro — o que torna "fluxo máximo" também a resposta para "corte mínimo" (segmentação, particionamento, confiabilidade).

• Ford-Fulkerson (achar caminhos aumentantes) / Edmonds-Karp (BFS para o caminho, O(V·E²)) / Dinic (O(V²·E), rápido na prática, o padrão).
• Aplicações: capacidade de uma rede (dados, água, tráfego); segmentação de imagem (graph cut); confiabilidade (quantas falhas a rede aguenta); project selection e outros problemas de otimização que se reduzem a min-cut.

5.2 Emparelhamento bipartido

Dois grupos (trabalhadores × tarefas, candidatos × vagas, alunos × projetos) e arestas de compatibilidade. O emparelhamento máximo é o maior conjunto de pares sem repetir ninguém. Resolve-se como um caso de fluxo máximo (fonte → grupo A → grupo B → sorvedouro, capacidades 1) ou com Hopcroft-Karp (O(E√V)).

• Assignment problem (emparelhamento de custo mínimo, cada aresta com um custo): algoritmo húngaro (O(V³)) ou min-cost max-flow.
• Teorema de Hall: existe emparelhamento perfeito do lado A sse e só se todo subconjunto S de A tem pelo menos |S| vizinhos — critério útil para provar (in)viabilidade.

6.1 Centralidade: "importância" tem várias definições

Betweenness exata é O(V·E) (Brandes) — cara em grafos grandes; usa-se amostragem. PageRank é iterativo (multiplicação matriz-vetor até convergir), escala bem.

6.2 Detecção de comunidades

• Louvain: otimiza modularidade (densidade de arestas dentro dos grupos vs esperado ao acaso) de forma gulosa e hierárquica. Rápido, o padrão de fato.
• Leiden: melhora o Louvain garantindo comunidades bem conectadas (o Louvain às vezes produz grupos internamente desconexos). Prefira Leiden quando disponível.
• Label propagation: cada nó adota o rótulo mais comum entre vizinhos, iterando. Quase linear, mas instável.
• Usos: segmentação de clientes por interação, detecção de bolhas/eco em redes sociais, módulos funcionais em redes biológicas, anéis de fraude.

6.3 Previsão de link

Dado o grafo atual, quais arestas vão aparecer (ou estão faltando)? Base de "pessoas que você talvez conheça", recomendação, completar bases incompletas.

• Heurísticas locais: vizinhos em comum, Jaccard, Adamic-Adar (pondera vizinhos raros), preferential attachment (grau × grau).
• Baseadas em caminho: Katz, rooted PageRank.
• Aprendidas: embeddings de nó (módulo 7) + classificador, ou GNN (módulo 8).
• Avaliação: dividir arestas em treino/teste no tempo, medir AUC / precisão@k. Cuidado com data leakage temporal.

6.4 As ferramentas

import networkx as nx
G = nx.karate_club_graph()
pr   = nx.pagerank(G)
btw  = nx.betweenness_centrality(G)
comm = nx.community.louvain_communities(G, seed=42)

• NetworkX: didático e completo, Python puro — até ~10⁴–10⁵ nós. igraph / graph-tool: C por baixo, ordens de magnitude mais rápido. cuGraph (RAPIDS): GPU.
• Neo4j Graph Data Science (GDS): roda PageRank, Louvain/Leiden, node2vec, previsão de link etc. dentro do banco de grafo, sobre projeções em memória — o caminho de produção quando o grafo já vive no Neo4j.

7.1 A ideia

Um node embedding mapeia cada nó para um vetor de baixa dimensão (64–256) tal que nós estruturalmente próximos no grafo fiquem próximos no espaço vetorial. Com isso, tarefas de grafo viram tarefas tabulares: classificar nós, prever links (distância entre embeddings), agrupar, buscar "nós parecidos".

7.2 Os métodos baseados em passeio aleatório

from node2vec import Node2Vec
emb = Node2Vec(G, dimensions=128, walk_length=30, num_walks=200, p=1, q=1).fit()
vec = emb.wv["42"]                 # vetor do nó 42
emb.wv.most_similar("42")             # nós estruturalmente parecidos

7.3 Graph embeddings (o grafo inteiro) e KG embeddings

• Grafo → vetor (para classificar moléculas, comparar grafos): graph2vec, ou pooling de node embeddings, ou uma GNN com readout (módulo 8).
• Knowledge Graph embeddings (triplas sujeito-relação-objeto): TransE (relação ≈ translação: h + r ≈ t), DistMult, ComplEx, RotatE. Usados para completar o KG (prever triplas faltantes) e para link prediction em bases de conhecimento.

8.1 Message passing: a ideia central

Uma GNN calcula o vetor (embedding) de cada nó agregando os vetores dos vizinhos, camada após camada. Após k camadas, o vetor de um nó resume informação da sua vizinhança de k saltos. Cada camada faz, para todo nó v:

h_v^(k) = UPDATE( h_v^(k-1) ,  AGGREGATE( { h_u^(k-1) : u vizinho de v } ) )

8.2 As três tarefas

• Nível de nó: classificar/regredir nós (conta fraudulenta? categoria do artigo? risco do cliente?).
• Nível de aresta / link prediction: esta aresta existe/vai existir? (recomendação, completar KG, descoberta de fármacos — "esta proteína interage com aquela?").
• Nível de grafo: classificar o grafo inteiro via um readout (pooling) dos nós — propriedade de uma molécula, malícia de um binário representado como grafo de chamadas.

8.3 Armadilhas

• Over-smoothing: com muitas camadas, os embeddings de todos os nós convergem para o mesmo — a informação local se dilui. Na prática, 2–4 camadas. Técnicas: conexões residuais, jumping knowledge, normalização.
• Escala: um grafo com bilhões de arestas não cabe na GPU. Soluções: amostragem de vizinhança (GraphSAGE), amostragem de subgrafos (GraphSAINT, Cluster-GCN), e sistemas distribuídos.
• Grafos heterogêneos (vários tipos de nó/aresta): R-GCN, HGT — pesos por tipo de relação.
• Precisa de features de nó: sem features (só estrutura), use grau/embeddings estruturais como entrada, ou volte para node2vec.
• Baseline honesta: muitas vezes um MLP sobre features + algumas features de grafo (grau, PageRank, nº de triângulos) chega perto de uma GNN com muito menos custo. Sempre compare.

import torch_geometric.nn as gnn
class Net(torch.nn.Module):
    def __init__(self, in_dim, hid, out):
        self.c1 = gnn.SAGEConv(in_dim, hid)
        self.c2 = gnn.SAGEConv(hid, out)
    def forward(self, x, edge_index):
        x = self.c1(x, edge_index).relu()
        return self.c2(x, edge_index)

Frameworks: PyTorch Geometric (PyG) e DGL são os dois padrões.

9.1 Property graph vs RDF/SPARQL

Para um KG interno de produto, property graph costuma ser mais produtivo. RDF ganha quando você precisa integrar com vocabulários públicos (schema.org, Wikidata), fazer inferência formal, ou publicar dados ligados.

9.2 Ontologia e resolução de entidades — onde a qualidade se decide

• Ontologia / esquema: quais tipos de nó e de relação existem e como se conectam (Pessoa TRABALHA_EM Empresa; Empresa SEDIADA_EM Cidade). Sem isso, o KG vira um amontoado inconsistente. Comece pequeno e específico ao caso de uso.
• Resolução de entidades (entity resolution / linking): "IBM", "I.B.M." e "International Business Machines" nos textos são um nó. É o passo mais trabalhoso e mais impactante: heurísticas (normalização, similaridade), blocking para escalar, modelos de matching, e ligação a um identificador canônico (Wikidata QID, um id interno).
• Proveniência: cada aresta guarda de onde veio (documento, trecho, data, confiança). Essencial para auditar e para o GraphRAG citar fontes.

9.3 Construir um KG a partir de texto

1. Extração de entidades (NER) e de relações — hoje frequentemente com um LLM guiado por um schema-alvo ("extraia triplas (Pessoa, CARGO_EM, Organização)").
2. Normalização e resolução de entidades contra o KG existente.
3. Carga das triplas/nós com proveniência; deduplicação de arestas.
4. Validação: consistência com a ontologia, detecção de contradições, amostragem humana.
5. Atualização incremental: novos documentos adicionam/reforçam arestas; versionar e permitir expiração de fatos.

9.4 GraphRAG tema em alta

RAG clássico recupera trechos por similaridade vetorial. Ele falha em perguntas que exigem conectar informação espalhada ("quais fornecedores da empresa A também fornecem para concorrentes dela?") e em perguntas globais ("quais os temas principais deste corpus?"). GraphRAG usa um KG construído do corpus:

• Recuperação por travessia: encontrar as entidades da pergunta no KG e trazer a subrede relevante (vizinhos, caminhos entre entidades) como contexto para o LLM — respostas multi-hop com as ligações explícitas.
• Resumo por comunidade (abordagem da Microsoft): detectar comunidades no KG (Leiden), pré-resumir cada uma, e responder perguntas globais agregando os resumos de comunidade.
• Híbrido: combinar recuperação vetorial de trechos + contexto do grafo; o grafo dá estrutura e citação, os trechos dão o texto literal.
• Custo: construir e manter o KG (extração com LLM é cara) — justifique com perguntas que o RAG vetorial comprovadamente erra. Não é substituto universal do RAG clássico.

Conecta com a apostila de IA Generativa & RAG (retrieval, avaliação) e com a Modelagem de Dados NoSQL (módulo 7, modelagem de grafo e KG).

10.1 Visualização de grafos

• Layouts: force-directed (ForceAtlas2, Fruchterman-Reingold) para estrutura geral; hierárquico/Sugiyama para DAGs; circular/arc para poucos nós; matriz de adjacência para grafos densos (evita o "hairball").
• Ferramentas: Gephi (exploração desktop), Cytoscape.js e D3-force (web interativo), graphviz (DAGs estáticos), yFiles/sigma.js (grande escala), o próprio Neo4j Bloom.
• Grafos grandes: não plote 100 mil nós — filtre (k-core, maior componente), agregue (desenhe comunidades como super-nós), ou use amostragem. Codifique com tamanho (grau/centralidade), cor (comunidade) e espessura (peso).
• Acessibilidade: não dependa só de cor (→ apostila de WCAG); rótulos legíveis; alternativa em tabela.

10.2 Onde grafos aparecem nas vagas

10.3 Roadmap (5 semanas)

• Sem. 1 — módulos 1–2: implementar do zero (sem lib) BFS, DFS, detecção de ciclo, topológica, componentes conexos; resolver 15 problemas de grafo.
• Sem. 2 — módulos 3–4: Dijkstra + reconstrução de caminho, A* num grid, Kruskal com Union-Find, Tarjan SCC.
• Sem. 3 — módulo 6: NetworkX num dataset real (rede de coautoria, transações, social) — PageRank, betweenness, Louvain; um relatório com achados.
• Sem. 4 — módulos 7–8: node2vec + classificador para classificação de nó; depois GraphSAGE em PyG na mesma tarefa, comparando com baseline MLP+features.
• Sem. 5 — módulo 9: construir um KG pequeno de um corpus (extração com LLM guiada por schema, resolução de entidades básica, Neo4j), e um GraphRAG que responde 5 perguntas multi-hop com citação.

10.4 Banco de perguntas (com a resposta que aprova)

10.5 Fontes

• Algoritmos: CLRS (capítulos de grafo); o capítulo 8 da apostila de Algoritmos com Python; problemas em plataformas de prática.
• Ciência de redes: Networks (Mark Newman); Network Science (Barabási, online e gratuito); documentação do NetworkX e do Neo4j GDS.
• GNN: curso CS224W (Stanford, Machine Learning with Graphs); tutoriais do PyTorch Geometric e do DGL; o livro Graph Representation Learning (Hamilton, gratuito).
• KG / GraphRAG: a documentação do GraphRAG da Microsoft; material do Neo4j sobre KG + LLM; papers de KG embeddings (TransE e sucessores).
• Apostilas irmãs: NoSQL, Modelagem de Dados NoSQL, IA Generativa & RAG, Redes Neurais, Análise de Dados.