Algorithmus zum Finden aller azyklischen Orientierungen eines Graphen

Ich arbeite an azyklischen Orientierungen ungerichteter Graphen und habe folgende Fragen:

Wie kann man bei einem verbundenen ungerichteten einfachen Graphen alle möglichen azyklischen Orientierungen von ? $G$ $G$
Wie viele azyklische Orientierungen gibt es? Es ist (von hier ) bekannt, dass für einen Graphen mit Eckpunkten ist, wobei das bei bewertete chromatische Polynom ist ; aber es gelang mir nicht zu verstehen, wie man mit einem negativen Wert ( ) bewertet . $(-1)^p\ \chi(G,-\lambda)$ $G$ $p$ $\chi$ $-\lambda$ $\chi$ $-\lambda$

algorithms graph-theory counting Seteropere
quelle

Re 2,

ist nur ein Polynom. Es kann an jedem komplexen Punkt ausgewertet werden. Die Anzahl der azyklischen Orientierungen beträgt

, wobei

die Anzahl der Eckpunkte ist. Zum Beispiel ist das chromatische Polynom eines Dreiecks

, und daher ist die Anzahl der azyklischen Orientierungen

χ (G, \cdot)

$\chi(G,\cdot)$

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

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

p

$p$

t (t - 1) (t - 2)

$t(t-1)(t-2)$

(alle

Orientierungen außer den

zyklischen Orientierungen).

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

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

2^{3}

$2^3$

2

$2$

Yuval Filmus

@ YuvalFilmus vielen Dank. es geht also darum, das Polynom bei

bewerten .

- λ

$-\lambda$

Seteropere

Antworten:

Wie Yuval bemerkte, können Sie die Anzahl der azyklischen Orientierungen zählen, indem Sie das chromatische Polynom eines Graphen bei negativer Einheit auswerten. Für die Berechnung chromatischer Polynome sind für einige Graphklassen effiziente Algorithmen bekannt .

Es gibt auch einen rekursiven Algorithmus zum Erzeugen aller azyklischen Orientierungen eines von Squire [1] gegebenen Graphen. Der Algorithmus benötigt Zeit pro erzeugter azyklischer Orientierung. Vor ungefähr 20 Jahren war dies der schnellste bekannte Algorithmus. Es ist möglich, dass jetzt ein schnellerer bekannt ist oder dass Sie den Squire-Algorithmus durch bekannte Techniken verbessern können. $O(n)$

[1] Squire, MB (1998). Generieren der azyklischen Orientierungen eines Graphen. Journal of Algorithms, 26 (2), 275 & ndash; 290.

Juho
quelle