2

Gostaria de saber se alguém sabe se é possível eliminar todos os ciclos de um grafo não-direcionado (n vértices) sem pesos, removendo o menor número de vértices, em tempo O(n²)?

Obs: O grafo pode ser completo, na pior das hipóteses.

1 Resposta 1

1

Primeiro, você tenta fazer uma ordenação topológica do grafo. Numa ordenação topológica, você define uma ordem que diz quais vértices vem antes ou depois de quais outros vértices. Em um grafo com ciclos, não existe ordenação topológica. Vou copiar o algoritmo referenciado nesse link, mas com algumas modificações pontuais minhas para esclarecer melhor:

// Algoritmo de ordenação topológica, versão 1.
G ← grafo de entrada
L ← lista vazia que irá conter os vértices ordenados topologicamente
S ← conjunto de todos os vértices de G sem arestas de entrada
A ← conjunto de todas as arestas de G
enquanto S é não-vazio faça
    remova um vértice N de S
    insira N em L
    para cada vértice M em G com uma aresta E de N até M faça
        remova a aresta E de A
        se M não tem mais arestas de entrada em A então
            insira M em S
se o A é não-vazio então
    retorne que o grafo G tem pelo menos um ciclo com arestas A
senão
    retorne que L é uma ordenação topológica proposta

A parte de computar o S pode ser feita assim:

// Algoritmo para computar as arestas sem entrada.
G ← grafo de entrada
S ← lista com todos os vértices de G
para cada aresta Y dentro de G faça
   F ← vértice de destino da aresta Y
   remova F de S (se já não tiver sido removido antes)

Para computar S, a complexidade é de VE, pois temos que construir a lista de vértices V e percorrer a lista de arestas E.

No algoritmo da ordenação topológica, a complexidade do laço enquanto é E. Dentro do enquanto, há um laço para. Cada iteração do para remove uma aresta, de forma que no pior caso, todas as arestas são removidas, o que dá E.

Poder-se-ia pensar que o laço enquanto corre o risco de ser infinito por tirar vértices de S no começo e reintroduzir vértices em S dentro do se que está dentro do para. Entretanto, as arestas são progressivamente removidas e os vértices só são introduzidos quando arestas são removidas. Logo, o número de vértices introduzidos não tem como ser maior que o número de arestas, o que garante que o laço enquanto não é infinito. Além disso, os vértices introduzidos não são os mesmos que são removidos, pois S contém apenas vértices sem arestas de entrada que são eliminados, enquanto que os lá acrescentados são apenas aqueles que acabaram de ter todas as arestas de entrada removidas.

O se no final e a construção de L vazio na primeira linha têm complexidade 1. A construção de A antes do laço enquanto tem custo E. Assim sendo, esse algoritmo têm complexidade total de VE.

Esse algoritmo tenta formar uma ordenação topológica ao remover arestas e vértices do grafo (na verdade dos conjuntos A e S) até que no final ele fique vazio. Se ele não conseguir remover todos os vértices e arestas desses grupos, então todas as que sobrarem fazem parte de algum ciclo.

Assim sendo, você pode fazer isso:

// Algoritmo de remoção do menor número de vértices de ciclos, versão 1.
G ← grafo de entrada
R ← lista que receberá os vértices a serem removidos
enquanto a ordenação topológica (versão 1) de H contém um ciclo de arestas A faça
    G ← novo grafo com as arestas de A e os vértices correspondentes
    C ← vértice de origem de alguma aresta qualquer de A
    remova C de H junto com todas as arestas que entram ou saem de C
    insira C em R

Criar R como uma lista vazia tem custo 1. A segunda e a quarta instrução do corpo do laço enquanto têm complexidade 1. No pior caso, ignorando-se a primeira instrução do laço enquanto, ao final desse algoritmo, todos os vértices e todas as arestas serão removidas pela terceira instrução do laço enquanto até a condição que o guarda tornar-se falsa, logo o custo total dessa instrução (ignorando-se o custo da primeira instrução do laço enquanto e somando-se todas as iterações do laço) é de VE.

O problema agora é saber quantas vezes a ordenação topológica de H será tentada no laço enquanto. No pior caso (um grafo completo), se S tiver todas as arestas de H, a cada iteração do enquanto, uma aresta de H é removida. Assim sendo, o número de iterações desse laço no pior caso é de V. Em cada uma dessas iterações, uma ordenação topológica é feita com o custo VE. Assim sendo, o custo total do laço no pior caso (ainda ignorando-se a criação de um novo grafo G) é V2VE.

Porém, a estimativa do pior caso ser V2VE é exagerada. Se olharmos melhor o algoritmo da remoção do menor número de vértices e o da ordenação topológica em conjunto, vemos que o enquanto da ordenação topológica remove vértices e arestas até sobrar somente ciclos, e o enquanto da remoção do menor número de vértices dos ciclos remove os vértices que formam ciclos junto com as arestas que neles incidem. como não há forma de um mesmo vértice ou uma mesma aresta ser removida duas vezes e nenhum vértice ou aresta é vistado sem ser removido, concluímos que a complexidade na verdade é VE.

No entanto, ainda há dois problemas. O primeiro é obviamente que nós ignoramos o custo de recriar G, o que aumenta bastante a complexidade por ser uma operação complexa realizada dentro do laço. O segundo é que nada garante que a escolha dos vértices removidos em R é mínima. Por exemplo, suponha que eu tenho um grafo com dois ciclos que tenham um único vértice como intersecção (o grafo é a figura de um número 8). Se eu remover o vértice central, com uma remoção eu chego ao resultado ótimo. Mas se o algoritmo escolher outro vértice para remover, serão necessárias duas remoções para quebrar todos os ciclos. A solução para esses dois problemas é realizar essa pequena modificação na primeira instrução do corpo do laço enquanto:

// Algoritmo de remoção do menor número de vértices de ciclos, versão 2.
G ← grafo de entrada
R ← lista que receberá os vértices a serem removidos
H ← clone de G
enquanto a ordenação topológica (versão 1) de H contém um ciclo de arestas A faça
    C ← vértice que aparece mais vezes nas arestas de A
    remova C de H junto com todas as arestas que entram ou saem de C
    insira C em R

Ao sempre remover o vértice que aparece mais vezes nas arestas que formam ciclos, você garante que o maior número possível de ciclos estão sendo quebrados ao removê-lo.

Entretanto temos mais um outro problema: Contar o número de vezes que cada vértice aparece em cada iteração do laço enquanto é custoso e aumenta o nosso grau de complexidade (assim como recriar o grafo). Podemos resolver esses problemas ao alterar-se o algoritmo da ordenação topológica para que ele contabilize o grau e remova vértices não mais desejados:

// Algoritmo de ordenação topológica destrutiva, versão 2.
G ← grafo de entrada
L ← lista vazia que irá conter os vértices ordenados topologicamente
S ← conjunto de todos os vértices de G sem arestas de entrada
A ← conjunto de todas as arestas de G
T ← mapeamento dos graus de cada vértice de G
enquanto S é não-vazio faça
    remova um vértice N de S
    remova N de G
    insira N em L
    coloque 0 em T na posição de N
    para cada vértice M em G com uma aresta E de N até M faça
        remova a aresta E de A e de G
        subtraia 1 em T na posição de M
        se M não tem mais arestas de entrada em A então
            insira M em S
se o A é não-vazio então
    C ← vértice com o maior número em T
    retorne que:
        o grafo G tem pelo menos um ciclo com arestas A e;
        C é o vértice com mais incidências
senão
    retorne que L é uma ordenação topológica proposta

Computar T antes do enquanto tem custo VE. Computar C tem custo V. As demais operações que foram colocadas no algoritmo têm custo 1, elas também resolvem o problema de recriar o grafo: ao invés de recriá-lo, eu faço modificações destrutivas nele. Logo, o algoritmo da ordenação topológica continua sendo VE.

E então, temos uma terceira versão do nosso algoritmo de remoção de vértices:

// Algoritmo de remoção do menor número de vértices de ciclos, versão 3.
G ← grafo de entrada
R ← lista que receberá os vértices a serem removidos
H ← clone de G // sofrerá modificações destrutivas,
               // por isso queremos preservar o original.
enquanto a ordenação topológica destrutiva (versão 2) de H contém:
        um ciclo A e;
        um vértice C que aparece mais vezes
faça
    remova C de H junto com todas as arestas que entram ou saem de C
    insira C em R

O custo de criar o H original como um clone de G é VE. O custo no pior caso do laço enquanto continua VE e dessa vez sem ignorar a parte de reconstruir/modificar o garfo. Apesar disso, ainda dá para melhorar um pouquinho!

Se você considerar que o grafo de entrada não contém arestas paralelas (ou seja, duas ou mais arestas saindo de um mesmo vértice A e entrando em um mesmo vértice B), então não haverá como o número de arestas ser mais do que o quadrado do número de vértices (ou seja, EmV), e portanto, no pior caso, teríamos Fim.

Por outro lado, se o seu grafo puder ter arestas paralelas, você pode eliminá-las assim: Você cria um array com V2s entradas booleanas (matriz de adjacência) de forma que cada entrada corresponde a uma possível de entrada e saída do grafo, ou seja, cada uma corresponde a uma possível aresta. Esse array é inicializado com todas as posições com falso. Você então percorre todas as arestas e põe verdadeiro nas que achar. Depois, você usa o array resultante para remontar o grafo, sem as arestas repetidas e então tenta remover os vértices do ciclo. A complexidade do processo de eliminar as arestas repetidas e remontar o grafo será de V2E, mas isso vai fazer a complexidade de remover os vértices dos ciclos ir para V2. Assim sendo, a complexidade total será V2E.

Assim, chegamos na última versão do nosso algoritmo de remoção de vértices:

// Algoritmo de remoção de arestas paralelas
G ← grafo de entrada
T ← número de vértices de G
Z ← matriz booleana com o T * T posições
para cada aresta W de G:
    P ← número do vértice de entrada de W // primeira posição é zero
    Q ← número do vértice de saída de W   // primeira posição é zero
    U ← P * T + Q
    Z[U] ← verdadeiro
// Algoritmo de remoção do menor número de vértices de ciclos, versão 4.
G ← grafo de entrada
R ← lista que receberá os vértices a serem removidos
H ← clone de G // sofrerá modificações destrutivas,
               // por isso queremos preservar o original.
remova as arestas paralelas de H.
enquanto a ordenação topológica destrutiva (versão 2) de H contém:
        um ciclo A e;
        um vértice C que aparece mais vezes
faça
    remova C de H junto com todas as arestas que entram ou saem de C
    insira C em R

Por fim, notamos que essa própria matriz booleana de adjacência pode servir para representar o grafo.

Já sabemos que no pior caso, a complexidade do algoritmo é V2. Vez que para que essa matriz de adjacência ser construída e também para ser percorrida a fim de determinar-se quais são os vértices sem entradas, será necessário que todas as células dessa matriz sejam acessadas, bem como todas as arestas paralelas, então temos um limite inferior de complexidade OmegaV2E. Como o limite inferior e superior são iguais, então a complexidade do algoritmo é ThetaV2E.

Se o grafo original já estiver representado em forma de matriz de adjacência (com valores 0 onde não há aresta, 1 onde há uma aresta e 2 ou mais onde há arestas paralelas), a complexidade será ThetaV2 porque nesse caso, o algoritmo para remover as arestas paralelas pode simplesmente percorrer a matriz de adjacência e trocar quaisquer números maiores ou iguais a 2 por 1.

2
  • 1
    Essa matriz de booleanos é chamada de matriz de adjacência Commented 15/04/2018 às 3:46
  • 1
    @JeffersonQuesado Sim. o porém é que como ela rejeita arestas paralelas ela só tem 0 e 1, enquanto que a definição conceitual de matriz de adjacência aceitaria quaisquer valores inteiros maiores ou iguais a zero onde 2 ou mais indicaria a existência de arestas paralelas. Aliás, essa própria matriz booleana de adjacência representa o grafo. Commented 15/04/2018 às 5:27

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .