Algorithme pour trouver toutes les orientations acycliques d'un graphe

8

Je travaille sur les orientations acycliques des graphes non orientés et j'ai les questions suivantes:

  1. Étant donné le graphe simple non orienté connecté , comment trouver toutes les orientations acycliques possibles de ?gg
  2. Quel est le nombre d'orientations acycliques? Il est connu (d' ici ) d'être pour un graphe avec sommets où est le polynôme chromatique évalué à ; mais je n'ai pas réussi à comprendre comment évaluer à une valeur négative ( ). (-1)p χ(g,-λ)gpχ-λχ-λ
sétéropère
la source
3
Re 2, χ(g,)est juste un polynôme. Il peut être évalué en tout point complexe. Le nombre d'orientations acycliques est(-1)pχ(g,-1), où pest le nombre de sommets. Par exemple, le polynôme chromatique d'un triangle estt(t-1)(t-2), et donc le nombre d'orientations acycliques est (-1)3(-1)(-2)(-3)=6 (tout 23 orientations autres que la 2orientations cycliques).
Yuval Filmus
@YuvalFilmus merci beaucoup. il est donc question d'évaluer le polynôme à-λ.
seteropere

Réponses:

5

Comme l'a noté Yuval, vous pouvez compter le nombre d'orientations acycliques en évaluant le polynôme chromatique d'un graphique à l'unité négative. Pour calculer les polynômes chromatiques, il existe des algorithmes efficaces connus pour certaines classes de graphes .

Il existe également un algorithme récursif pour générer toutes les orientations acycliques d'un graphe donné par Squire [1]. L'algorithme nécessiteO(n)temps par orientation acyclique générée. Il y a environ 20 ans, c'était l'algorithme le plus rapide connu; il est possible qu'un plus rapide soit connu maintenant, ou que vous puissiez améliorer l'algorithme de Squire par des techniques connues.


[1] Squire, MB (1998). Génération des orientations acycliques d'un graphe. Journal of Algorithms, 26 (2), 275-290.

Juho
la source