Algorithme pour trouver toutes les orientations acycliques d'un graphe

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

Étant donné le graphe simple non orienté connecté , comment trouver toutes les orientations acycliques possibles de ? $G$ $G$
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\ \chi(G,-\lambda)$ $G$ $p$ $\chi$ $-\lambda$ $\chi$ $-\lambda$

algorithms graph-theory counting sétéropère
la source

Re 2,

χ (G, \cdot)

$\chi(G,\cdot)$ est juste un polynôme. Il peut être évalué en tout point complexe. Le nombre d'orientations acycliques est

(- 1)^{p} χ (G, - 1)

$(-1)^p \chi(G,-1)$ , où

p

$p$ est le nombre de sommets. Par exemple, le polynôme chromatique d'un triangle est

t (t - 1) (t - 2)

$t(t-1)(t-2)$ , et donc le nombre d'orientations acycliques est

(- 1)^{3} (- 1) (- 2) (- 3) = 6

$(-1)^3(-1)(-2)(-3) = 6$ (tout

2^{3}

$2^3$ orientations autres que la

2

$2$ orientations cycliques).

Yuval Filmus

@YuvalFilmus merci beaucoup. il est donc question d'évaluer le polynôme à

- λ

$-\lambda$ .

seteropere

Réponses:

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écessite $O(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