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:
[llll 0 & 1 & 1 & 0 0 & 0 & 1 & 1 1 & 0 & 0 & 1 1 & 0 & 0 & 0 ]
(b) O grafo é balanceado? Justifique sua resposta.

Passo 1

Resumo do enunciado: a gente tem um grafo dirigido dado pela matriz de adjacência
A= 0 & 1 & 1 & 0 0 & 0 & 1 & 1 1 & 0 & 0 & 1 1 & 0 & 0 & 0
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.

Exercícios relacionados