Dado um grafo orientado e sem circuitos descrever um algoritmo matricial que faça a ordenação hierárquica dos vértices e que detecte a existência de circuitos. Qual a complexidade deste algoritmo ?
Passo 1
Beleza, vamos entender o que a gente precisa aqui. A questão pede para a gente trabalhar com um grafo orientado, ou seja, um conjunto de vértices conectados por arestas que têm direção. Além disso, o grafo não tem circuitos inicialmente, mas a gente precisa criar um algoritmo que ordene os vértices de forma hierárquica (tipo uma classificação topológica) e que também consiga detectar se há algum circuito no grafo. Para resolver isso, vamos usar matrizes e conhecer um pouquinho sobre grafos direcionados e ordenação topológica.
Passo 2
Primeiro, vamos representar o grafo usando uma matriz de adjacência. Essa matriz é uma forma de mostrar quais vértices estão conectados por arestas. Se tivermos um grafo com $ n $ vértices, nossa matriz será uma matriz quadrada de ordem $ n $, onde a posição $ (i, j) $ é 1 se há uma aresta do vértice $ i $ para o vértice $ j $, e 0 caso contrário.
Passo 3
Agora, para fazer a ordenação hierárquica dos vértices, vamos usar o método conhecido como Ordenação Topológica. Esse método é usado em grafos direcionados acíclicos (DAGs) e organiza os vértices de forma que para cada aresta $ (i, j) $, o vértice $ i $ vem antes do vértice $ j $ na ordenação.
Passo 4
Vamos implementar o algoritmo de Ordenação Topológica utilizando a matriz de adjacência. O passo a passo é o seguinte:
- Calcular o grau de entrada de cada vértice. O grau de entrada de um vértice é o número de arestas que chegam nele, ou seja, o número de 1’s na coluna correspondente na matriz de adjacência.
- Encontrar os vértices com grau de entrada 0. Esses vértices não têm dependências e podem ser colocados no início da ordenação.
- Remover esses vértices do grafo (ou seja, ajustar a matriz de adjacência) e diminuir o grau de entrada dos vértices que eles apontavam.
- Repetir o processo até que todos os vértices sejam ordenados.
Passo 5
Para detectar circuitos, durante a execução da Ordenação Topológica, se em algum momento não conseguirmos encontrar um vértice com grau de entrada 0, isso significa que há um ciclo no grafo. Ou seja, os vértices restantes estão todos se apontando mutuamente, formando um circuito.
Passo 6
Vamos analisar a complexidade desse algoritmo. Supondo que temos $ n $ vértices:
- Inicializar a matriz de adjacência leva $ O(n^2) $ tempo.
- Calcular os graus de entrada também leva $ O(n^2) $ tempo, já que precisamos percorrer a matriz inteira.
- A Ordenação Topológica, no pior caso, também será $ O(n^2) $, pois para cada vértice removido, pode ser necessário atualizar os graus de entrada de $ n $ vértices.
Então, a complexidade total do algoritmo é $ O(n^2) $.
Resposta
Criamos um algoritmo matricial usando a matriz de adjacência para realizar a Ordenação Topológica dos vértices e detectar circuitos no grafo. A complexidade desse algoritmo é de ordem $ O(n^2) $.