Construa um DAG a partir de múltiplas ordenações topológicas

Question

Preciso construir um DAG, a partir de suas ordenações topológicas (ou seja,o gráfico $G$ criado deve ter todas as ordenações dadas como suas ordenações topológicas).Para simplificar, os vértices são rotulados como primeiro $n$ números naturais.(Observe que uma vez criado, o gráfico $G$ pode ter mais ordenações topológicas além daquelas fornecidas.)
As seguintes restrições devem ser atendidas:

1. O outdegree máximo de cada nó deve ser 1
2. O número de nós com indegree 0 deve ser mínimo.

Pode haver várias soluções, qualquer uma delas deve funcionar.

O que eu tentei.(Abordagem 1 o que está errado, pois falha em um exemplo dado na resposta.Vá para a segunda abordagem, que ainda não consigo encontrar um erro.)

Abordagem 1
A partir de todas as ordenações fornecidas, primeiro, crie um gráfico direcionado criando uma aresta direcionada de cada nó para o próximo nó.Isso significa que se os pedidos forem:
$$ 1, 3, 2, 5, 4, 6 $$ $$ 3, 1, 5, 2, 4, 6 $$ $$ 1, 5, 3, 2, 4, 6 $$

Criarei um gráfico direcionado com uma aresta direcionada de $1$ para $3, 3$ para $2, 2$ para $5$ e assim por diante.

Isso garante que o número de nós com indegree 0 permaneça mínimo.Agora, vou remover todos os ciclos e ter certeza de que todas as ordenações são válidas e, finalmente, eliminar todas as arestas extras que qualquer nó possui.Ao fazer isso, terei certeza de que, se houver dois nós cuja aresta vem do mesmo nó, removerei a aresta do nó com um grau de entrada mais alto, para que a condição 2 seja atendida.O gráfico construído então deverá ficar assim:

Este DAG criado segue ambas as restrições, e o IMO tem o número mínimo de nós de indegree como 0, embora não esteja comprovado.

Codifiquei a abordagem e ela está dando os resultados esperados para os casos de uso que forneço, mas sei que está errada.O que estou perdendo aqui?Alguém pode fornecer um caso de uso alternativo que falhe na abordagem acima?

Abordagem 2
Eu crio um gráfico direcionado $G$ criando uma borda de $a_i $ para $a_j$ para todos $ j > eu$ em todas as ordens dadas.Então, para os pedidos:
$$ 1, 2, 3, 4, 5$$ $$ 2, 4, 1, 5, 3$$

Vou criar o seguinte gráfico:
O primeiro passo depois disso é validar todos os pedidos.Não é necessário remover os ciclos separadamente, pois eles serão removidos nesta etapa.
Para qualquer pedido$$ a_1, a_2, a_3, a_4, ...a_n $$Vou verificar se existe alguma aresta de $a_j$ para $a_i$ onde $ j > eu$, vou remover essa borda.
Fazendo isso, obteremos o seguinte gráfico:
A última etapa é remover arestas extras de todos os nós, pois o grau máximo de qualquer nó pode ser $1$ máx.Removerei as arestas de saída de modo que o número de nós com grau de entrada $0$ é mínimo.Primeiro calculo o grau de entrada de cada nó.Então, para cada nó que tenha mais de uma aresta de saída, removerei todas as arestas, exceto aquela com o grau mínimo.

O gráfico final $G$ vai parecer:

Este gráfico satisfaz ambas as restrições.Mas eu sei que essa abordagem está errada!Alguém pode ajudar a descobrir por que isso está errado?

Answer 1

Abordagem 1

Por exemplo, considere as duas ordens:1, 2, 3, 4, 5 e 2, 4, 1, 5, 3.

De acordo com a sua abordagem, obteremos um ciclo 1->2->3->4->1.Em seguida, removemos 3->4 e 4->1 e obtemos um gráfico:

     ______
    /      \
1->2->4->5->3
 \______/

Agora 5->3 e 1->2 violam respectivamente a primeira e a segunda ordens, então nós os removemos e obtemos

     ______
    /      \
1  2->4->5  3
 \______/

Agora o nó 2 tem 2 arestas de saída.A remoção de qualquer um deles cria um gráfico final onde 3 nós (1, 2, 3 ou 1, 2, 4) têm grau 0.

No entanto, existe um gráfico

1->3 2->4->5

onde ambos os pedidos são satisfeitos, mas apenas 2 nós têm grau 0.

Portanto, a abordagem 1 está incorreta.

Abordagem 2

Considere uma solução ótima.Cada aresta nesta solução ótima deve ter a forma $(a_i,a_j)$ onde $eu<j$ em cada pedido.Isso significa que todas as arestas da solução ótima estão contidas no gráfico intermediário.Portanto, se você remover as arestas de saída de modo que o número de nós com grau 0 seja mínimo, você obterá uma solução ótima correta.

No entanto, sua abordagem de tentar fazer com que o número de nós com grau mínimo de 0 esteja incorreta.

Por exemplo, considere as três ordens:Begin {align} 1, 2, 3, 4, 5, 6, 7, 8 5, 1, 6, 3, 8, 2, 4, 7 2, 7, 3, 8, 1, 4, 4 , 5, 6 end {align}

Primeiro podemos obter o seguinte gráfico intermediário:

    _____
   / ____\__
  / / ____\_\__
 / / /     \ \ \
1 2 3->4 5->6 7 8
 \ \__/
  \__/

Aplicando sua abordagem, removeremos 1->4, 2->4 e 3->4 (ou 3->8), e há 5 nós com grau 0:1, 2, 3, 4 (ou 8), 5.Contudo, a solução ideal seria

     _______
    / ____ _\__
   / /       \ \
1 2 3 4 5->6 7 8
 \___/

onde apenas 4 nós têm grau 0:1, 2, 3, 5.