1. Dada a matriz de adjacências de uma grafo de N 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.

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

Exercícios relacionados