Kombinatorik orientierter Graphen

25.04.2017, 17:44

SunSharks

Kombinatorik orientierter Graphen

Meine Frage:
Wie viele Möglichkeiten für verschiedene orientierte Graphen mit n Knoten gibt es? Dabei ist ein orientierter Graph folgendermaßen definiert:
Zwischen zwei Knoten v,w darf entweder eine Kante (v,w) oder eine Kante (w,v) oder keine Kante existieren.

Meine Ideen:
Ich habe es bereits für den ungerichteten und für den gerichteten Fall gezeigt. Dabei ging ich davon aus, dass es $\begin{eqnarray*} \frac{n(n-1)}{2} \end{eqnarray*}$ mögliche Kanten im gerichteten und $\begin{eqnarray*} n(n-1) \end{eqnarray*}$ mögliche Kanten im ungerichteten Fall gibt. Dann habe ich in beiden Fällen die Summe über alle möglichen k des Binomialkoeffizienten der max.Kantenanzahl über k gebildet und kam dann mithilfe des binomischen Lehrsatzes auf 2^(Max. Kantenanzahl).
$\begin{eqnarray*} \sum\limits_{k=0}^{\frac{n(n-1)}{2} } \begin{pmatrix} \frac{n(n-1)}{2} \\ k \end{pmatrix} \end{eqnarray*}$ bzw. $\begin{eqnarray*} \sum\limits_{k=0}^{n(n-1)} \begin{pmatrix} n(n-1) \\ k \end{pmatrix} \end{eqnarray*}$
Oder ist mein Vorgehen dort bereits falsch?

Die maximale Kantenanzahl im orientierten Graphen ist ja genau wie im ungerichteten Fall (n(1-1))/2. Allerdings weiß ich nicht, wie ich jetzt vorgehen kann, da es ja, anders als im ungerichteten Fall mit 2, pro Knotenpaar 3 Möglichkeiten der Kantenanzahlen gibt.

25.04.2017, 17:56

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von SunSharks
und kam dann mithilfe des binomischen Lehrsatzes auf 2^(Max. Kantenanzahl).

[...]

Allerdings weiß ich nicht, wie ich jetzt vorgehen kann, da es ja, anders als im ungerichteten Fall mit 2, pro Knotenpaar 3 Möglichkeiten der Kantenanzahlen gibt.

Kombiniere mal diese beiden Ideen. smile

Und bei Unsicherheit: Einfach mal für kleine Knotenzahlen n=2,3,4 nachzählen, bevor man leichtfertig irgendwelche Formeln aus dem Hut zaubert.

25.04.2017, 20:49

SunSharks

Auf diesen Beitrag antworten »

Vielen Dank für den Tipp!

Ok, also muss ich tatsächlich von einem anderen Blickwinkel aus rangehen. Ich habe mir nun überlegt, dass es im einfachen, ungerichteten Fall $\begin{eqnarray*} \frac{n(n-1)}{2} \end{eqnarray*}$ Kombinationsmöglichkeiten jeweils zweier Knoten gibt und pro Zweierkombi sind zwei Fälle möglich: keine Kante oder eine Kante. Damit ergeben sich $\begin{eqnarray*} 2^{\frac{n(n-1)}{2}} \end{eqnarray*}$ Möglichkeiten, den Graphen zu gestalten.

Übertrage ich das darauf, dass pro Zweierkombination (der Graph ist zwar gerichtet, aber es existieren trotzdem $\begin{eqnarray*} \frac{n(n-1)}{2} \end{eqnarray*}$ "Zwischenräume") drei Fälle möglich sind, gibt es wohl $\begin{eqnarray*} 3^{\frac{n(n-1)}{2}} \end{eqnarray*}$ verschiedene orientierte, einfache Graphen mit Knotenanzahl n?

25.04.2017, 21:41

HAL 9000

Auf diesen Beitrag antworten »

Exakt so ist es. Freude

25.04.2017, 21:49

SunSharks

Auf diesen Beitrag antworten »

Super, vielen Dank, jetzt ist mir das auch ein wenig klarer.

Neue Frage »

Antworten »

Kombinatorik orientierter Graphen

Verwandte Themen