- Dada a matriz de adjacências de uma grafo de
vértices, faça um algoritmo que determine se esse grafo é orientado ou não-orientado.
Passo 1
O enunciado pede um algoritmo que, dado a matriz de adjacência de um grafo com N vértices, identifique se o grafo é orientado ou não. O conteúdo principal aqui é grafos e a propriedade de simetria da matriz em grafos não orientados.
Passo 2
Em grafos não orientados, a aresta (i,j) existe se e somente se (j,i) existe, logo a matriz de adjacência é simétrica. Em grafos orientados não há essa obrigação: podemos ter a_{ij} ≠ a_{ji}.
Passo 3
Para aproveitar essa teoria, podemos percorrer apenas metade da matriz (exceto a diagonal) e comparar cada elemento a_{ij} com seu espelho a_{ji}. Se encontrarmos alguma diferença, o grafo é orientado; caso contrário, ao fim do laço, ele é não orientado.
Detalhando o procedimento: inicializamos um indicador assumeNãoOrientado=true. Para i de 1 até N-1 e para j de i+1 até N, comparamos a_{ij} e a_{ji}. Se forem diferentes, definimos assumeNãoOrientado=false e interrompemos as verificações.
Detalhando o procedimento: inicializamos um indicador assumeNãoOrientado=true. Para i de 1 até N-1 e para j de i+1 até N, comparamos a_{ij} e a_{ji}. Se forem diferentes, definimos assumeNãoOrientado=false e interrompemos as verificações.
Passo 4
Ao final das comparações, se assumeNãoOrientado ainda for verdadeiro, retornamos “não orientado”; caso contrário, retornamos “orientado”. A complexidade desse método é O(N^2), pois percorremos aproximadamente N(N-1)/2 comparações.
Resposta
Pseudocódigo:
Entrada: matriz A[1..N][1..N]
assumeNaoOrientado ← verdadeiro
para i de 1 até N-1 faça
para j de i+1 até N faça
se A[i][j] ≠ A[j][i] então
assumeNaoOrientado ← falso
sair dos dois laços
fim se
fim para
fim para
se assumeNaoOrientado então
imprimir "Grafo não orientado"
senão
imprimir "Grafo orientado"
fim se