Anzahl der gerichteten Graphen?
Wie kann man die Anzahl der gerichteten Graphen mit n Knoten zählen? Und wie viele davon gibt es?
1 Antwort
Hier findet sich die Formel a(n) ~ 2^(n*(n-1))/n!
Da steht allerdings "∼" und nicht "=". Ich bin mir nicht sicher, was das genau bedeutet, wahrscheinlich nur ungefähr. 2^m ist im Allgemeinen auch nicht durch n! teilbar. Ich habe jetzt selber ein paar Zahlen ausprobiert. Das sieht eher nach einem Wachstumsverhalten aus. Wenn da keine genaue Formel steht, gehe ich davon aus, dass es auch keine einfache gibt für diese Folge.
Überlegungen zu der angegeben Formel:
n ⋅ (n - 1) sind die maximale Anzahl der Kanten.
2^... bedeutet, dass es jeweils die Möglichkeiten gibt "Kante vorhanden" und "Kante fehlt".
n! ist die Anzahl der Permutationen der Knoten.
Die Formel "a(n) = 2^(n*(n-1))/n!" gibt die Anzahl der ungerichteten Graphen mit n Knoten an. Um die Anzahl der gerichteten Graphen zu bekommen musste ich die Formel zu "a(n) = (n!) * 2^(n(n-1)/2)" abwandeln.