Grafos Direcionados: Quando a Direção Importa

Enunciado: Considere um quarteirão de Copacabana, no Rio de Janeiro, limitado por quatro vias — a Avenida Atlântica, a Rua Figueiredo Magalhães, a Avenida Nossa Senhora de Copacabana e a Rua Santa Clara — com a Rua Domingos Ferreira cortando o quarteirão ao meio. Modele esse quarteirão primeiro como um grafo \(G\) comum e depois como um dígrafo \(D\), registrando o sentido do trânsito de cada rua.

Solução: Cada esquina (cruzamento de ruas) é um vértice, identificado pelas duas ruas que se cruzam ali: \(AF\) (Atlântica × Figueiredo), \(AS\) (Atlântica × Santa Clara), \(DF\) (Domingos Ferreira × Figueiredo), \(DS\) (Domingos Ferreira × Santa Clara), \(NF\) (N. S. Copacabana × Figueiredo) e \(NS\) (N. S. Copacabana × Santa Clara). Cada trecho de rua entre duas esquinas vizinhas é uma aresta.

Sem considerar o sentido do trânsito, isso já é um grafo \(G\) comum, com arestas

Mas as ruas têm sentido de tráfego: a Av. Atlântica tem mão dupla; a Rua Figueiredo Magalhães é de mão única no sentido \(AF \to DF \to NF\); a Rua Santa Clara tem mão única no sentido oposto, \(NS \to DS\) e \(DS \to AS\); a Rua Domingos Ferreira flui de \(DF\) para \(DS\); e a Av. Nossa Senhora de Copacabana flui de \(NS\) para \(NF\). Registrando cada sentido como um arco, obtemos o dígrafo

— o mesmo quarteirão, agora com a informação de para onde o trânsito pode seguir em cada rua. A figura abaixo mostra as duas versões lado a lado:

Enunciado: Para o dígrafo \(D\) com \(V = \{a, b, c, d, e\}\) e \(E = \{(a,b),(b,c),(a,e),(b,e),(e,b),(e,c),(d,c),(d,e)\}\), descreva as relações de adjacência de cada vértice.

Solução:

• \(a\): aponta para \(b\) e \(e\) (mas ninguém aponta para \(a\))
• \(b\) e \(e\) têm arcos em ambas as direções entre si: \((b,e)\) e \((e,b)\)
• \(c\): recebe arcos de \(b\), \(e\) e \(d\), mas não aponta para ninguém

Enunciado: Construa o grafo subjacente do dígrafo \(D\) do exemplo anterior (\(V=\{a,b,c,d,e\}\), arcos \(\{(a,b),(b,c),(a,e),(b,e),(e,b),(e,c),(d,c),(d,e)\}\)).

Solução: O grafo subjacente é construído em duas etapas:

1. Remover as direções: cada arco vira uma aresta comum. Como \((b,e)\) e \((e,b)\) eram dois arcos distintos entre os mesmos vértices, viram duas arestas paralelas entre \(b\) e \(e\).
2. Remover as arestas paralelas: as duas arestas entre \(b\) e \(e\) colapsam em uma só.

O resultado é o grafo subjacente \(G\), com arestas \((a,b), (a,e), (b,c), (b,e), (e,c), (c,d), (d,e)\) — 7 arestas, uma a menos que os 8 arcos originais de \(D\). A figura abaixo mostra as duas etapas:

Enunciado: Encontre duas orientações diferentes do grafo subjacente \(G\) do exemplo anterior.

Solução: Duas possibilidades:

• \(\vec{G}\): \((a,b), (a,e), (b,c), (e,b), (c,e), (c,d), (e,d)\)
• \((\vec{G})’\): a orientação oposta de cada aresta — \((b,a), (e,a), (c,b), (b,e), (e,c), (d,c), (d,e)\)

As duas são dígrafos válidos sobre o mesmo grafo subjacente \(G\), mas com arcos apontando em sentidos diferentes — por isso a orientação de um grafo não é única, como mostra a figura:

Enunciado: Calcule o grau de entrada e o grau de saída de cada vértice do dígrafo \(D\) do exemplo acima (\(V = \{a,b,c,d,e\}\)), e identifique fontes e sumidouros.

Solução:

\(a\) e \(d\) são fontes; \(c\) é sumidouro.

Soma dos graus de saída: \(2+2+0+2+2 = 8 = |E|\). ✓

Contar arcos à mão funciona para dígrafos pequenos, mas o networkx já traz o grau de entrada e de saída prontos como métodos do próprio dígrafo: D.in_degree(v) e D.out_degree(v). O código abaixo percorre cada vértice, calcula os dois graus e marca quem é fonte (\(d^-=0\)) ou sumidouro (\(d^+=0\)):

import networkx as nx

D = nx.DiGraph([("a", "b"), ("b", "c"), ("a", "e"), ("b", "e"),
                ("e", "b"), ("e", "c"), ("d", "c"), ("d", "e")])

for v in sorted(D.nodes()):
    d_mais, d_menos = D.out_degree(v), D.in_degree(v)
    papel = " (fonte)" if d_menos == 0 else " (sumidouro)" if d_mais == 0 else ""
    print(f"{v}: d+={d_mais}, d-={d_menos}{papel}")

a: d+=2, d-=0 (fonte)
b: d+=2, d-=2
c: d+=0, d-=3 (sumidouro)
d: d+=2, d-=0 (fonte)
e: d+=2, d-=3

O resultado bate exatamente com a tabela calculada à mão.

Enunciado: Considere o dígrafo com \(V = \{a,b,c,d,e,f,g,h\}\) e arcos \(E = \{(a,b),(b,c),(b,e),(c,e),(c,g),(e,a),(e,d),(d,a),(d,c),(d,f),(f,d),(d,h)\}\), mostrado na figura abaixo. Classifique as sequências \(P_1 = a,b,c,e,a,b,c,g\), \(P_2 = a,b,e,d,f,d,c,g\) e \(P_3 = a,b,c,g\).

Solução:

• \(P_1\) é um passeio direcionado de \(a\) a \(g\): os arcos \((a,b)\) e \((b,c)\) são percorridos duas vezes — logo não é um trajeto.
• \(P_2\) é um trajeto direcionado de \(a\) a \(g\): nenhum arco se repete, mas o vértice \(d\) aparece duas vezes — logo não é um caminho.
• \(P_3\) é um caminho direcionado de \(a\) a \(g\): nenhum vértice se repete.

Além disso, \(C_1 = a,b,c,e,d,a\) é um ciclo direcionado, e \(C_2 = d,f,d\) é um ciclo direcionado de comprimento 2 — possível porque \((d,f)\) e \((f,d)\) são ambos arcos de \(D\).

Enunciado: No dígrafo da figura anterior, quais vértices \(a\) alcança? Existe algum vértice que não alcança \(a\)?

Solução: \(a\) alcança \(g\) (via \(a,b,c,g\)), alcança \(f\) (via \(a,b,e,d,f\)) e alcança \(h\) (via \(a,b,e,d,h\)) — na verdade, \(a\) alcança todos os outros vértices.

Isso não vale para todo vértice: \(g\) não tem nenhum arco saindo dele, então \(g\) não alcança ninguém — em particular, \(g\) não alcança \(a\).

Enunciado: Verifique que o dígrafo \(D\) com \(V=\{a,b,c,d,e\}\) e arcos \(E = \{(a,b),(b,c),(c,d),(d,a),(a,e),(c,e),(e,b),(e,d)\}\), mostrado abaixo, é fortemente conexo.

Solução: Basta mostrar que, partindo de qualquer vértice, chega-se a todos os outros. Por exemplo, partindo de \(a\): chega-se a \(e\) diretamente, a \(b\) via \(a,b\), a \(c\) via \(a,b,c\) e a \(d\) via \(a,e,d\) (ou \(a,b,c,d\)). Repetindo essa verificação a partir de cada vértice, confirma-se que \(D\) é fortemente conexo.

Enunciado: Classifique os três dígrafos abaixo, todos com \(V = \{a,b,c,d,e\}\), quanto ao nível de conexidade:

• \(D_1\): arcos \((a,b), (d,a), (b,c), (d,c), (c,e)\).
• \(D_2\): arcos \((a,b), (a,d), (c,b), (c,d), (c,e)\).
• \(D_3\): arcos \((a,b), (d,a), (b,c), (d,c)\), com \(e\) isolado.

Solução:

• Em \(D_1\), \(d\) é uma fonte que alcança todos os demais (\(d \to a \to b \to c \to e\)), e \(e\) é um sumidouro alcançado por todos os demais. Como \(a\), \(b\) e \(c\) formam uma cadeia direta \(a \to b \to c\), todo par de vértices tem caminho em pelo menos um sentido — \(D_1\) é unilateralmente conexo. Mas como nada chega a \(d\) e \(e\) não alcança ninguém, \(D_1\) não é fortemente conexo.
• Em \(D_2\), \(a\) só alcança \(b\) e \(d\), enquanto \(c\) alcança \(b\), \(d\) e \(e\) — nenhum dos dois alcança o outro. Esse único par já basta para \(D_2\) não ser unilateralmente conexo. Mas o grafo subjacente é conexo (todos os vértices se ligam através de \(a\) e \(c\)), então \(D_2\) é fracamente conexo.
• Em \(D_3\), o vértice \(e\) está isolado — nenhum arco o liga aos demais, nem mesmo sem considerar direção. Como o grafo subjacente já é desconexo, \(D_3\) é desconexo.

Verificar conexidade à mão exige checar caminhos entre vários pares de vértices — cansativo mesmo em dígrafos pequenos. O networkx tem uma função pronta para cada um dos três níveis: nx.is_strongly_connected, nx.is_semiconnected (esse é o nome técnico para “unilateralmente conexo”) e nx.is_weakly_connected:

import networkx as nx

D1 = nx.DiGraph([("a", "b"), ("d", "a"), ("b", "c"), ("d", "c"), ("c", "e")])
D2 = nx.DiGraph([("a", "b"), ("a", "d"), ("c", "b"), ("c", "d"), ("c", "e")])
D3 = nx.DiGraph([("a", "b"), ("d", "a"), ("b", "c"), ("d", "c")])
D3.add_node("e")  # e isolado

for nome, D in [("D1", D1), ("D2", D2), ("D3", D3)]:
    print(f"{nome}: forte={nx.is_strongly_connected(D)}, "
          f"unilateral={nx.is_semiconnected(D)}, "
          f"fraco={nx.is_weakly_connected(D)}")

D1: forte=False, unilateral=True, fraco=True
D2: forte=False, unilateral=False, fraco=True
D3: forte=False, unilateral=False, fraco=False

Repare que fraco=True para \(D_1\) também — faz sentido, já que unilateralmente conexo implica fracamente conexo (a hierarquia vista antes). Só \(D_3\) tem fraco=False, exatamente porque \(e\) está isolado.

Enunciado: Construa a matriz de adjacência do dígrafo \(D\) com \(V = \{v_1,v_2,v_3,v_4\}\) e arcos \((v_1,v_2), (v_1,v_4), (v_3,v_2), (v_3,v_4), (v_4,v_2), (v_2,v_4)\), e identifique fontes e sumidouros a partir dela.

Solução:

• Linha de \(v_1\): soma = 2 = \(d^+(v_1)\)
• Coluna de \(v_2\): soma = \(1+0+1+1 = 3 = d^-(v_2)\)
• Colunas de \(v_1\) e \(v_3\) são totalmente nulas: \(v_1\) e \(v_3\) são fontes (nenhum arco chega a eles)
• Nenhuma linha é totalmente nula: \(D\) não tem sumidouro

Enunciado: Construa a matriz de incidência do mesmo dígrafo \(v_1,v_2,v_3,v_4\) do exemplo anterior, agora com os arcos rotulados \(e_1=(v_1,v_2), e_2=(v_3,v_2), e_3=(v_3,v_4), e_4=(v_1,v_4), e_5=(v_4,v_2), e_6=(v_2,v_4)\):

Solução:

Cada coluna tem exatamente um \(+1\) e um \(-1\): por exemplo, a coluna de \(e_5\) tem \(+1\) em \(v_4\) e \(-1\) em \(v_2\), confirmando o arco \((v_4,v_2)\).

O networkx calcula as duas matrizes prontas: nx.to_numpy_array para a de adjacência e nx.incidence_matrix para a de incidência. Só um detalhe: a convenção de sinal do networkx é a oposta da nossa (\(-1\) na cauda e \(+1\) na cabeça, em vez de \(+1\) na cauda e \(-1\) na cabeça) — então basta multiplicar o resultado por \(-1\) para bater com a matriz \(B\) que calculamos à mão:

import networkx as nx

D = nx.DiGraph()
D.add_edges_from([("v1", "v2"), ("v1", "v4"), ("v3", "v2"),
                   ("v3", "v4"), ("v4", "v2"), ("v2", "v4")])
vertices = ["v1", "v2", "v3", "v4"]
arcos = [("v1", "v2"), ("v3", "v2"), ("v3", "v4"), ("v1", "v4"), ("v4", "v2"), ("v2", "v4")]  # e1..e6

A = nx.to_numpy_array(D, nodelist=vertices, dtype=int)
print("Matriz de adjacência:\n", A)

B = -nx.incidence_matrix(D, nodelist=vertices, edgelist=arcos, oriented=True).toarray().astype(int)
print("Matriz de incidência:\n", B)

Matriz de adjacência:
 [[0 1 0 1]
 [0 0 0 1]
 [0 1 0 1]
 [0 1 0 0]]
Matriz de incidência:
 [[ 1  0  0  1  0  0]
 [-1 -1  0  0 -1  1]
 [ 0  1  1  0  0  0]
 [ 0  0 -1 -1  1 -1]]

As duas batem, arco por arco, com as matrizes \(A\) e \(B\) calculadas nos exemplos acima.

O Apache Airflow é a ferramenta mais usada para orquestrar pipelines de dados, e modela cada pipeline literalmente como um DAG: cada tarefa é um vértice, e o operador >> declara um arco de dependência entre duas tarefas.

from datetime import datetime

from airflow import DAG
from airflow.operators.python import PythonOperator


def extrair_dados():
    print("extraindo os dados de vendas")


def transformar_dados():
    print("transformando os dados")


def carregar_dados():
    print("carregando os dados no banco")


with DAG("pipeline_vendas", start_date=datetime(2026, 1, 1), schedule="@daily") as dag:
    extrair = PythonOperator(task_id="extrair_dados", python_callable=extrair_dados)
    transformar = PythonOperator(task_id="transformar_dados", python_callable=transformar_dados)
    carregar = PythonOperator(task_id="carregar_dados", python_callable=carregar_dados)

    extrair >> transformar >> carregar  # arcos do DAG: extrair -> transformar -> carregar

Traduzindo para a linguagem deste artigo: cada PythonOperator é um vértice (uma tarefa que executa uma função Python); o bloco with DAG(...) declara o dígrafo em si, com um nome e uma frequência de execução; e a linha extrair >> transformar >> carregar declara os arcos \((extrair, transformar)\) e \((transformar, carregar)\), na ordem em que as tarefas precisam rodar. Na hora de executar, o Airflow segue uma ordenação topológica desse DAG.

Se alguém tentasse fechar o ciclo com carregar >> extrair, o Airflow recusaria o DAG na validação — a aciclicidade não é só uma curiosidade teórica, é uma regra que a ferramenta impõe.

Para o dígrafo \(D\) com vértices \(\{a,b,c,d\}\) e arcos \(\{(a,b),(a,c),(c,a),(c,b),(d,a),(d,c)\}\):

(a) Quem são as fontes? (b) Quem são os sumidouros? (c) \(a\) alcança todos os vértices? (d) \(D\) é fortemente conexo?

Solução:

(a) Fonte: \(d\) — nenhum arco chega a \(d\) (\(d^-(d) = 0\)).

(b) Sumidouro: \(b\) — nenhum arco parte de \(b\) (\(d^+(b) = 0\)).

(c) De \(a\): \(a \to b\) ✓, \(a \to c\) ✓, mas \(a\) não alcança \(d\). Falso.

(d) Não, pois \(d\) é fonte — nenhum vértice alcança \(d\). Logo \(D\) não é fortemente conexo.

Classifique como fortemente, unilateralmente ou fracamente conexo:

(a) Cadeia linear \(a \to b \to c \to d \to e \to f\) (b) Ciclo \(a \to b \to c \to a\) com arco extra \(b \to d\)

Solução:

(a) Unilateralmente conexo: de \(a\) alcança-se todos os vértices. Para qualquer par \((v_i, v_j)\) com \(i < j\), existe caminho de \(v_i\) para \(v_j\). Mas \(f\) não alcança \(a\): não é fortemente conexo.

(b) O vértice \(d\) não tem nenhum arco saindo — é sumidouro, então não alcança ninguém. Como \(d\) não alcança nenhum outro vértice, o dígrafo não é fortemente conexo. Mas todo vértice alcança \(d\) (\(a \to b \to d\), \(b \to d\), \(c \to a \to b \to d\)), e entre \(a\), \(b\) e \(c\) o ciclo garante caminho nos dois sentidos — logo todo par tem caminho em pelo menos um sentido, e o dígrafo é unilateralmente conexo.