Fundamentos e Teoria dos Grafos

1. Definição e Contexto

Uma rede de computadores é, em essência, um grafo: dispositivos são vértices (nós) e enlaces físicos/lógicos são arestas. A teoria dos grafos fornece o arcabouço matemático para analisar topologias de rede, calcular caminhos ótimos, avaliar resiliência e projetar redes eficientes. Sem teoria dos grafos, planejamento de rede fica limitado a intuição e tentativa-erro.

Um grafo é definido formalmente como um par G = (V, E) onde:

• V é o conjunto de vértices (nós): roteadores, switches, hosts, etc.
• E é o conjunto de arestas (links): conexões físicas ou lógicas entre nós.
• Cada aresta e = (u, v) conecta dois vértices u e v ∈ V.

2. Contexto Histórico

A teoria dos grafos nasceu em 1736 com Leonhard Euler e o famoso problema das Pontes de Königsberg. A cidade de Königsberg (atual Kaliningrado) tinha sete pontes conectando duas ilhas no rio Pregel. A questão: é possível atravessar todas as sete pontes uma única vez e voltar ao ponto de partida?

Euler provou que não. O argumento: para um caminho fechado atravessar cada ponte uma única vez (caminho euleriano), cada nó deve ter número par de arestas incidentes (grau par). Em Königsberg, todos os quatro nós tinham grau ímpar — impossível.

3. Tipos de Grafos

3.1 Dirigido vs Não-Dirigido

• Não-dirigido (undirected): aresta (u,v) = (v,u). Ex.: rede Ethernet, Wi-Fi ad-hoc.
• Dirigido (directed, digraph): aresta u→v ≠ v→u. Ex.: enlace de satélite unidirecional, BGP AS-path (as-path é dirigido).

3.2 Ponderado vs Não-Ponderado

• Ponderado (weighted): cada aresta tem peso (custo, latência, banda).
• Algoritmos de roteamento (OSPF, IS-IS) usam grafos ponderados onde peso = inverso da largura de banda (1/bandwidth) ou custo configurado manualmente.

3.3 Conexo vs Desconexo

• Conexo: existe caminho entre qualquer par de vértices.
• Desconexo: dois ou mais componentes isolados.
• Fortemente conexo (digraph): para todo u,v existe caminho u→v e v→u.
• Bipartido: vértices podem ser divididos em 2 conjuntos disjuntos, com arestas somente entre conjuntos (ex.: topologia spine-leaf!).

3.4 Cíclico vs Acíclico

• Cíclico: contém ciclos (caminho fechado com vértices distintos exceto início/fim).
• Acíclico: sem ciclos. Em dirigidos, chamado DAG (Directed Acyclic Graph).
• Árvore: grafo conexo acíclico não-dirigido. Topologia STP é uma árvore.

3.5 Simples vs Multigrafo

• Simples: sem laços (self-loops) nem arestas paralelas.
• Multigrafo: permite arestas paralelas entre mesmo par (ex.: dois cabos físicos entre mesmos switches).

3.6 Completo (clique)

• Grafo completo Kₙ: toda aresta possível existe. Tem n(n-1)/2 arestas. Em uma rede, Kₙ é topologia full mesh.

4. Conceitos Fundamentais

4.1 Grau de um Vértice (degree)

Número de arestas incidentes no vértice. Em digraph: grau de entrada (in-degree) + grau de saída (out-degree).

Teorema do Aperto de Mãos: a soma dos graus de todos os vértices é o dobro do número de arestas:

Consequência: o número de vértices de grau ímpar é sempre par.

4.2 Vizinhança

• Vizinhança aberta N(v): vizinhos de v, excluindo v.
• Vizinhança fechada N[v]: vizinhos de v, incluindo v.

4.3 Caminho e Caminho Mínimo

• Caminho (walk): sequência de arestas conectadas.
• Trilha (trail): caminho sem aresta repetida.
• Caminho simples (path): sem vértice repetido.
• Caminho mínimo (shortest path): caminho com menor soma de pesos.

4.4 Distância

• Distância d(u,v): comprimento do caminho mínimo entre u e v.
• Excentricidade ε(v): máxima distância de v a qualquer outro vértice.
• Diâmetro diam(G): máxima excentricidade = maior distância mínima entre quaisquer dois vértices.
• Raio rad(G): mínima excentricidade.

Em redes reais, diâmetro baixo é desejável: menos hops = menos latência. Spine-leaf tem diâmetro 2 (qualquer servidor a servidor em 2 hops).

4.5 Componentes Conexos e Cliques

Componentes conexos são subgrafos conexos máximos; o número é k(G). Em rede sem redundância, queda de um nó pode fragmentar o grafo em múltiplos componentes. Clique: subconjunto de vértices totalmente conectados entre si. Conjunto independente: subconjunto sem nenhuma aresta interna.

5. Árvores e Florestas

• Árvore: grafo conexo acíclico. Tem |V| − 1 arestas.
• Floresta: grafo acíclico desconexo (várias árvores).
• Árvore geradora (spanning tree): subgrafo que é árvore e inclui todos os vértices.
• Árvore geradora mínima (MST): spanning tree de peso total mínimo.

Algoritmos clássicos: Kruskal (ordena arestas por peso, adiciona se não forma ciclo, O(E log E)) e Prim (expande pela aresta mais barata, O(E log V)). Em redes, STP (Spanning Tree Protocol) é uma MST distribuída — embora não minimize peso, encontra uma árvore livre de loops.

6. Caminhos Mínimos

6.1 Algoritmo de Dijkstra

Encontra caminho mínimo de uma origem a todos os demais (single-source shortest path) para grafos com pesos não-negativos. Complexidade O((V+E) log V) com heap binário.

import heapq

def dijkstra(G, s):
    dist = {v: float('inf') for v in G}
    dist[s] = 0
    pq = [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in G[u]:
            if dist[v] > d + w:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    return dist

Aplicação em redes: OSPF usa Dijkstra para construir Shortest Path Tree. Link-State Database é o grafo completo; SPF é executado periodicamente.

6.2 Bellman-Ford

Permite pesos negativos; detecta ciclos negativos. Usado em RIP (counting to infinity problem) e BGP (path-vector). Floyd-Warshall computa all-pairs shortest path em O(V³); útil para planejamento de roteamento global. A* (A-star) é heurístico, usado em GPS e roteamento planetário.

7. Fluxo em Redes

Modelagem para roteamento de banda: cada aresta tem capacidade c(u,v); fonte s e sorvedouro t; fluxo máximo = máximo de unidades que podem fluir de s a t. Algoritmos: Ford-Fulkerson (1956), Edmonds-Karp (O(VE²)), Push-Relabel (O(V²E)). Teorema de max-flow min-cut: o fluxo máximo = capacidade do corte mínimo que separa s de t. Aplicações: dimensionamento de backbones, cálculo de bissecção de rede, SDN traffic engineering.

8. Resiliência e Conectividade

Conectividade de vértices κ(G): mínimo número de vértices que precisam ser removidos para desconectar o grafo. Conectividade de arestas λ(G): mínimo número de arestas que precisam ser removidas. Teorema de Whitney: κ(G) ≤ λ(G) ≤ δ(G) (grau mínimo). Uma rede k-conexa permanece conexa após a remoção de k-1 nós — fator crítico em projetos de alta disponibilidade.

9. Centralidade

Medidas de importância de nós: centralidade de grau (k_v/(n-1)), centralidade de proximidade (1/Σ d(u,v)), centralidade de intermediação/betweenness (fração de caminhos mínimos que passam pelo nó) e centralidade de autovetor (importância ponderada pela importância dos vizinhos — base do PageRank). Aplicações: identificar roteadores críticos, pontos de bottleneck, gargalos em DC.

10. Modelos de Geração de Grafos

• Erdős-Rényi G(n,p): cada aresta existe com probabilidade p. Diâmetro ~log n, mas sem hubs (pouco realista).
• Watts-Strogatz (1998): redes "small-world" com alto clustering + baixo caminho médio.
• Barabási-Albert (1999): redes "livre de escala" com P(k) ~ k^(-γ), decorrente de crescimento preferencial (rich-get-richer). Internet é scale-free!

11. Aplicações em Redes Reais

• OSPF: grafo ponderado, Dijkstra, MST (SPF tree).
• BGP: grafo dirigido de ASs, path-vector.
• STP/RSTP/MSTP: spanning tree em L2.
• SDN (OpenFlow): controlador calcula caminhos sobre grafo topológico.
• Network slicing 5G: particionamento de grafo por demanda.

12. Ferramentas e Conclusão

import networkx as nx

G = nx.Graph()
G.add_edges_from([('A','B'), ('B','C'), ('C','A'), ('C','D')])
print(nx.degree(G, 'C'))              # 3
print(nx.shortest_path(G, 'A', 'D'))   # ['A', 'C', 'D']
print(nx.diameter(G))                  # 2

13. Conclusão

A teoria dos grafos é a linguagem matemática natural das redes de computadores. Topologia, roteamento, resiliência, centralidade — todos conceitos que têm contrapartida rigorosa em grafos. Engenheiros de redes que dominam grafos têm vantagem sistemática: podem provar propriedades, calcular limites e otimizar topologias com rigor, em vez de intuição. Em eras de SDN, AIOps e redes dinâmicas, esse conhecimento é ainda mais crítico.