Tri un graphique pour faire autant de flèches pointent vers l'avant que possible

Question

Je dois trier les noeuds d'un graphe orienté de telle sorte que le nombre de flèches qui coulent vers l'arrière (contre l'ordre de tri) est minime.

Je peux penser à des algorithmes (par exemple garder la permutation des noeuds jusqu'à ce qu'aucun échange permettra d'améliorer les choses), mais je ne sais pas à quelle vitesse ils courent ou si elles arrivent à la meilleure solution.

Quel est le nom et la complexité de ce problème?

Answer 1

Après réflexion, je me suis aperçu que le problème peut être divisé en deux:

1. déterminer un plus grand sous-graphe acyclique d'un graphe (qui est NP-dur )
2. topologiquement trier (qui est beaucoup plus facile )

Answer 2

Le tri des nœuds afin de la profondeur peut être fait avec un tri topologique. Cependant, cette ne fonctionne qu'avec des graphiques qui ne contiennent pas de cycles. Votre problème semble comme il y a des cycles dans le graphique. Une option serait de trouver les cycles (voir le algorithme Tortoise et Hare pour une méthode de faire cela) et briser le cycle, l'enregistrement où vous l'avez cassé. Ensuite, trier les nœuds et re-lien.

Si vous faites cela à des fins de visualisation, il est une bibliothèque de rendu graphique appelé GraphViz qui fait quelque chose de très semblable à ce que vous décrivez et définit les nœuds. Il est facile à intégrer et à utiliser et rendre à l'écran ou une variété de formats de sortie.