não consigo entender uma certa parte do artigo publicado por Donald Johnson sobre encontrar ciclos (circuitos) em um gráfico.

Mais específico, não consigo entender qual é a matriz Ak mencionada na seguinte linha do pseudo-código:

Ak: = estrutura de adjacência do componente forte K com menos vértice no subgrafo de G induzido por {s, s + 1, .... n};

para piorar as coisas algumas linhas depois é mencionado "para i in Vk do" sem declarar o que é o Vk ...

Até onde eu entendi, temos o seguinte: 1) em geral, um componente forte é um subgrafo de um gráfico, no qual, para cada nó deste subgrafo, existe um caminho para qualquer nó do subgrafo ( em outras palavras, você pode acessar qualquer nó do subgrafo a partir de qualquer outro nó do subgrafo)

2) um sub-gráficoinduzidopor uma lista de nós, há um gráfico que contém todos esses nós, além de todas as arestas que os conectam. no papel, a definição matemática é "F é um subgrafo de G induzido por W se W é um subconjunto de V e F = (W, {u, y) | u, y em W e (u, y) em E)})" onde u, y são arestas, E é o conjunto de todas as arestas no gráfico, W é um conjunto de nós.

3) na implementação do código, os nós são nomeados por números inteiros 1 ... n.

4) eususpeito que o Vk é o conjunto de nós do componente forte K.

agora para a pergunta. Digamos que temos um gráfico G = (V, E) com V = {1,2,3,4,5,6,7,8,9}, que pode ser dividido em 3 componentes fortes, o SC1 = {1, 4,7,8} SC2 = {2,3,9} SC3 = {5,6} (e suas bordas)

Alguém pode me dar um exemplo para s = 1, s = 2, s = 5 e se for o Vk e o Ak de acordo com o código?

O pseudo-código está na minha pergunta anterior emCompreendendo o pseudocódigo no algoritmo de Donald B. Johnson

e o documento pode ser encontrado emCompreendendo o pseudocódigo no algoritmo de Donald B. Johnson

Agradeço antecipadamente