Um grafo é dito balanceado se, em um grafo direcionado, o grau de entrada de cada vértice é igual ao seu grau de saída. Considere o grafo com a seguinte matriz de adjacência:
(b) O grafo é balanceado? Justifique sua resposta.
Passo 1
Resumo do enunciado: a gente tem um grafo dirigido dado pela matriz de adjacência
Conteúdo: teoria de grafos — grau de entrada (in‐degree) e grau de saída (out‐degree).
O que vamos usar:
• Definição: num grafo dirigido, o grau de saída de um vértice é .
• Grau de entrada é .
• Grafo balanceado ⇔ para todo vértice , .
Passo 2
Vamos calcular o grau de saída de cada vértice somando as linhas da matriz:
vértice 1:
vértice 2:
vértice 3:
vértice 4:
Passo 3
Agora o grau de entrada somando as colunas da matriz:
vértice 1:
vértice 2:
vértice 3:
vértice 4:
Passo 4
Compara in e out para cada vértice:
in 2 = out 2 ✔
in 1 ≠ out 2 ✘
in 2 = out 2 ✔
in 2 ≠ out 1 ✘
Resposta
Não, o grafo não é balanceado, pois os vértices 2 e 4 têm grau de entrada diferente do grau de saída.