Algorithmus zum Finden aller azyklischen Orientierungen eines Graphen

8

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

  1. Wie kann man bei einem verbundenen ungerichteten einfachen Graphen alle möglichen azyklischen Orientierungen von G finden ?GG
  2. 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 χ(G,λ)Gpχλχλ
Seteropere
quelle
3
Re 2, ist nur ein Polynom. Es kann an jedem komplexen Punkt ausgewertet werden. Die Anzahl der azyklischen Orientierungen beträgt ( - 1 ) p χ ( G , - 1 ) , wobei p die Anzahl der Eckpunkte ist. Zum Beispiel ist das chromatische Polynom eines Dreiecks t ( t - 1 ) ( t - 2 ) , und daher ist die Anzahl der azyklischen Orientierungen ( - 1 ) 3 ( - 1 )χ(G,)(1)pχ(G,1)pt(t1)(t2) (alle 2 3 Orientierungen außer den 2 zyklischen Orientierungen). (1)3(1)(2)(3)=6232
Yuval Filmus
@ YuvalFilmus vielen Dank. es geht also darum, das Polynom bei bewerten . λ
Seteropere

Antworten:

5

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