Anzahl gerichteter Graphen

25.02.2013, 13:53

2phil.05.phil

Anzahl gerichteter Graphen

Meine Frage:
Wie viele gerichtete Graphen mit n Knoten gibt es, wenn von jedem der n Knoten k Kanten abgehen?

Wie viele dieser Graphen besitzen keine! reine Quelle?
Also jeder Knoten soll auch min. eine eingehende Kante haben.

Meine Ideen:
Ich glaube für die erste Frage erhält man so etwas wie:
$\begin{eqnarray*} Anzahl=\begin{pmatrix} n-1 \\ k \end{pmatrix}^n \end{eqnarray*}$
da man von jedem Knoten aus n-1 weitere Knoten erreichen kann und von denen wählt man k aus. Diese Möglichkeit hat man für alle n Knoten und kann sie somit munter durchpermotieren, also hoch n das ganze.

Für den zweiten Teil komme ich auf keine brauchbaren Ideen...
Die Gegenfrage dazu wäre: Wie viele Graphen gibt es in dem genau ein Knoten nicht erreicht wird, zwei Knoten nicht erreicht werden, ... , n-(k+1) Knoten keine eingehende Kante besitzen.
So richtig weiterverwerten konnte ich diese Erkenntnis leider noch nicht.

25.02.2013, 14:33

Math1986

Auf diesen Beitrag antworten »

RE: Anzahl gerichteter Graphen
Hallo,
Ich gehe im Folgenden mal davon aus, dass der Graph keine Mehrfachkanten und keine Schleifen haben darf, sonst muss man manches anpassen. Wäre gut, wenn sowas vorher genannt wird.

Das erste ist richtig.

Bei der zweiten wäre es wohl am einfachsten, du berechnest die Anzahl Graphen mit mindestens einer Quelle, und ziehst dies vom Ergebnis der ersten Aufgabe ab.
Nimm also an, der Graph habe eine Quelle q, und gehe nach dem selben Prinzip wie oben vor.

25.02.2013, 15:38

2phil.05.phil

Auf diesen Beitrag antworten »

RE: Anzahl gerichteter Graphen
Entschuldige, natürlich sollen Schleifen und Mehrfachkanten verboten sein, als von Knoten i erreicht man k von einander verschiedene Knoten (außer i)

Ok wie sähe das für diese eine Quelle aus?

$\begin{eqnarray*} \begin{pmatrix} n-1 \\ k\\\end{pmatrix}^n-\left(\begin{pmatrix} n-1 \\ k\\\end{pmatrix}*\begin{pmatrix} n-2 \\ k\\\end{pmatrix}^{n-1} \right) \end{eqnarray*}$

und insgesamt dann

$\begin{eqnarray*} \begin{pmatrix} n-1 \\ k\\\end{pmatrix}^n-\left(\begin{pmatrix} n-1 \\ k\\\end{pmatrix}*\begin{pmatrix} n-2 \\ k\\\end{pmatrix}^{n-1} +\begin{pmatrix} n-2 \\ k\\\end{pmatrix}^2*\begin{pmatrix} n-3 \\ k\\\end{pmatrix}^{n-2}+...+\begin{pmatrix} n-(k+1) \\ k\\\end{pmatrix}^{(k+1)}*\begin{pmatrix} n-2 \\ k\\\end{pmatrix}^{n-(k+1)} \right) \end{eqnarray*}$

?

Vielen Dank schon mal für deine Hilfe! smile

25.02.2013, 16:16

Math1986

Auf diesen Beitrag antworten »

RE: Anzahl gerichteter Graphen

Zitat:

$\begin{eqnarray*} \begin{pmatrix} n-1 \\ k\\\end{pmatrix}^n-\left(\begin{pmatrix} n-1 \\ k\\\end{pmatrix}*\begin{pmatrix} n-2 \\ k\\\end{pmatrix}^{n-1} \right) \end{eqnarray*}$

Nachtrag: Wenn das das Endergebnis seien soll, dann ist es richtig.

Das zweite ist dann falsch, das oben war der Fall für mindestens eine Wurzel, beinhaltet also auch mehr als eine Wurzel.

25.02.2013, 16:26

2phil.05.phil

Auf diesen Beitrag antworten »

RE: Anzahl gerichteter Graphen
ja das sollte das Ergebnis für die Graphen sein, die nicht genau eine Quelle haben (sondern weniger oder mehr).

das darunter sollen nun alle Graphen sein in denen es gar keine Quelle gibt, also von jedem gehen k Kanten ab aber es trifft auch auf jeden min. eine Kante

25.02.2013, 16:27

Math1986

Auf diesen Beitrag antworten »

RE: Anzahl gerichteter Graphen

Zitat:

Original von 2phil.05.phil
das darunter sollen nun alle Graphen sein in denen es gar keine Quelle gibt, also von jedem gehen k Kanten ab aber es trifft auch auf jeden min. eine Kante

Wie gesagt: Das zweite ist dann falsch, das oben war der Fall für mindestens eine Wurzel, beinhaltet also auch mehr als eine Wurzel.

25.02.2013, 16:35

2phil.05.phil

Auf diesen Beitrag antworten »

RE: Anzahl gerichteter Graphen
aber für den Fall n=3 und k=1 stimmt es schon nicht... denn dann gibt es 2 Graphen die die Bedingung erfüllen:
1->2 ->3->(1) und (3)<-1<-2<-3

und 6 die das nicht tun.

Die Formel liefert mir als Ergebnis nun aber 7...

Neue Frage »

Antworten »

Anzahl gerichteter Graphen

Verwandte Themen